Linked Lists — Dr. Vivek Kumar · Bennett University

The Building Block

What is a Node?

Every linked list is made of nodes. A node is a small structure with two parts: a data field that holds the actual value, and a pointer field (called NEXT) that holds the memory address of the next node. When there is no next node, NEXT holds NULL — a special value meaning "nothing follows."

A single node — the basic unit

42data

0x1Cnext

→

next node is at memory address 0x1C

The value 0x1C stored in the NEXT field is not an arrow — it is a real hexadecimal number sitting in memory. To reach the next node, the computer reads this number and jumps to that address. This is pointer traversal.

Key mental model: A linked list is not a chain of boxes drawn on paper. It is a set of nodes scattered anywhere in memory, connected only by the fact that each one stores the address of the next. Change the address value and you rewire the entire list instantly.

Four Types

Types of Linked Lists

1 · Singly Linked List

Each node has one pointer — NEXT — pointing forward. Traversal is one-directional only: you can move from HEAD toward NULL but never backwards. This is the simplest and most memory-efficient form.

HEAD

→

12data

0x08next

→

35data

0x14next

→

61data

NULLnext

→

NULL

2 fields per node · One-directional · Used in stacks, hash chaining, simple queues

2 · Doubly Linked List

Each node has two pointers — PREV pointing to the previous node and NEXT pointing to the next. Traversal works in both directions. Deletion is more efficient because you can reach the predecessor directly from the node being deleted.

NULL

↔

NULLprev

12data

0x10next

↔

0x04prev

35data

NULLnext

↔

NULL

3 fields per node · Bi-directional · Used in browser history, undo/redo, deques

3 · Circular Linked List

The last node's NEXT points back to the first node instead of NULL. There is no end — the list forms a loop. Every node can reach every other node by following pointers long enough. A TAIL pointer is usually maintained to allow O(1) insertion at the end.

HEAD

→

12data

→next

→

35data

→next

→

61data

↩ HEADnext

No NULL terminator · Loop structure · Used in round-robin CPU scheduling, playlist loops, token rings

4 · Sorted Linked List

Elements are always maintained in ascending order. Every insertion performs a traversal to find the correct position before wiring the new node in — keeping the list sorted at all times without a separate sorting step. Useful when data arrives in random order but must always be retrievable in sorted sequence.

HEAD

→

8data

→next

→

21data

→next

→

47data

→next

→

NULL

Always ordered · O(n) insert · Used as basis for priority queues implemented with linked lists

Core Operations

Traversal · Search · Insert · Delete · Reverse

Every operation on a linked list works by following pointers. The key skill is knowing which pointer to change, in which order. Getting the order wrong can permanently lose access to part of the list.

Traversal — Walk the list from HEAD to NULL

O(n)

curr = HEAD while curr ≠ NULL: visit(curr.data) // process this node curr = curr.next // follow the pointer

Start at HEAD. Read the data. Follow NEXT to the next node. Repeat until NEXT is NULL. Each step reads exactly one pointer — this is why traversal is O(n).

Search — Find a value by linear scan

O(n) worst

curr = HEAD while curr ≠ NULL: if curr.data == target: return curr // found curr = curr.next return NULL // not found

Unlike arrays, there is no index formula — you cannot jump to position i directly. Every search must start at HEAD and walk forward. Best case Ω(1) if target is at HEAD; worst case O(n) if absent or at the tail.

Insert — Add a node at any position

O(1) at front · O(n) at position

Insert at front (O(1)) — always 2 pointer changes:

newNode.next = HEAD.next // step 1: new node points to old first HEAD.next = newNode // step 2: HEAD now points to new node

Insert after a known node (O(1) once at position):

newNode.next = prev.next // step 1: link new node forward prev.next = newNode // step 2: link predecessor to new node

Order matters critically: If you do step 2 before step 1, you overwrite prev.next before saving it. The remainder of the list becomes permanently unreachable — a memory leak. Always wire the new node forward first, then update the predecessor.

