A linked list is a linear collection whose elements are not stored next to each other in memory: every node holds a value and a pointer to the next node. Insertion and deletion at a known position are O(1), at the price of O(n) access by index.
head
↓
┌──────┬──────┐ ┌──────┬──────┐ ┌──────┬──────┐
│ 10 │ ●───┼───▶│ 20 │ ●───┼───▶│ 30 │ ∅ │
└──────┴──────┘ └──────┴──────┘ └──────┴──────┘
data next data next data next = None (end of list)Structure of a node
A node is a tiny object (or struct) with two fields. Nodes are allocated one at a time, so the list grows and shrinks without ever copying or resizing an array. Traversal starts at the head and follows next until it becomes None.
class Node:
def __init__(self, data):
self.data = data
self.next = None # no next node yet
def show(head):
parts = []
curr = head
while curr is not None: # traversal: follow next until the end
parts.append(str(curr.data))
curr = curr.next
print(" -> ".join(parts))
def length(head):
n, curr = 0, head
while curr:
n += 1
curr = curr.next
return n
head = Node(10) # build by hand: 10 -> 20 -> 30
head.next = Node(20)
head.next.next = Node(30)
show(head)
print("length:", length(head))#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {} // no next node yet
};
void show(Node* head) {
for (Node* curr = head; curr; curr = curr->next) { // traversal: follow next until null
cout << curr->data;
if (curr->next) cout << " -> ";
}
cout << "\n";
}
int length(Node* head) {
int n = 0;
for (Node* curr = head; curr; curr = curr->next) n++;
return n;
}
int main() {
Node* head = new Node(10); // build by hand: 10 -> 20 -> 30
head->next = new Node(20);
head->next->next = new Node(30);
show(head);
cout << "length: " << length(head) << "\n";
}public class Main {
static class Node {
int data; Node next; // next stays null until linked
Node(int d) { data = d; }
}
static void show(Node head) {
StringBuilder sb = new StringBuilder();
for (Node curr = head; curr != null; curr = curr.next) { // traversal
sb.append(curr.data);
if (curr.next != null) sb.append(" -> ");
}
System.out.println(sb);
}
static int length(Node head) {
int n = 0;
for (Node curr = head; curr != null; curr = curr.next) n++;
return n;
}
public static void main(String[] args) {
Node head = new Node(10); // build by hand: 10 -> 20 -> 30
head.next = new Node(20);
head.next.next = new Node(30);
show(head);
System.out.println("length: " + length(head));
}
}class Node {
constructor(data) { this.data = data; this.next = null; } // no next node yet
}
function show(head) {
const parts = [];
for (let curr = head; curr !== null; curr = curr.next) // traversal
parts.push(curr.data);
console.log(parts.join(" -> "));
}
function length(head) {
let n = 0;
for (let curr = head; curr !== null; curr = curr.next) n++;
return n;
}
const head = new Node(10); // build by hand: 10 -> 20 -> 30
head.next = new Node(20);
head.next.next = new Node(30);
show(head);
console.log("length:", length(head));10 -> 20 -> 30
length: 3Time O(n) traversal · Space O(n) for n nodes
Why — and why not — a linked list
Linked lists are the building block of other structures: stacks and queues (O(1) at the ends), hash-table chains, adjacency lists in graphs, and the LRU cache (a doubly linked list plus a hash map).
Operations and their cost
| Operation | Time | Why |
|---|---|---|
| Insert at beginning | O(1) | New node points at the old head; the head reference moves. No traversal. |
| Insert at end | O(n) — O(1) with a tail pointer | Without a tail you must walk to the last node first. |
| Delete head | O(1) | Head moves to head.next. |
| Delete last | O(n) | Need the second-to-last node to clear its next; a singly linked list cannot go backwards. |
| Insert / delete after a given node | O(1) | Only pointers of the given node and its neighbour change. |
| Search | O(n) | Sequential scan; nothing better is possible without random access. |
| Access by index | O(n) | Walk i links. |
Insert at the beginning
before: head ──▶ [20] ──▶ [30] ──▶ ∅
step 1: new = [10] new.next = head [10] ──▶ [20] ──▶ [30] ──▶ ∅
step 2: head = new head ──▶ [10] ──▶ [20] ──▶ [30] ──▶ ∅class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head # new node points at the old head
return new_node # it is the new head — caller must store it
def show(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
print(" -> ".join(parts))
head = None
for x in (30, 20, 10): # insert in reverse to get 10 -> 20 -> 30
head = insert_at_beginning(head, x)
show(head)#include <iostream>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* insertAtBeginning(Node* head, int data) {
Node* newNode = new Node(data);
newNode->next = head; // new node points at the old head
return newNode; // it is the new head — caller must store it
}
void show(Node* head) {
for (; head; head = head->next) cout << head->data << (head->next ? " -> " : "\n");
}
int main() {
Node* head = nullptr;
for (int x : {30, 20, 10}) { // insert in reverse to get 10 -> 20 -> 30
head = insertAtBeginning(head, x);
show(head);
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node insertAtBeginning(Node head, int data) {
Node newNode = new Node(data);
newNode.next = head; // new node points at the old head
return newNode; // it is the new head — caller must store it
}
static void show(Node head) {
StringBuilder sb = new StringBuilder();
for (; head != null; head = head.next) sb.append(head.data).append(head.next != null ? " -> " : "");
System.out.println(sb);
}
public static void main(String[] args) {
Node head = null;
for (int x : new int[]{30, 20, 10}) { // insert in reverse to get 10 -> 20 -> 30
head = insertAtBeginning(head, x);
show(head);
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function insertAtBeginning(head, data) {
const newNode = new Node(data);
newNode.next = head; // new node points at the old head
return newNode; // it is the new head — caller must store it
}
function show(head) {
const parts = [];
for (; head !== null; head = head.next) parts.push(head.data);
console.log(parts.join(" -> "));
}
let head = null;
for (const x of [30, 20, 10]) { // insert in reverse to get 10 -> 20 -> 30
head = insertAtBeginning(head, x);
show(head);
}30
20 -> 30
10 -> 20 -> 30Time O(1) · Space O(1)
Insert at the end
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_end(head, data):
new_node = Node(data)
if head is None: # empty list: the new node is the head
return new_node
current = head
while current.next is not None: # O(n) walk to the last node
current = current.next
current.next = new_node
return head # head is unchanged
def show(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
print(" -> ".join(parts))
head = None
for x in (10, 20, 30):
head = insert_at_end(head, x)
show(head)#include <iostream>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* insertAtEnd(Node* head, int data) {
Node* newNode = new Node(data);
if (!head) return newNode; // empty list: the new node is the head
Node* current = head;
while (current->next) current = current->next; // O(n) walk to the last node
current->next = newNode;
return head; // head is unchanged
}
void show(Node* head) {
for (; head; head = head->next) cout << head->data << (head->next ? " -> " : "\n");
}
int main() {
Node* head = nullptr;
for (int x : {10, 20, 30}) {
head = insertAtEnd(head, x);
show(head);
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node insertAtEnd(Node head, int data) {
Node newNode = new Node(data);
if (head == null) return newNode; // empty list: the new node is the head
Node current = head;
while (current.next != null) current = current.next; // O(n) walk to the last node
current.next = newNode;
return head; // head is unchanged
}
static void show(Node head) {
StringBuilder sb = new StringBuilder();
for (; head != null; head = head.next) sb.append(head.data).append(head.next != null ? " -> " : "");
System.out.println(sb);
}
public static void main(String[] args) {
Node head = null;
for (int x : new int[]{10, 20, 30}) {
head = insertAtEnd(head, x);
show(head);
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function insertAtEnd(head, data) {
const newNode = new Node(data);
if (head === null) return newNode; // empty list: the new node is the head
let current = head;
while (current.next !== null) current = current.next; // O(n) walk to the last node
current.next = newNode;
return head; // head is unchanged
}
function show(head) {
const parts = [];
for (; head !== null; head = head.next) parts.push(head.data);
console.log(parts.join(" -> "));
}
let head = null;
for (const x of [10, 20, 30]) {
head = insertAtEnd(head, x);
show(head);
}10
10 -> 20
10 -> 20 -> 30Time O(n) — O(1) with a tail pointer · Space O(1)
Delete the head
class Node:
def __init__(self, data):
self.data = data
self.next = None
def delete_head(head):
if head is None:
return None # nothing to delete
return head.next # the old head is garbage-collected
def show(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
print(" -> ".join(parts) if parts else "empty")
head = Node(10); head.next = Node(20); head.next.next = Node(30)
show(head)
for _ in range(4):
head = delete_head(head)
print("after delete head: ", end="")
show(head)#include <iostream>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* deleteHead(Node* head) {
if (!head) return nullptr; // nothing to delete
Node* next = head->next;
delete head; // free the old head
return next;
}
void show(Node* head) {
if (!head) { cout << "empty\n"; return; }
for (; head; head = head->next) cout << head->data << (head->next ? " -> " : "\n");
}
int main() {
Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30);
show(head);
for (int i = 0; i < 4; i++) {
head = deleteHead(head);
cout << "after delete head: ";
show(head);
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node deleteHead(Node head) {
if (head == null) return null; // nothing to delete
return head.next; // the old head is garbage-collected
}
static void show(Node head) {
if (head == null) { System.out.println("empty"); return; }
StringBuilder sb = new StringBuilder();
for (; head != null; head = head.next) sb.append(head.data).append(head.next != null ? " -> " : "");
System.out.println(sb);
}
public static void main(String[] args) {
Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
show(head);
for (int i = 0; i < 4; i++) {
head = deleteHead(head);
System.out.print("after delete head: ");
show(head);
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function deleteHead(head) {
if (head === null) return null; // nothing to delete
return head.next; // the old head is garbage-collected
}
function show(head) {
const parts = [];
for (; head !== null; head = head.next) parts.push(head.data);
console.log(parts.length ? parts.join(" -> ") : "empty");
}
let head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
show(head);
for (let i = 0; i < 4; i++) {
head = deleteHead(head);
process.stdout.write("after delete head: ");
show(head);
}10 -> 20 -> 30
after delete head: 20 -> 30
after delete head: 30
after delete head: empty
after delete head: emptyTime O(1) · Space O(1)
Delete the last node
class Node:
def __init__(self, data):
self.data = data
self.next = None
def delete_last(head):
if head is None or head.next is None:
return None # 0 or 1 node → empty list
current = head
while current.next.next is not None: # stop at the second-to-last node
current = current.next
current.next = None
return head
def show(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
print(" -> ".join(parts) if parts else "empty")
head = Node(10); head.next = Node(20); head.next.next = Node(30)
show(head)
for _ in range(3):
head = delete_last(head)
print("after delete last: ", end="")
show(head)#include <iostream>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* deleteLast(Node* head) {
if (!head || !head->next) { delete head; return nullptr; } // 0 or 1 node → empty list
Node* current = head;
while (current->next->next) current = current->next; // stop at the second-to-last node
delete current->next;
current->next = nullptr;
return head;
}
void show(Node* head) {
if (!head) { cout << "empty\n"; return; }
for (; head; head = head->next) cout << head->data << (head->next ? " -> " : "\n");
}
int main() {
Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30);
show(head);
for (int i = 0; i < 3; i++) {
head = deleteLast(head);
cout << "after delete last: ";
show(head);
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node deleteLast(Node head) {
if (head == null || head.next == null) return null; // 0 or 1 node → empty list
Node current = head;
while (current.next.next != null) current = current.next; // stop at the second-to-last node
current.next = null;
return head;
}
static void show(Node head) {
if (head == null) { System.out.println("empty"); return; }
StringBuilder sb = new StringBuilder();
for (; head != null; head = head.next) sb.append(head.data).append(head.next != null ? " -> " : "");
System.out.println(sb);
}
public static void main(String[] args) {
Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
show(head);
for (int i = 0; i < 3; i++) {
head = deleteLast(head);
System.out.print("after delete last: ");
show(head);
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function deleteLast(head) {
if (head === null || head.next === null) return null; // 0 or 1 node → empty list
let current = head;
while (current.next.next !== null) current = current.next; // stop at the second-to-last node
current.next = null;
return head;
}
function show(head) {
const parts = [];
for (; head !== null; head = head.next) parts.push(head.data);
console.log(parts.length ? parts.join(" -> ") : "empty");
}
let head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
show(head);
for (let i = 0; i < 3; i++) {
head = deleteLast(head);
process.stdout.write("after delete last: ");
show(head);
}10 -> 20 -> 30
after delete last: 10 -> 20
after delete last: 10
after delete last: emptyTime O(n) · Space O(1)
Search in a linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
def search_list(head, target):
current, position = head, 1
while current is not None:
if current.data == target:
return position
current = current.next
position += 1
return -1 # fell off the end
def report(head, x):
pos = search_list(head, x)
print(f"search {x}:", f"position {pos}" if pos != -1 else -1)
head = Node(10); head.next = Node(20); head.next.next = Node(30)
for x in (20, 10, 40):
report(head, x)#include <iostream>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
int searchList(Node* head, int target) {
int position = 1;
for (Node* current = head; current; current = current->next, position++)
if (current->data == target) return position;
return -1; // fell off the end
}
void report(Node* head, int x) {
int pos = searchList(head, x);
cout << "search " << x << ": ";
if (pos != -1) cout << "position " << pos << "\n"; else cout << "-1\n";
}
int main() {
Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30);
for (int x : {20, 10, 40}) report(head, x);
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static int searchList(Node head, int target) {
int position = 1;
for (Node current = head; current != null; current = current.next, position++)
if (current.data == target) return position;
return -1; // fell off the end
}
static void report(Node head, int x) {
int pos = searchList(head, x);
System.out.println("search " + x + ": " + (pos != -1 ? "position " + pos : "-1"));
}
public static void main(String[] args) {
Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
for (int x : new int[]{20, 10, 40}) report(head, x);
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function searchList(head, target) {
let position = 1;
for (let current = head; current !== null; current = current.next, position++)
if (current.data === target) return position;
return -1; // fell off the end
}
function report(head, x) {
const pos = searchList(head, x);
console.log(`search ${x}:`, pos !== -1 ? `position ${pos}` : -1);
}
const head = new Node(10); head.next = new Node(20); head.next.next = new Node(30);
for (const x of [20, 10, 40]) report(head, x);search 20: position 2
search 10: position 1
search 40: -1Time O(n) · Space O(1)
Array vs linked list
| Operation | Array / dynamic array (contiguous) | Linked list (pointers) |
|---|---|---|
| Access by index | O(1) — address = base + i · size | O(n) — walk i links |
| Search (unsorted) | O(n) | O(n) |
| Search (sorted) | O(log n) binary search | O(n) — no random access, binary search impossible |
| Insert / delete at start | O(n) — shift every element | O(1) — re-link the head |
| Insert / delete at end | O(1) amortised (occasional resize copy) | O(n), or O(1) with a tail pointer (delete last stays O(n) for singly linked) |
| Insert / delete in the middle (position known) | O(n) — shift the tail | O(1) — once you hold the previous node |
| Extra memory | None per element; unused capacity in dynamic arrays | One next pointer per node |
| Memory layout | Contiguous — cache friendly, prefetchable | Scattered — pointer chasing, cache misses |
| Size | Fixed, or resized by copying | Grows node by node |
Interview Q&A
Why is inserting at the front O(1) in a linked list but O(n) in an array?
Why is binary search not possible on a linked list?
How do you find the middle of a linked list in one pass?
How would you reverse a singly linked list?
When is a linked list a better choice than a dynamic array?