Linked List Basics
What Is a Linked List?
A linked list is a data structure where elements — called nodes — are stored in memory and connected to each other through pointers. Unlike an array, the nodes do not need to be adjacent in memory. Each node knows where the next node is because it stores a direct reference to it.
Think of it like a scavenger hunt where each clue tells you where the next clue is hidden. You cannot jump to clue 5 directly — you have to follow the chain from clue 1 to 2 to 3 to 4 to 5.
Linked list of three integers: 10 → 20 → 30 Node 1 Node 2 Node 3 ┌──────┬──────┐ ┌──────┬──────┐ ┌──────┬──────┐ │ 10 │ ●───┼──▶│ 20 │ ●───┼──▶│ 30 │ null │ └──────┴──────┘ └──────┴──────┘ └──────┴──────┘ data next data next data next ● = pointer (memory address of the next node) null = no next node — this is the end of the list
The first node is called the head. The last node's next pointer is null (or None in Python, nullptr in C++) — this signals the end of the list.
What Is a Node?
A node is the fundamental building block of a linked list. Every node contains exactly two things:
- ›Data — the value stored at this position (an integer, string, object, etc.)
- ›Next pointer — the memory address of the next node in the list
Node structure: ┌──────────┬──────────┐ │ data │ next │ └──────────┴──────────┘ data: the value (10, "alice", any type) next: address of the next node, or null if this is the last node
This is the key difference from an array. An array element only stores its value — the position comes from the index. A linked list node stores both its value and an explicit pointer to the next element.
1public class LinkedListNode {
2
3 // A node in a singly linked list
4 static class Node {
5 int data; // The value stored in this node
6 Node next; // Reference to the next node (null if last)
7
8 Node(int data) {
9 this.data = data;
10 this.next = null; // New nodes start with no next
11 }
12 }
13
14 public static void main(String[] args) {
15 // Create individual nodes
16 Node first = new Node(10);
17 Node second = new Node(20);
18 Node third = new Node(30);
19
20 // Link them together manually
21 first.next = second; // 10 → 20
22 second.next = third; // 20 → 30
23 // third.next is already null → 30 is the last node
24
25 // Traverse: follow next pointers until null
26 Node current = first;
27 while (current != null) {
28 System.out.print(current.data + " → ");
29 current = current.next;
30 }
31 System.out.println("null");
32
33 // Access: head is first, tail is third
34 System.out.println("Head: " + first.data); // 10
35 System.out.println("Tail: " + third.data); // 30
36 System.out.println("Tail.next: " + third.next); // null
37 }
38}Output:
10 → 20 → 30 → null
Head: 10
Tail: 30
Tail.next: null
Key Vocabulary
Before going further, these are the terms every linked list discussion uses:
Head The first node in the list. The entry point — all traversal starts here. The list itself is represented by a reference to its head. If head is null/None/nullptr, the list is empty. Tail The last node in the list. Its next pointer is null — signals the end. Some implementations maintain a tail pointer for O(1) append. Node A single element: (data, next). The building block of the list. Pointer / Reference / Link The "next" field inside a node. Stores the memory address of the next node. Following a pointer means reading what it points to. Null / None / nullptr A pointer to nothing — the absence of a node. tail.next == null means "no more nodes after this." Length / Size The number of nodes in the list. No built-in field — must be counted by traversal (O(n)) or tracked by the list as a maintained counter.
Why Linked Lists Exist — The Array Problem
Arrays are stored in contiguous memory. Every element sits right next to the previous one. This is excellent for O(1) index access but creates one expensive operation: insertion and deletion in the middle.
When you insert at position k in an array, every element from k onward must shift one slot right. For n elements, that is up to n shifts — O(n).
Insert 15 at index 1 in array [10, 20, 30, 40]:
Before: [10, 20, 30, 40]
Shift: ↓ ↓ ↓ ↓
10 → → →
After: [10, 15, 20, 30, 40]
↑ ↑ ↑
shifted right
Cost: 3 shifts for a 4-element array
Cost grows with n
Linked lists solve this differently. Insertion at any position only requires changing two pointers — the new node's next pointer and the previous node's next pointer. No elements shift. No reallocation. O(1) insert at a known position.
Insert 15 after node containing 10 in: 10 → 20 → 30 Step 1: Create new node 15 new.next = 10.next (point new node to 20) Step 2: Redirect previous node 10.next = new (point 10 to the new node) Before: 10 → 20 → 30 After: 10 → 15 → 20 → 30 Cost: 2 pointer updates, regardless of list length
This is the fundamental tradeoff: arrays win on access, linked lists win on structural modification.
Linked List vs Array — The Core Tradeoff
Operation Array Linked List ───────────────────────────────────────────────── Access by index O(1) O(n) Search by value O(n) O(n) Insert at beginning O(n) shift O(1) Insert at end O(1) amort. O(1) with tail pointer Insert at middle O(n) shift O(1) if node is known* Delete at beginning O(n) shift O(1) Delete at end O(1) O(n) singly linked† Delete at middle O(n) shift O(1) if node is known* Memory layout Contiguous Scattered Extra memory per elem None 1 pointer (singly), 2 (doubly) Cache performance Excellent Poor (pointer chasing) * "Known" means you already hold a reference to the node. If you must search first, add O(n) for the search. † Singly linked lists cannot go backward — to delete the last node, you must traverse to find the second-to-last node: O(n). Doubly linked lists fix this with a prev pointer: O(1) with tail.
The "O(1) insert if node is known" caveat is critical. It means: given a pointer to the node BEFORE where you want to insert, the insert itself is O(1). Finding that node first costs O(n). In practice, linked lists shine when you already have a pointer to the relevant position — e.g., iterating and modifying as you go.
Memory Layout: Why Access Is O(n)
Arrays store elements consecutively — index access computes an address directly (base + index × size). The CPU can jump to any element in one step.
Linked list nodes are scattered across the heap wherever memory is available at the time of allocation. To reach node k, you must follow k pointers one at a time starting from the head.
Array [10, 20, 30] in memory — contiguous:
Address: 1000 1004 1008
Value: 10 20 30
arr[2] → address 1000 + (2 × 4) = 1008 → value 30 (one step)
Linked list 10 → 20 → 30 in memory — scattered:
Node 10 at address 1000: {data=10, next=2048}
Node 20 at address 2048: {data=20, next=3120}
Node 30 at address 3120: {data=30, next=null}
To reach 30: follow 1000 → 2048 → 3120 (three steps — O(n))
This scattered layout also hurts cache performance. Arrays benefit from cache locality — when the CPU loads one element, it loads surrounding elements into the cache too. Linked list pointer chasing jumps to random addresses, causing cache misses at every node.
Types of Linked Lists
There are three main variants, each with different structural properties:
Singly Linked List Each node has one pointer: next Traversal: forward only 10 → 20 → 30 → null Most common — simple and memory-efficient Doubly Linked List Each node has two pointers: prev and next Traversal: forward and backward null ← 10 ↔ 20 ↔ 30 → null Used when backward traversal or O(1) delete of known node matters Circular Linked List The tail's next points back to the head (or to any node) No null terminator — the list forms a loop 10 → 20 → 30 → (back to 10) Used for round-robin scheduling, cycling buffers
Each variant is covered in its own dedicated topic. The node structure and core operations build on the same foundation — this page.
How Linked Lists Are Used in Practice
Linked lists are the underlying data structure behind several higher-level abstractions:
Stack (LIFO): Push = insert at head (O(1)) Pop = delete at head (O(1)) No shifting — linked list is a natural fit Queue (FIFO): Enqueue = insert at tail (O(1) with tail pointer) Dequeue = delete at head (O(1)) Again, no shifting — better than array for FIFO HashMap (collision chaining): Each hash bucket is a linked list of entries with the same hash Insert/delete in a chain is O(1) once the slot is found LRU Cache: Doubly linked list + hash map Move recently accessed node to head in O(1) Evict least-recently-used node from tail in O(1) Operating System: Process scheduling uses circular linked lists (round-robin) Memory free lists are singly linked lists of free blocks
When to Use a Linked List vs an Array
Prefer Linked List when: - Frequent insertions or deletions at the front - Frequent insertions or deletions in the middle while iterating - Size is unknown and changes frequently - You do not need random access by index - Implementing a queue, stack, or LRU cache Prefer Array when: - Frequent access by index (arrays are O(1), lists are O(n)) - Cache performance matters (arrays are cache-friendly) - Memory overhead matters (arrays have zero pointer overhead) - The size is fixed or known in advance - Sorting is needed (most sort algorithms work better on arrays) In interview problems: Linked list problems typically give you the head node. The problem is usually about manipulation, not counting or indexing. Pattern signals: reverse, detect cycle, find middle, merge, remove nth node.
Interview Questions
Q: What is the difference between a linked list and an array at the memory level?
Arrays store elements in a single contiguous block of memory. Index access uses the formula base + index × element_size — one arithmetic step, O(1). Linked list nodes are allocated individually and can be anywhere in the heap. Accessing node k requires following k pointers from the head — O(k) steps in the worst case. The scattered memory layout also hurts CPU cache performance since each pointer dereference may point to a different cache line.
Q: If linked list insertion at a known position is O(1), why is it often described as O(n)?
The O(1) for insertion assumes you already hold a reference to the node before the insertion point. In practice, you first need to find that position, which requires traversing from the head — O(n). The two costs are: O(n) to find the position + O(1) to do the actual insertion. The combined complexity is O(n). If you are already iterating and inserting as you go, you have the position for free and insertion is truly O(1) per operation.
Q: What is the head of a linked list and what does it mean when head is null?
The head is the first node in the list — the entry point for all operations. The list itself is typically represented by a reference to its head node. When head == null, the list is empty — it contains zero nodes. Any traversal immediately terminates, and any operation that tries to read head.data or head.next on a null head will throw a NullPointerException (Java), AttributeError (Python), or segfault (C++). Always check for an empty list before accessing head.
Q: Why does a singly linked list take O(n) to delete the last node?
Because singly linked list nodes only have a next pointer — there is no way to go backward. To delete the tail, you need to set the second-to-last node's next to null. But the only way to find the second-to-last node is to start at the head and traverse until you reach the node whose next.next is null. This traversal is O(n). Doubly linked lists solve this by adding a prev pointer — with a tail reference and prev, deleting the last node is O(1).
FAQs
Can a linked list store elements of different types?
In statically typed languages (Java, C++), each linked list is typed — all nodes store the same type. You can use generics or templates to make the node type flexible, but all nodes in one list must be the same declared type. In dynamically typed languages (Python, JavaScript), nodes can hold any value — mixing types in one list is possible, though usually a sign of poor design.
What happens if you lose the head reference?
The entire list becomes inaccessible — a memory leak in languages without garbage collection (C++). In Java and Python, the garbage collector will eventually reclaim the memory, but the data is gone. This is why you must be careful when reassigning the head pointer during operations like reversal — always save the new head before unlinking the old one.
How is a linked list different from a tree?
A tree node can have multiple children — a linked list node has at most one next pointer (two for doubly linked). Trees form hierarchical structures with branching; linked lists form linear sequences. A singly linked list can be seen as a degenerate tree where every node has exactly one child. Trees support hierarchical queries (subtree operations, ancestor checks) that have no meaning in a linear list.
Does Python have a built-in linked list?
No. Python's list is a dynamic array — not a linked list. For a doubly linked list with O(1) append/prepend, use collections.deque. For general linked list problems in interviews, you implement the Node class from scratch as shown in this topic.
Quick Quiz
Question 1: What two pieces of information does every singly linked list node store?
- ›A) Index and value
- ›B) Value and a pointer to the next node
- ›C) Key and value
- ›D) Value and the length of the list
Answer: B) Value and a pointer to the next node. A singly linked list node stores its data (the value) and a next pointer (the memory address of the next node, or null if it is the last). Unlike arrays, there is no index — the position is implicit from how many pointer hops you take from the head.
Question 2: What is the time complexity of accessing the kth element in a linked list?
- ›A) O(1) — same as array
- ›B) O(log k) — binary search
- ›C) O(k) — must follow k pointers from head
- ›D) O(n) — must traverse the entire list
Answer: C/D) O(k), which is O(n) in the worst case. To reach node k, you follow k next pointers starting from the head. In the best case (k=0, the head), it is O(1). In the worst case (k = n-1, the last node), it is O(n). This is why accessing linked list elements by position is described as O(n).
Question 3: You want to insert a new element between nodes A and B in a singly linked list, and you already have a pointer to A. How many pointer updates are required?
- ›A) 0 — no updates needed
- ›B) 1 — update only the new node's next
- ›C) 2 — set new.next = B, then set A.next = new
- ›D) n — must shift all subsequent elements
Answer: C) 2 pointer updates. Set the new node's next to B (the node after A), then set A's next to the new node. No elements shift. The order matters — always link the new node forward first before relinking the previous node, to avoid losing the reference to B.
Question 4: What does head == null indicate about a linked list?
- ›A) The list has one element
- ›B) The list is empty — it contains zero nodes
- ›C) The head node's data is null
- ›D) The list has lost its tail pointer
Answer: B) The list is empty. head == null means there is no first node — the list contains nothing. All traversal loops should check head != null before starting. All operations that access head.data or head.next must guard against null head first.
Summary
A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. The list is represented by a reference to its head — the first node. The tail node's next pointer is null, marking the end.
The key ideas to carry forward:
- ›Node = data + next pointer — the fundamental building block
- ›Head = entry point, tail.next = null = end marker
- ›Access is O(n) — must traverse from head, following pointers
- ›Insert/delete at a known position is O(1) — two pointer updates, no shifting
- ›Insert/delete at an unknown position is O(n) — O(n) to find it + O(1) to do it
- ›Arrays win on access (O(1) vs O(n)); linked lists win on front/middle insert-delete (O(1) vs O(n))
- ›Nodes are heap-allocated and scattered — poor cache locality compared to arrays
- ›Singly linked list → forward only; doubly linked → bidirectional; circular → loop structure
In the next topic, you will explore the Singly Linked List — complete implementation of the foundational variant with all operations, edge cases, and the pointer manipulation patterns that appear in every linked list interview problem.