Delete — Remove a node by relinking

O(n) find · O(1) unlink

curr = HEAD while curr.next ≠ target: curr = curr.next // find predecessor curr.next = target.next // skip over target free(target) // release memory

Deletion requires finding the node before the target — the predecessor — because you need to update its NEXT pointer. In a singly linked list this means an O(n) scan from HEAD. In a doubly linked list, the predecessor is already stored in the target node's PREV field, making the unlink itself O(1) — but finding the node still takes O(n) unless you already have a pointer to it.

Reverse — Flip all pointers in place

O(n) · O(1) space

prev = NULL curr = HEAD.next while curr ≠ NULL: next = curr.next // save next before overwriting curr.next = prev // reverse the link prev = curr // advance prev curr = next // advance curr HEAD.next = prev // HEAD now points to old tail

Three pointers — prev, curr, next — move through the list together. At each step, curr.next is flipped to point backward. After n steps, every pointer is reversed and HEAD is updated to the old tail. No extra data structure is needed — the reversal happens entirely in place.

Performance

Time Complexity Summary

Operation	Singly	Doubly	Notes
Access by index	O(n)	O(n)	Must traverse from HEAD — no formula
Search by value	O(n)	O(n)	Linear scan always
Insert at front	O(1)	O(1)	2 pointer changes only
Insert at end	O(n)*	O(n)*	O(1) if TAIL pointer maintained
Insert at position i	O(n)	O(n)	Traverse to position i−1 first
Delete at front	O(1)	O(1)	Update HEAD only
Delete by value	O(n)	O(n) find, O(1) unlink	Doubly skips predecessor scan
Reverse	O(n)	O(n)	All n pointers must flip

When linked lists win over arrays: When insertions and deletions at the front or middle happen frequently and the size changes dynamically at runtime. Examples include implementing stacks, queues, and adjacency lists for graphs — all of which insert and delete at known positions without needing random index access.

When linked lists lose to arrays: Any algorithm that needs to jump to a position by index — binary search, heap operations, matrix access — is severely penalised because each index access costs O(n). Cache performance is also poor: pointer chasing causes frequent cache misses because nodes are scattered in memory.

Real-World Use

Where Linked Lists Appear

🌐

Browser History

The back and forward buttons in a web browser are implemented using a doubly linked list. Each visited page is a node. The PREV pointer implements "back" and NEXT implements "forward." Navigating history is pure pointer following — no copying of page data.

↩️

Undo / Redo

Text editors maintain a doubly linked list of editing actions. Each action is a node. "Undo" follows PREV; "Redo" follows NEXT. Inserting a new action after an undo simply rewires the forward pointer — constant-time O(1) regardless of history length.

🖨️

Print Spooler Queue

A printer queue holds jobs as a singly linked list. New jobs are appended to the tail; the printer dequeues from the head. When a job is cancelled, it is unlinked from the middle of the list — two pointer changes, no shifting of other jobs.

🖥️

OS Memory Management

Operating systems track free memory blocks using a linked list of available segments. When a program requests memory, the OS traverses this list to find a suitable block and unlinks it. When memory is freed, the block is re-inserted — all via pointer operations.

🎵

Music Playlist

A playlist is a circular doubly linked list. Each song is a node with PREV and NEXT pointers. "Next track" follows NEXT; "Previous track" follows PREV. Looping the playlist is the circular structure — the last song's NEXT points back to the first.

📊

Hash Table Chaining

When two keys hash to the same index (a collision), most hash tables store all colliding entries as a singly linked list at that bucket. Searching for a key in a bucket is a linear scan of that list. This is the most common collision resolution strategy.

Interactive Learning

Node Forge — Build a Linked List

Node Forge lets you build linked lists from scratch — drag DATA and NEXT fields to forge a node, stamp nodes onto a canvas, wire them with pointer connections, then run search, insert, delete, and reverse operations. Work through all five stages to earn points.

Linked Lists — Connecting Data with Pointers