Unit 14: Linked Lists
Nodes scattered anywhere in memory, connected by pointers alone, and the exact order of reassignments that keeps or loses the rest of the list.
6 topics · 22 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Singly Linked List Structure: Nodes and next Pointers
- How it worksHow does each node hold a value and a pointer to the next node instead of sitting next to it in memory?
- Worked exampleTrace building the list 3 → 7 → 1 by creating three nodes and setting each node's next pointer.
- Common mistakeWhy isn't a linked list's third element reachable in one step the way an array's third element is?
Your turn1 of 2
A linked list is built from 697 nodes, each holding a value and a pointer to the next node. How many total next-pointers exist across all n nodes, including the last one's pointer to None?Traversing a Linked List
- How it worksHow does a traversal follow next pointers one node at a time until it hits a node whose next is None?
- Worked exampleTrace a traversal printing every value in the list 5 → 2 → 8 → None.
- Going furtherWhat happens to a traversal if a node's next pointer accidentally points back to an earlier node?
Your turn1 of 2
A traversal follows next pointers one node at a time until it reaches a node whose next is None, in a list of 697 nodes. How many next-pointer follows does the traversal make to reach the last node from the head?Inserting a Node: The Exact Order of Pointer Reassignments
- How it worksHow does inserting a node between two existing ones require setting the new node's next before the earlier node's next?
- Worked exampleTrace inserting node 9 between nodes 3 and 7 by first setting 9's next to 7, then 3's next to 9.
- Common mistakeWhy doesn't inserting at the front of a linked list require shifting any other node?
- Going furtherWhat changes about the reassignment order once you insert at the very front of the list instead of the middle?
Your turn1 of 2
Inserting one new node between two existing nodes in a linked list requires exactly 2 pointer reassignments: setting the new node's next, then the earlier node's next. For 349 such middle insertions performed one at a time, how many total pointer reassignments does this require?Deleting a Node and Losing the Rest of the List
- How it worksHow does deleting node B between A and C require setting A's next straight to C before B is let go?
- Worked exampleTrace deleting node 7 from 3 → 7 → 1 and find what happens if 3's next is cleared before it points to 1.
- Common mistakeWhy doesn't setting a node's own next pointer to None remove that node from the rest of the list?
- Ties togetherHow does losing the rest of a list from a bad deletion connect to why aliasing two names to one object is risky?
- Going furtherWhat happens once the deleted node still has other variables in the program pointing directly at it?
Your turn1 of 2
Deleting node B between A and C requires setting A's next straight to C before B is let go. For 349 such middle deletions performed one at a time, how many total pointer reassignments does this require, at one reassignment per deletion?Doubly Linked Lists
- How it worksHow does a doubly linked list add a previous pointer so each node can be reached in both directions?
- Worked exampleTrace inserting a node between two existing nodes in a doubly linked list and setting all four pointers involved.
- Going furtherWhat changes about deleting a node once every node also has a previous pointer to update?
Your turn1 of 2
A doubly linked list has 697 nodes, and each node holds both a next pointer and a previous pointer. How many total pointers, next plus previous, exist across all n nodes?Circular Linked Lists
- How it worksHow does the last node's next pointer loop back around to point at the first node instead of stopping?
- Worked exampleTrace traversing a circular list of 3 nodes for exactly 7 steps and find which node you land on.
- Common mistakeWhy doesn't a naive traversal notice on its own that it has already visited a node in a circular list?
- Going furtherWhat happens once two pointers moving at different speeds are used to detect whether a list is circular?
Your turn1 of 2
A circular list of 15 nodes is traversed starting from node 0, taking exactly 2 steps forward, where steps is less than n so no wraparound happens. Which node index does the traversal land on?