Building a LinkedList

Last chapter left head, tail, and size as loose variables the caller had to keep in sync, with the list’s ListItem structure exposed to anyone using it. This chapter wraps that structure in a LinkedList<T> class that owns its own state and hides the internals. It also shows how to use sentinel nodes to remove the boundary-case branches that make the code more complex.

After reading this chapter, you should be able to:

• Motivate a LinkedList abstraction in terms of encapsulation, information hiding, and the invariants a class can keep that loose head/tail/size variables cannot
• Define a LinkedList<T> that owns head, tail, and size behind a private generic doubly linked Node<T>, separating the public list operations from the private node details
• Implement the access and search operations (a private node(index) helper, get/set, and indexOf/contains with Objects.equals) and explain why indexed access is $O(n)$
• Implement add, remove(index), and remove(value), keeping the head, tail, and size invariants correct as nodes are inserted and unlinked
• Compare the operation costs of LinkedList and DynamicArray, and choose the implementation that fits a given access or update pattern
• Explain how front and back sentinel nodes remove the list’s boundary-case branches

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

Sections

1. Why the List Needs an Abstraction
2. A Class to Own the List
3. From ListItem to Node
4. Keeping the Size
5. Adding to the List
6. Getting by Index
7. Setting by Index
8. Searching the List
9. Removing by Index
10. Removing by Value
11. The Whole Class
12. Two Lists, Side by Side
13. Special Cases at the Ends
14. A Sentinel Node