Lesson 028
Linked Lists
Nodes · Pointers · Traversal
1:00How linked lists store data in scattered nodes joined by pointers, why splice is O(1) but random access is O(n), and the classic singly/doubly/circular variants.
By the end, you can
- Describe the two parts of a node and the roles of HEAD and NULL.
- Trace the traversal of a linked list, writing the visit order from HEAD to tail.
- Explain why index access is O(n) on a linked list but O(1) on an array.
- Perform a splice insert and a splice delete by re-pointing the correct pointers in the correct order.
- State the time complexity of head insert/delete, arbitrary insert, search, and index access for a singly linked list.
- Distinguish the memory and cache trade-offs between arrays and linked lists.
- Identify the appropriate variant (singly, doubly, circular) for a given use-case.
- Recognize and avoid the three common linked-list pitfalls (lost head, null dereference, wrong pointer order).
- Describe the reverse-in-place algorithm, the slow/fast two-pointer pattern, and Floyd's cycle detection.
Up next in Linear Data Structures
