A linked list in data structure is your first step beyond arrays, and it shows up everywhere: university exams, placement tests and coding interviews (“reverse a linked list” is one of the most asked questions of all time). The idea is simple once you see it, so this guide is mostly about seeing it.
You'll play with a live linked list, compare it with arrays, step through the reverse algorithm, get clean code in Python, Java and C++, and lock it all in with a memory trick borrowed from Indian Railways.
What is a linked list?
An array keeps its items in one continuous block of memory, like seats in a single row. A linked list doesn't care where its items live. Each item is wrapped in a node with two parts:
- data: the value you're storing (a number, a name, a song).
- next: the address of the next node, or NULL if this is the last one.
You only need to remember one address: the head. From the head you can follow the pointers to every other node. That's the whole trick, and also the weakness: there's no shortcut to node number 500.
Try it: linked list playground
Insert and delete at both ends and search for a value. Watch how many nodes each operation has to visit.
🎮 Linked list playground
Try each button and watch the step count: some operations are instant, some must walk the list.
Types of linked lists
- Singly linked list: each node points only to the next. Simple and light. You can only move forward.
- Doubly linked list: each node has
nextandprev. You can move both ways and delete a node in O(1) when you have it, at the cost of one extra pointer per node. Browser history and LRU caches use this. - Circular linked list: the last node points back to the head instead of NULL. Handy for things that repeat in a loop, like round-robin CPU scheduling or a music playlist on repeat.
Array vs linked list
This comparison is a favourite exam question. The short version: arrays are fast to read, linked lists are fast to change.
| Feature | Array | Linked list |
|---|---|---|
| Memory layout | Side by side (contiguous) | Scattered, joined by pointers |
| Access k-th item | O(1): jump to index | O(n): walk from head |
| Insert / delete at start | O(n): shift everything | O(1): move one pointer |
| Insert / delete in middle | O(n): shift | O(1) once you're at the node (finding it is O(n)) |
| Size | Fixed (or costly resize) | Grows and shrinks freely |
| Extra memory | None per item | One pointer per node (two if doubly) |
| Cache friendly? | Yes, very | No, nodes are scattered |
| Binary search? | Yes, if sorted | Not useful |
🧠 PATH memory card
Remember linked lists for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
An Indian train: the engine is the HEAD, every coach is coupled only to the one behind it, and the last coach carries the yellow X board that says “the train ends here”.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Coaches Couple, No Jumping”
- Coaches→Nodes: each holds data (passengers)
- Couple→Each node links to the next with a pointer
- Engine→HEAD: the only entry point you store
- X board→The tail's next is NULL
- No Jumping→No index access: reaching k-th node is O(n)
- Add a coach at the front→Insert at head is O(1)
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Start with 12 → 7 → 31 → NULL. Insert 5 at the head: 5.next = 12, head = 5, giving 5 → 12 → 7 → 31 (1 step). Now find 31: visit 5, 12, 7, 31 (4 steps). Say it once: “adding at the front is instant, finding is a walk.” - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Linked list operations and time complexity
| Operation | Time | Why |
|---|---|---|
| Access / search | O(n) | Must walk from the head |
| Insert at head | O(1) | New node → old head, move head |
| Insert at tail | O(n) · O(1) with tail pointer | Walk to the end, or keep a tail |
| Delete head | O(1) | head = head.next |
| Delete a value | O(n) | Find it, then relink prev.next |
| Reverse | O(n) time, O(1) space | Flip each arrow once |
If the O(1) and O(n) notation feels shaky, take five minutes with Big O notation explained first.
Linked list implementation (Python, Java, C++)
One small, complete program per language: a node, insert at head and tail, delete by value, reverse and print.
class Node:
def __init__(self, data):
self.data = data
self.next = None # pointer to the next node
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data): # O(1)
node = Node(data)
node.next = self.head
self.head = node
def insert_at_tail(self, data): # O(n)
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, key): # O(n)
curr, prev = self.head, None
while curr and curr.data != key:
prev, curr = curr, curr.next
if not curr:
return # not found
if prev:
prev.next = curr.next
else:
self.head = curr.next # deleting the head
def reverse(self): # O(n) time, O(1) space
prev, curr = None, self.head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
self.head = prev
def __str__(self):
out, curr = [], self.head
while curr:
out.append(str(curr.data))
curr = curr.next
return " -> ".join(out) + " -> None"
ll = LinkedList()
for x in (7, 31, 5):
ll.insert_at_tail(x)
ll.insert_at_head(12)
print(ll) # 12 -> 7 -> 31 -> 5 -> None
ll.reverse()
print(ll) # 5 -> 31 -> 7 -> 12 -> NoneInterview classic: reverse a linked list
You walk the list once with three pointers. prev starts at NULL, curr at the head. At each step, save next, turn curr's arrow back to prev, then move both forward. Step through it:
🔁 Reverse a linked list, step by step
Reversed part (new list)
HEAD → NULL (the list is empty)
Still to reverse
Step 0 of 5. Start: prev = NULL, curr = head. We'll flip one arrow at a time.
More linked list interview questions
- Find the middle node: slow pointer moves 1, fast moves 2. When fast reaches the end, slow is in the middle.
- Detect a cycle: the same slow/fast idea (Floyd's algorithm). If they ever meet, there's a loop.
- Merge two sorted lists: compare the two heads, attach the smaller one, move on. O(n + m).
- Remove the n-th node from the end: move one pointer n steps ahead, then move both until the first hits the end.
What to learn next
Stacks and queues are often built on top of linked lists: push and pop at the head are both O(1). That's the next part of the course: stack vs queue. After that, linked lists come back in hashing to solve collisions.
Key takeaways
- ✓A linked list is a chain of nodes; each node stores data and a pointer to the next node.
- ✓You keep only the head. The tail's next pointer is NULL.
- ✓Insert or delete at the head is O(1); search and access by position are O(n).
- ✓Arrays are fast to read; linked lists are fast to change at a known spot.
- ✓Singly (next), doubly (next + prev), circular (tail points back to head).
- ✓Remember it with “Coaches Couple, No Jumping.”
Frequently asked questions
What is a linked list in data structure?
A linked list is a linear data structure made of nodes. Each node stores a value and a pointer (reference) to the next node. The nodes can live anywhere in memory; the pointers chain them together. The first node is called the head and the last node points to NULL.
What is the difference between an array and a linked list?
An array stores items side by side in memory, so you can jump to any index in O(1), but inserting or deleting in the middle shifts elements (O(n)). A linked list stores nodes anywhere and links them with pointers, so inserting or deleting at a known node is O(1), but reaching the k-th item means walking from the head (O(n)).
What are the types of linked lists?
Singly linked list (each node points to the next), doubly linked list (each node points to the next and the previous), and circular linked list (the last node points back to the first instead of NULL). A circular list can be singly or doubly linked.
What is the time complexity of linked list operations?
Insert or delete at the head: O(1). Insert at the tail: O(n), or O(1) if you keep a tail pointer. Search or access by position: O(n). Delete a node when you already have a pointer to the previous node: O(1).
Where are linked lists used in real life?
Music playlists with next and previous, the browser's back and forward history (doubly linked), undo in editors, LRU caches (a hash map plus a doubly linked list), and as the building block for stacks, queues and adjacency lists in graphs.
🧠 Quick check: linked lists
1. What does the last node of a singly linked list point to?
2. Which operation is O(1) in a singly linked list but O(n) in an array?
3. Why is binary search a bad idea on a linked list?
4. In “Coaches Couple, No Jumping”, what does the yellow X board on the last coach stand for?
Checking your access…