Lists Without Arrays

This chapter builds a linked list out of ListItem objects connected by next references and compares it with the array-backed list from earlier chapters. We write each operation as a function over a head reference, first the operations that read the list, then the ones that change its shape. Along the way we keep running into the same problem: the head is stored in the caller’s code, so an operation that changes it cannot update it. Separately, we look at adding a backward link to each item, which gives us a doubly linked list. The chapter ends by comparing the singly linked and doubly linked designs.

After reading this chapter, you should be able to:

  • Explain how a linked list stores a sequence as ListItem objects connected by next references
  • Contrast a linked list with an array-backed list in how each stores and connects its items
  • Implement the reading operations over a bare chain (traversal, size, get, set, and contains), each as a function over a head reference
  • Change the shape of a list with addFirst, addLast, insertAfter, insertBefore, and remove, rewiring next references
  • Return the new head from any operation that changes it
  • Explain why the caller must store the returned head back, since a Java method can only hand back one value
  • Reason about the cost of each operation, distinguishing an head re-point from an traversal to a position
  • Insert beside or remove a ListItem passed to you directly, rather than reaching it by index
  • Add a prev link to form a doubly linked list, weighing the benefit the extra link gives in operations against the extra bookkeeping it costs

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. A Different Kind of List
  2. The ListItem Class
  3. A Linked List
  4. Two Kinds of Lists
  5. Following the Chain
  6. Traversing a List
  7. The Size of a List
  8. Getting an Item by Index
  9. Setting an Item by Index
  10. Searching for an Item
  11. Prepend Operation
  12. Append Operation
  13. A Tail Pointer
  14. Inserting After an Item
  15. Inserting Before an Item
  16. Removing an Item
  17. Getting the Item Itself
  18. A Backward Link
  19. Removing a Given Item
  20. Singly and Doubly Linked Lists