Linked List
A linked list is a data structure where elements (called nodes) are connected using pointers, and each node stores data and a reference to the next node in the sequence.
Fundamental Concepts
Types of Linked Lists
A singly linked list is a list where each node contains data and a pointer to the next node, forming a one-way chain.
Key idea: Can move only forward.
A doubly linked list is a list where each node contains data and two pointers — one to the next node and one to the previous node — allowing movement in both directions.
Key idea: Can move forward and backward.
A circular linked list is a list where the last node points back to the first node, forming a loop instead of ending with null.
Key idea: No end — forms a circle.
Traversal
Traversal in a linked list means visiting each node one by one starting from the head and following the pointers until the end, and its time complexity is O(n) because we may need to visit all nodes.
Access
Access in a linked list means reaching a specific node by starting from the head and following pointers until the desired position, and its time complexity is O(n) because nodes must be visited sequentially.
Insertion
Insertion in a linked list means adding a new node by updating pointers at the desired position, and its time complexity is O(1) if the position is known, or O(n) if traversal is needed to find the position.
Deletion
Deletion in a linked list means removing a node by updating pointers to skip it, and its time complexity is O(1) if the node is known, or O(n) if traversal is needed to locate it.
Search
Search in a linked list means checking each node one by one starting from the head until the target value is found, and its time complexity is O(n) because we may need to examine all nodes.
Time Complexity Comparison
| Operation | Singly Linked List | Doubly Linked List | Circular Linked List | Explanation |
|---|---|---|---|---|
| Access (by index) | O(n) | O(n) | O(n) | Must traverse |
| Traversal | O(n) | O(n) | O(n) | Visit nodes |
| Search | O(n) | O(n) | O(n) | Sequential check |
| Insert at head | O(1) | O(1) | O(1) | Pointer update |
| Insert at tail | O(n) / O(1)* | O(1)* | O(1)* | With tail pointer |
| Delete at head | O(1) | O(1) | O(1) | Pointer update |
| Delete node | O(n) | O(1)** | O(n) | Need previous node |
* O(1) if tail pointer maintained.
** O(1) if node reference available.