Linked lists are dynamic data structures made of nodes connected by references or pointers. This cheat sheet helps students compare common linked list operations and remember how head, tail, and next references change. It is useful when tracing code, writing pseudocode, and analyzing the cost of list operations.
Key Facts
- A singly linked list node stores data and a next pointer, often written as node = (data, next).
- The head pointer references the first node, and an empty linked list has head = null.
- Traversal starts at head and repeatedly moves current = current.next until current = null.
- Searching an unsorted linked list takes O(n) time because nodes may need to be checked one by one.
- Inserting at the front of a singly linked list takes O(1) time using newNode.next = head and head = newNode.
- Deleting the first node takes O(1) time using head = head.next, assuming the list is not empty.
- Inserting or deleting after a known node takes O(1) time, but finding that node usually takes O(n) time.
- A doubly linked list node has prev and next pointers, which allows movement in both directions but uses extra memory.
Vocabulary
- Node
- A node is one element of a linked list that stores data and one or more links to other nodes.
- Head
- The head is the pointer or reference to the first node in a linked list.
- Tail
- The tail is the last node in a linked list, where tail.next is usually null in a singly linked list.
- Pointer
- A pointer is a reference that stores the location of another node or object.
- Traversal
- Traversal is the process of visiting each node in a linked list in order.
- Big-O Notation
- Big-O notation describes how an algorithm's time or memory use grows as the input size increases.
Common Mistakes to Avoid
- Forgetting to update head during front insertion or deletion is wrong because the list's first node changes and head must point to the new first node.
- Changing pointers in the wrong order during insertion is wrong because the rest of the list can become unreachable if a link is overwritten too early.
- Assuming linked lists allow O(1) random access is wrong because reaching index i requires moving through nodes from the head.
- Deleting a node without saving the previous node is wrong in a singly linked list because the previous node's next pointer must be redirected.
- Ignoring the empty-list case is wrong because operations such as head.next cause errors when head = null.
Practice Questions
- 1 A singly linked list contains 12 nodes. In the worst case, how many nodes must be checked to search for a value that is not in the list?
- 2 Starting with head -> 4 -> 7 -> 9 -> null, insert 2 at the front. What should head point to, and what is the new list order?
- 3 A current node stores 15 and current.next points to a node storing 20. Write the pointer updates needed to insert a new node storing 18 after current.
- 4 Why is inserting at the front of a linked list usually faster than inserting at the end when no tail pointer is stored?
Understanding Linked List Operations Reference
The key idea in linked list code is to protect the chain before changing it. A pointer holds the route to another node. If a program overwrites that route too early, part of the list can become unreachable.
That lost section may still exist in memory for a while, but the program has no normal way to reach it. Before an insertion or deletion, draw the nodes as boxes with arrows. Mark the current pointer, the previous pointer when needed, and the node being changed.
Then update the arrows in the same order as the code. This tracing habit catches many errors that are hard to spot by reading code alone.
The first and last positions need special care because they have fewer neighbors. A list with no nodes, one node, or many nodes can behave differently during the same operation. For example, removing the only node must leave both the start reference and any stored end reference empty.
Inserting into an empty list must establish the first reachable node. If a program keeps a tail pointer, adding at the end can be fast because the last node is already known.
The program must still connect the old tail to the new node, then move tail to the new node. Forgetting either step leaves an incorrect structure.
Deletion usually requires more thought than insertion. To remove a node from the middle of a singly linked list, code needs access to the node before it. That earlier node is redirected to skip over the target.
The removed node should no longer point into the list when a language or course expects references to be cleared. Removing by value creates another issue.
If the same value occurs several times, the algorithm needs a stated rule such as remove the first matching node or remove every matching node. Searching and deleting must handle the case where no match is found without changing any links.
Linked lists show why running time depends on access patterns, not just on the number of stored items. An array can directly reach an item at a chosen index because its elements occupy predictable positions. A linked list must follow links from the beginning to reach a position.
This makes linked lists useful when items are frequently added or removed near a location already known to the program. They are less useful when a program repeatedly needs random indexed access.
Students meet this tradeoff in music queues, task histories, browser navigation models, memory managers, and implementations of stacks or queues. When studying, separate the cost of locating a position from the cost of changing links once that position has been located.