Definition: What Is Linked List?
A Linked List is a linear data structure where elements (called nodes) are stored in non-contiguous memory locations. Each node contains data and a pointer/reference to the next node. Unlike arrays, linked lists don't require contiguous memory, allowing dynamic size and efficient insertions/deletions.
Linked list is like a chain: each link (node) is connected to the next link. You can only access nodes by following the chain from the head (first node). Linked lists are dynamic—they can grow or shrink as needed, unlike arrays which have fixed size (in most languages).
There are two main types: Singly Linked List (each node points to the next node only) and Doubly Linked List (each node points to both next and previous nodes). Linked lists are fundamental data structures used in many algorithms and real-world applications.
Key Point: Linked list is a linear data structure with nodes connected by pointers. Nodes stored in non-contiguous memory. Types: singly (one pointer) and doubly (two pointers). Dynamic size, efficient insertions/deletions, but no random access.
What: Singly vs Doubly Linked List
Understanding the difference between singly and doubly linked lists:
Real-Life Analogy: Train Cars
Linked list is like a train with connected cars:
Just like train cars, linked list nodes are connected and can be easily added or removed.
Singly Linked List
Each node has: data and one pointer to next node. Can traverse only forward (head to tail). Less memory (one pointer per node). Simpler implementation. Cannot traverse backward. Example: [1] → [2] → [3] → null. Head points to first node, last node points to null.
Example: [1] → [2] → [3] → null (forward traversal only)
Doubly Linked List
Each node has: data and two pointers (next and previous). Can traverse both forward and backward. More memory (two pointers per node). More complex implementation. Can traverse backward. Example: null ← [1] ↔ [2] ↔ [3] → null. Head and tail pointers for efficient access.
Example: null ← [1] ↔ [2] ↔ [3] → null (bidirectional traversal)
Singly vs Doubly Linked List Visualization
Singly Linked List
Forward traversal only: Head → Node → Node → null
Doubly Linked List
Bidirectional traversal: null ↔ Node ↔ Node ↔ null
Singly vs Doubly Linked List Comparison
| Feature | Singly Linked List | Doubly Linked List |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next, previous) |
| Memory usage | Less (one pointer) | More (two pointers) |
| Traversal | Forward only | Forward and backward |
| Delete node | Need previous node (O(n)) | Direct access (O(1)) |
| Complexity | Simpler | More complex |
| Use cases | Forward-only traversal, stacks | Bidirectional traversal, LRU cache |
Important: Singly linked list has one pointer (next), forward traversal only, less memory. Doubly linked list has two pointers (next, previous), bidirectional traversal, more memory but easier deletion. Choose based on traversal needs and memory constraints.
When: When to Use Linked List vs Array
When to use linked list vs array:
Use Linked List When:
- Dynamic size: Size changes frequently
- Frequent insertions/deletions: O(1) at head
- No random access needed: Sequential access is fine
- Memory fragmented: Non-contiguous memory OK
- Implementing stacks/queues: Natural fit
Use Array When:
- Random access needed: Access by index O(1)
- Fixed size known: Size doesn't change
- Cache locality important: Contiguous memory
- Memory efficient: No extra pointers
- Simple operations: Direct index access
Common Scenario: Use linked list for dynamic size, frequent insertions/deletions, and when random access isn't needed. Use array for random access, fixed size, and cache locality. Linked list is better for insertions/deletions, array is better for random access.
How To: Implement Linked List with Examples
Learn to implement linked list with examples:
Example 1: Singly Linked List Implementation
Basic singly linked list with insert and delete operations:
# Singly Linked List Implementation
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
# Insert at head (O(1))
def insert_at_head(self, val):
new_node = ListNode(val)
new_node.next = self.head
self.head = new_node
# Insert at tail (O(n))
def insert_at_tail(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
# Delete node (O(n) to find, O(1) to delete)
def delete_node(self, val):
if not self.head:
return
if self.head.val == val:
self.head = self.head.next
return
current = self.head
while current.next and current.next.val != val:
current = current.next
if current.next:
current.next = current.next.next
# Traverse (O(n))
def traverse(self):
current = self.head
while current:
print(current.val, end=" -> ")
current = current.next
print("null")
# Example usage
ll = SinglyLinkedList()
ll.insert_at_head(3)
ll.insert_at_head(2)
ll.insert_at_head(1)
ll.traverse() # Output: 1 -> 2 -> 3 -> nullExample 2: Doubly Linked List Implementation
Basic doubly linked list with bidirectional traversal:
# Doubly Linked List Implementation
class DoublyListNode:
def __init__(self, val=0, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# Insert at head (O(1))
def insert_at_head(self, val):
new_node = DoublyListNode(val)
if not self.head:
self.head = self.tail = new_node
return
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
# Insert at tail (O(1))
def insert_at_tail(self, val):
new_node = DoublyListNode(val)
if not self.tail:
self.head = self.tail = new_node
return
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
# Delete node (O(1) if have reference)
def delete_node(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
# Traverse forward (O(n))
def traverse_forward(self):
current = self.head
while current:
print(current.val, end=" <-> ")
current = current.next
print("null")
# Traverse backward (O(n))
def traverse_backward(self):
current = self.tail
while current:
print(current.val, end=" <-> ")
current = current.prev
print("null")
# Example usage
dll = DoublyLinkedList()
dll.insert_at_head(3)
dll.insert_at_head(2)
dll.insert_at_head(1)
dll.traverse_forward() # Output: 1 <-> 2 <-> 3 <-> null
dll.traverse_backward() # Output: 3 <-> 2 <-> 1 <-> nullBest Practice: Singly linked list: simpler, one pointer, forward traversal only. Doubly linked list: two pointers, bidirectional traversal, easier deletion. Use singly for forward-only needs, doubly for bidirectional needs. Both support O(1) insertion at head, O(n) search.
Why: Why Linked List Matters
Linked list matters for these reasons:
Dynamic Size
Linked list can grow or shrink dynamically as needed. No need to pre-allocate memory or resize like arrays. This makes linked lists flexible for applications where size is unknown or changes frequently. Memory is allocated only when needed.
Efficient Insertions/Deletions
Linked list provides O(1) insertion/deletion at head (singly) or both ends (doubly). No need to shift elements like arrays. This makes linked lists ideal for stacks, queues, and applications with frequent insertions/deletions.
Foundation for Other Structures
Linked list is the foundation for many other data structures: stacks, queues, graphs, trees. Understanding linked lists helps understand these more complex structures. Many algorithms use linked lists internally.
Interview Essential
Linked list is a common coding interview topic. Interviewers frequently ask about reversing linked lists, detecting cycles, finding middle, merging lists, and other linked list problems. Understanding linked lists is essential for technical interviews.
Important: Linked list matters because it provides dynamic size, efficient insertions/deletions, is the foundation for other structures, and is essential for interviews. Linked list is one of the most important data structures to understand.
Frequently Asked Questions
What is a linked list?
Linked list is a linear data structure where elements (nodes) are stored in non-contiguous memory locations. Each node contains data and a pointer/reference to the next node. Unlike arrays, linked lists don't require contiguous memory, allowing dynamic size and efficient insertions/deletions. Types: singly linked list (one pointer to next) and doubly linked list (pointers to next and previous).
What is the difference between singly and doubly linked list?
Singly linked list: each node has data and one pointer to next node. Can traverse only forward (head to tail). Doubly linked list: each node has data and two pointers (next and previous). Can traverse both forward and backward. Doubly linked list uses more memory (extra pointer) but allows bidirectional traversal and easier deletion.
When to use linked list vs array?
Use linked list when: need dynamic size, frequent insertions/deletions, don't need random access, memory is fragmented. Use array when: need random access by index, know size in advance, need cache locality, memory is contiguous. Linked list is better for insertions/deletions, array is better for random access.
What are the advantages of linked list?
Advantages: dynamic size (grows/shrinks as needed), efficient insertions/deletions (O(1) at head), no memory waste (only uses needed memory), easy to insert/delete in middle. Disadvantages: no random access (must traverse from head), extra memory for pointers, no cache locality, harder to reverse (singly).
What are common linked list operations?
Common operations: insert at head (O(1)), insert at tail (O(n) singly, O(1) doubly with tail pointer), delete node (O(n) to find, O(1) to delete), search (O(n)), traverse (O(n)), reverse (O(n)). Singly linked list: forward traversal only. Doubly linked list: forward and backward traversal.