Unit 3 · Moderate
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.
What a strong answer looks like
A strong Unit 3 answer draws the nodes, performs the reassignments in an order that never drops a needed reference, and states the resulting cost.
Know
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.
Apply
Walk from the head, counting steps, and keep a reference to the previous node when you may need to modify.
Watch out
Assuming constant-time access. That is an array property and does not survive the switch.
Study move
Draw a four-node list and write the traversal that reaches the third node.
Know
Once positioned, inserting or removing costs constant time because only a couple of references change. Getting positioned is the expensive part.
Apply
Write reassignments in an order that attaches the new node before detaching the old link.
Watch out
Overwriting the reference you still need, which silently drops the tail of the list.
Study move
Insert a node in the middle of a drawn list, numbering the reassignments in a safe order.
Know
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.
Apply
Choose doubly linked when removal by reference or backward traversal is needed.
Watch out
Forgetting to update both directions on a modification, which corrupts the list silently.
Study move
Remove a middle node from a doubly linked list and list every reference that must change.
Know
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.
Apply
Handle head and tail explicitly before writing the general middle case.
Watch out
Writing the general case first and patching the ends afterwards, which usually leaves one broken.
Study move
Write removal that works on an empty list, a one-node list, and removal of the head.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Given only a reference to a middle node of a singly linked list, remove it in constant time, and say for which node the technique fails.
