Different Implementation of Linked List
Definition
A linked list is a linear, dynamic data structure in which elements are stored in nodes, and each node contains data along with one or more links that connect it to other nodes in the sequence. The way these links are arranged creates different implementations of linked lists such as singly linked lists, doubly linked lists, circular linked lists, and circular doubly linked lists.
Main Content
1. Singly Linked List
A singly linked list is the simplest and most commonly taught implementation of a linked list. In this structure, each node contains two parts:
Data part
- : stores the actual value
Next pointer
- : stores the address of the next node in the sequence
The last node points to NULL, which indicates the end of the list.
Structure
A node in a singly linked list can be represented as:
[Data | Next]
Example:
10 -> 20 -> 30 -> NULL
Features
- Traversal is possible only in one direction, from the first node to the last node.
- Insertions and deletions are efficient when the position is already known.
- Memory usage is lower than doubly linked lists because only one link is stored in each node.
Example
If we create a list with values 5, 15, and 25:
Head -> [5 | •] -> [15 | •] -> [25 | NULL]
Here, Head points to the first node, and each node stores the address of the next node.
Advantages
- Simple to implement
- Requires less memory
- Useful when only forward traversal is needed
Limitations
- Cannot traverse backward
- Deleting a node usually requires access to the previous node
- Searching still takes linear time
2. Doubly Linked List
A doubly linked list is an advanced implementation in which each node contains three parts:
Data
Previous pointer
- : points to the previous node
Next pointer
- : points to the next node
This structure allows traversal in both directions.
Structure
A node in a doubly linked list can be represented as:
[Prev | Data | Next]
Example:
NULL <- 10 <-> 20 <-> 30 -> NULL
Features
- Forward and backward traversal are both possible.
- Deletion becomes easier because the previous node is directly available.
- It is useful in applications requiring movement in both directions, such as browser history, undo/redo systems, and music playlists.
Example
Consider the list:
Head -> [NULL | 8 | •] <-> [• | 16 | •] <-> [• | 24 | NULL]
The first node has no previous node, so Prev = NULL. The last node has no next node, so Next = NULL.
Advantages
- Bidirectional traversal
- Easier deletion of a given node
- More flexible than singly linked lists
Limitations
- Requires extra memory for the previous pointer
- More complex to implement
- Pointer updates are more error-prone during insertion and deletion
3. Circular Linked List
A circular linked list is a linked list in which the last node does not point to NULL. Instead, it points back to the first node, forming a circle. This implementation can be based on either singly linked or doubly linked structures.
Structure
For a singly circular linked list:
10 -> 20 -> 30 -> back to 10
Diagram:
Head -> [10 | •] -> [20 | •] -> [30 | •]
^ |
|_________________________|
Features
- There is no terminal
NULLnode. - Starting from any node, the list can eventually be traversed completely if the links are followed correctly.
- It is especially useful for applications where data must be processed repeatedly in a loop.
Example
A circular linked list of players in a round-robin game can be represented as:
A -> B -> C -> D -> back to A
This makes it easy to move from one player to the next indefinitely.
Advantages
- Useful for cyclic tasks
- No need to restart traversal after reaching the end
- Efficient for applications like CPU scheduling and buffering
Limitations
- Traversal must be handled carefully to avoid infinite loops
- Detecting the end of the list is less straightforward
- Implementation requires extra attention
Working / Process
1. Create the first node
- Allocate memory for the first node.
- Store the data in the node.
- Set the link fields appropriately depending on the implementation.
- In a singly linked list, the next pointer of the first node may initially be
NULL. - In a circular linked list, it may point to itself if it is the only node.
2. Connect additional nodes
- Allocate memory for each new node.
- Store the new data.
- Update pointers to connect the new node in the correct position.
- In a singly linked list, set the previous node’s next pointer to the new node.
- In a doubly linked list, update both previous and next pointers.
- In a circular linked list, ensure the last node points back to the first node.
3. Traverse, insert, and delete nodes
- Start from the head node and move through the links.
- For traversal in singly linked lists, move only forward.
- For traversal in doubly linked lists, move forward or backward.
- For insertion, adjust the surrounding node pointers without shifting elements as in arrays.
- For deletion, reconnect neighboring nodes so the removed node is bypassed.
- Finally, free the memory of deleted nodes to avoid memory leaks.
Advantages / Applications
Efficient dynamic memory use
- : Linked lists grow and shrink at runtime without needing a fixed size.
Easy insertion and deletion
- : Adding or removing nodes is often faster than in arrays because element shifting is avoided.
Used in real-world systems
- : Linked lists are used in stacks, queues, memory management, graph adjacency lists, browser navigation, playlists, and round-robin scheduling.
Summary
- Linked lists store data in nodes connected by links rather than in contiguous memory.
- Different implementations include singly linked lists, doubly linked lists, and circular linked lists.
- The choice of implementation depends on traversal needs, memory usage, and application requirements.
- Important terms to remember: node, head, next pointer, previous pointer, NULL, circular link, traversal, insertion, deletion