Layers of Logic

Phase X

The Collections Framework

Different ways to store data, and when each one makes sense.

8 sections152 min of reading34 exercises

Data structures are tradeoffs: what makes one operation quick can make another cost more. Java's collection framework offers several choices behind shared interfaces. You will look inside HashMap and find an array of buckets, calls to your hashCode, and the bit trick from Phase III. The pieces come from Phases IV, VII, VIII, and IX; this phase shows how they fit together.

When you finish this phase you can

  • Explain why there is no single best data structure, using a concrete trade
  • Read the framework hierarchy and say why Map sits outside Collection
  • Say what the for-each loop is really compiled into
  • Choose between ArrayList and LinkedList from first principles, not folklore
  • Explain how HashMap finds a value without searching
  • Implement Comparable correctly and say how it fails when you do not
  1. 10.1The Collections FrameworkEach way of storing data makes some jobs quick and others costly. Java gives you several choices behind shared interfaces, so you can switch when your program needs something different.The Collections FrameworkCore19 min4 exercises
  2. 10.2Iterable and the IteratorThe for-each loop is not a loop. It is one interface with one method, and it is why the same line works on an array, a list, a set and a map.IteratorCore18 min4 exercises
  3. 10.3The Collection InterfaceThe dozen methods every collection in Java has, and the rule that decides which methods live here rather than in List or Set.CollectionCore16 min4 exercises
  4. 10.4List: ArrayList, LinkedList, Vector, StackFour classes implement List. You should use two of them. Java keeps the other two because deleting them would break code written in 1997.ListCore19 min4 exercises
  5. 10.5Set and Map: Inside HashMapFinding a value in a million without searching. This is the section every earlier phase has been feeding, and your own hashCode is what makes it work.HashMapSetDeeper24 min5 exercises
  6. 10.6Map Methods, EnumMap, and the Rest of the FamilyThe methods you will actually call, plus four specialised maps. Two are worth knowing, one has a single use, and one Java would delete if it could.EnumMap and EnumSetCore18 min4 exercises
  7. 10.7Queue, Deque, and PriorityQueueWho is served next? A print queue answers "whoever arrived first". A hospital answers "whoever is most urgent". Both are queues, and the second one is a tree hiding inside an array.Queue and DequeHeapCore18 min4 exercises
  8. 10.8Comparable, Comparator, and SortingThree sections have deferred the same question. Java can sort Integers and Strings on its own, and it has no idea which of two Students comes first until you tell it.ComparableComparatorCore20 min5 exercises