Imagine you’re developing a simple game and need to store a list of player characters, say from Player 1 to Player 100. If you use an array, deleting a player from the middle requires shifting all subsequent players forward, which is cumbersome. This is where linked lists come in handy—each player’s information (data) only needs to remember the next player’s location (pointer), and they don’t need contiguous memory space. Insertions and deletions only require modifying a few pointers, like adjusting the bamboo sticks of a sugarcoated haws snack.
What is a Linked List?¶
A linked list is a linear data structure where each element (called a “node”) consists of two parts:
- Data Field: Stores specific information.
- Pointer Field: Stores the address of the next/previous node.
Unlike arrays, linked list nodes are not contiguous in memory—they’re like scattered beads strung together by a thread (the pointers).
Singly Linked List: A One-Way Sugarcoated Haws String¶
A singly linked list is the simplest type, with each node having only one pointer pointing to the next node. Think of it as a string of sugarcoated haws where each haw only knows the location of the next haw, not the previous one.
Structure of a Singly Linked List Node:¶
Data | Pointer → Next Node
For example, a singly linked list storing “Player 1 → Player 2 → Player 3”:
Player 1 Data | → Player 2
Player 2 Data | → Player 3
Player 3 Data | → null (end marker)
How to Use a Singly Linked List:¶
- Traversal: Only possible from the first node (head) by following pointers until reaching the last node (where
nextisnull). For example, to find the 5th player, you must traverse from the head one by one. - Insertion/Deletion: To insert a node in the middle, first find the “predecessor node,” then modify pointers. For example, inserting Player 4 between Player 2 and Player 3:
1. Locate Player 2 (original list: Player 1 → Player 2 → Player 3).
2. Create a new Player 4 node and set itsnextpointer to Player 3.
3. Update Player 2’snextpointer from Player 3 to Player 4.
This inserts the node without moving other players.
To delete Player 3, find Player 2 (the predecessor), then set Player 2’s next to Player 3’s next (which is null).
Doubly Linked List: A Two-Way Sugarcoated Haws String¶
A doubly linked list has an extra pointer per node—each node knows both the next and previous nodes. Now each haw is linked in both directions, like a sugarcoated haws string with double hooks.
Structure of a Doubly Linked List Node:¶
Previous Pointer ← Data → Next Pointer
For example, a doubly linked list storing “Player 1 → Player 2 → Player 3”:
null ← Player 1 Data → Player 2
Player 1 ← Player 2 Data → Player 3
Player 2 ← Player 3 Data → null
How to Use a Doubly Linked List:¶
- Traversal: Can start from any node and traverse bidirectionally (using
prevornext). For example, starting from Player 2, you can directly reach Player 1 (viaprev) or Player 3 (vianext). - Insertion/Deletion: More efficient for known nodes. For example, inserting Player 4 between Player 2 and Player 3:
1. Create Player 4 and set itsprevto Player 2.
2. Set Player 4’snextto Player 3.
3. Update Player 2’snextto Player 4.
4. Update Player 3’sprevto Player 4.
This modifies pointers directly without searching for the predecessor.
Singly vs. Doubly Linked Lists: Core Differences¶
| Comparison | Singly Linked List | Doubly Linked List |
|---|---|---|
| Node Structure | One pointer (next) only |
Two pointers (prev + next) |
| Traversal | Unidirectional (head to tail) | Bidirectional (forward/backward) |
| Insert/Delete | Requires finding predecessor, then modifying pointers | Directly modify prev/next—simpler |
| Memory Usage | Saves memory (no extra pointer) | Slightly higher (extra prev pointer) |
| Use Cases | Simple unidirectional storage (e.g., queues) | Bidirectional operations (e.g., browser history, deque) |
Why Learn Doubly Linked Lists?¶
A singly linked list suffices if your game only needs to display the player list “from start to end.” However, doubly linked lists are more flexible for scenarios like:
- Simultaneously managing “history” and “future” records (e.g., browser back/forward buttons).
- Frequent insertions/deletions in the middle of the list (e.g., phone contacts where you add/remove contacts bidirectionally from a known position).
Summary¶
- Singly Linked List: Like a single-file sugarcoated haws string—only eat from left to right. Simple, memory-efficient, and suitable for unidirectional operations.
- Doubly Linked List: Like sugarcoated haws with double hooks—eat from left to right or right to left. More versatile but slightly memory-heavy, ideal for bidirectional needs.
Don’t stress about complex operations initially. Focus on the core differences: number of pointers and traversal direction. You’ll master the details as you tackle real-world problems (e.g., implementing a deque with a doubly linked list)!