Lesson 3.1
Nodes and References
A linked list is nodes each holding a value and a reference onward. There is no index, so position k costs k steps to reach.
Lessons and exercises
The first structure with no indexing. Everything is reached by following references, which trades constant-time access for cheap insertion and removal once you are already in position.
Lesson 3.2
Insertion and Removal
Once positioned, inserting or removing costs constant time because only a couple of references change. Getting positioned is the expensive part.
Lesson 3.3
Singly Versus Doubly Linked
A doubly linked list adds a backward reference, which makes removal constant time given only a node reference, at the cost of memory and bookkeeping.
Lesson 3.4
Edge Cases
The empty list, the single-element list, and operations at the head or tail are where implementations break, because those are the cases where a reference is null.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic