DataslopeSingly Linked Lists
Understand node-based linked lists, traversal, insertion, deletion, search, memory management, and pointer reversal in C++
A singly linked list stores values in separate nodes connected by next pointers. Unlike a vector, nodes are not contiguous in memory. That means no O(1) random access, but adding to the front is simple and O(1).
Nodes and links
A minimal node stores data and a pointer to the next node.
Build and traverse a list
Traversal starts at head and follows next until nullptr.
A vector jumps directly to v[i]. A linked list must walk one link at a time to reach the ith node.
Prepend with push_front
Prepending creates a new node, points it at the old head, then updates the head pointer.
Append, search, and delete
Appending without a tail pointer requires walking to the end. Deleting a value requires tracking both the current node and the previous link.
Linked list operation costs
| Operation | Complexity | Note |
|---|---|---|
| access ith element | O(n) | Must follow links from the head |
| prepend | O(1) | Change one pointer |
| append without tail pointer | O(n) | Must find the last node |
| search by value | O(n) | May inspect every node |
Memory management with std::unique_ptr
Manual new and delete are useful for learning pointers, but production C++ should prefer ownership types. A node can own its successor with std::unique_ptr<Node>.
Pointers are links, not values
When you reverse or delete nodes, you are rewiring addresses. Draw the links before changing them; losing the only pointer to a node causes a memory leak.
Practice: reverse a linked list
Implement Node* reverse(Node* head). The driver builds 1->2->3->4 and prints the reversed values.
Practice: length of a linked list
Implement length by traversing from head to null and counting nodes.
Check your understanding
Which operation is O(1) on a singly linked list when you have the head pointer?
Accessing the element at index 900
Prepending a new node to the front
Searching for a value
Sorting the list
Why does a singly linked list not support efficient random access like a vector?
Nodes are connected by pointers, so reaching position i requires following i links.
Each node stores too many integers.
The compiler forbids indexing syntax for structs.
A linked list is always sorted.
What must you avoid when manually deleting nodes allocated with new?
Updating the head pointer
Losing the only pointer to a node before calling delete
Traversing with a temporary pointer
Comparing node values