Beginner·1 min read
Singly Linked Lists
Understand node-based memory allocation and implement core linked list operations.
Singly Linked Lists
A linked list is a chain of nodes where each node points to the next.
``
[Data|Next] → [Data|Next] → [Data|Next] → NULL
Node 1 Node 2 Node 3
`
Array vs Linked List
Header Feature Array Linked List
Header Memory Contiguous Scattered Access O(1) by index O(n) traversal Insert at head O(n) shift O(1) Insert at tail O(1) amortized O(n)* or O(1) with tail ptr Memory waste Pre-allocated None (per node)
Core Operations
Traversal: Walk from head to NULL, visiting each node.
Insertion at head:
`
Before: A → B → C → NULL
Insert X at head:
X → A → B → C → NULL
`
Deletion of node with value V:
`
Before: A → B → C → D → NULL, delete B
Find prev of B (which is A)
A → C → D → NULL
``
Key Insight
Linked lists excel at frequent insertions/deletions at the head and when you don't need random access. They're the building block for stacks, queues, and hash table chaining.
Code Example
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def push_front(self, data):
node = Node(data)
node.next = self.head
self.head = node
def push_back(self, data):
node = Node(data)
if not self.head:
self.head = node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
def delete(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
return
curr = self.head
while curr.next:
if curr.next.data == data:
curr.next = curr.next.next
return
curr = curr.next
def search(self, data):
curr = self.head
idx = 0
while curr:
if curr.data == data:
return idx
curr = curr.next
idx += 1
return -1
def display(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
return " → ".join(elements) + " → NULL"
ll = SinglyLinkedList()
for v in [10, 20, 30, 40]:
ll.push_back(v)
print(ll.display())
ll.push_front(5)
print(ll.display())
ll.delete(20)
print(ll.display())
print(f"Found 30 at: {ll.search(30)}")Practice Problems
- 01Reverse a singly linked list iteratively and recursively
- 02Find the middle element of a linked list in one pass
- 03Detect if a linked list has a cycle (Floyd's algorithm)