A linked list is a linear data structure where elements aren’t stored in contiguous memory. Instead, each element (called a node) holds two things: the data and a pointer (or reference) to the next node.
In simple language, think of a linked list like a scavenger hunt. Each clue tells us where to find the next clue. We can only move forward by following the chain — we can’t jump to the 5th clue directly.
Why Use Linked Lists?
Arrays are great, but they have a weakness: inserting or deleting in the middle requires shifting everything over. That’s O(n). Linked lists can insert or delete in O(1) if we already have a pointer to the right spot.
The trade-off? We lose random access. Getting the 5th element means following 5 pointers. That’s O(n) instead of O(1) with arrays.
Singly Linked List
Each node points to the next. The last node points to null.
Doubly Linked List
Each node has pointers to both the next AND previous nodes. We can traverse in both directions.
Node Definition
// Singly linked list node
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
// Doubly linked list node
class DListNode {
constructor(val, prev = null, next = null) {
this.val = val;
this.prev = prev;
this.next = next;
}
}# Singly linked list node
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Doubly linked list node
class DListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next// Singly linked list node
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
// Doubly linked list node
class DListNode {
int val;
DListNode prev, next;
DListNode(int val) { this.val = val; }
}Core Operations
Insert at Head — O(1)
// Insert a new node at the beginning
function insertAtHead(head, val) {
const newNode = new ListNode(val);
newNode.next = head; // point new node to old head
return newNode; // new node is now the head
}# Insert a new node at the beginning
def insert_at_head(head, val):
new_node = ListNode(val)
new_node.next = head # point new node to old head
return new_node # new node is now the head// Insert a new node at the beginning
static ListNode insertAtHead(ListNode head, int val) {
ListNode newNode = new ListNode(val);
newNode.next = head; // point new node to old head
return newNode; // new node is now the head
}Delete a Node — O(n) search + O(1) delete
// Delete first node with given value
function deleteNode(head, val) {
const dummy = new ListNode(0, head); // dummy to handle head deletion
let prev = dummy;
while (prev.next) {
if (prev.next.val === val) {
prev.next = prev.next.next; // skip over the node
break;
}
prev = prev.next;
}
return dummy.next;
}# Delete first node with given value
def delete_node(head, val):
dummy = ListNode(0, head) # dummy to handle head deletion
prev = dummy
while prev.next:
if prev.next.val == val:
prev.next = prev.next.next # skip over the node
break
prev = prev.next
return dummy.next// Delete first node with given value
static ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(0, head); // dummy to handle head deletion
ListNode prev = dummy;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next; // skip over the node
break;
}
prev = prev.next;
}
return dummy.next;
}Pro tip: The dummy node trick is hugely useful. It eliminates the edge case of deleting the head node. We’ll use it constantly in linked list problems.
Reverse a Linked List
This is the #1 most common linked list interview question. The idea: we walk through the list and flip each pointer to point backward instead of forward.
// Reverse a singly linked list -- O(n) time, O(1) space
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next; // save next before we break the link
curr.next = prev; // reverse the pointer
prev = curr; // move prev forward
curr = next; // move curr forward
}
return prev; // prev is the new head
}# Reverse a singly linked list -- O(n) time, O(1) space
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next # save next before we break the link
curr.next = prev # reverse the pointer
prev = curr # move prev forward
curr = next_node # move curr forward
return prev # prev is the new head// Reverse a singly linked list -- O(n) time, O(1) space
static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save next before we break the link
curr.next = prev; // reverse the pointer
prev = curr; // move prev forward
curr = next; // move curr forward
}
return prev; // prev is the new head
}Three pointers is all we need: prev, curr, and next. Memorize this pattern — it shows up everywhere.
Detect a Cycle — Floyd’s Algorithm
If a linked list has a cycle (a node’s next points back to an earlier node), we’ll loop forever trying to reach null. Floyd’s tortoise and hare algorithm detects this using two pointers moving at different speeds.
The slow pointer moves 1 step at a time. The fast pointer moves 2 steps. If there’s a cycle, they’ll eventually meet. If there’s no cycle, fast reaches null.
// Detect cycle in a linked list
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next; // move 1 step
fast = fast.next.next; // move 2 steps
if (slow === fast) return true; // they met -- cycle exists!
}
return false; // fast reached null -- no cycle
}# Detect cycle in a linked list
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next # move 1 step
fast = fast.next.next # move 2 steps
if slow == fast:
return True # they met -- cycle exists!
return False # fast reached null -- no cycle// Detect cycle in a linked list
static boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // move 1 step
fast = fast.next.next; // move 2 steps
if (slow == fast) return true; // they met -- cycle exists!
}
return false; // fast reached null -- no cycle
}Why does this work? Think of two runners on a circular track. The faster one will always lap the slower one. Same idea here.
Merge Two Sorted Lists
Another interview classic. We have two sorted linked lists and want to merge them into one sorted list.
// Merge two sorted linked lists
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0); // dummy head
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2; // attach remaining nodes
return dummy.next;
}# Merge two sorted linked lists
def merge_two_lists(l1, l2):
dummy = ListNode(0) # dummy head
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2 # attach remaining nodes
return dummy.next// Merge two sorted linked lists
static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // dummy head
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2; // attach remaining
return dummy.next;
}Key Patterns to Remember
| Pattern | When to Use |
|---|---|
| Dummy node | When the head might change (deletion, merging) |
| Two pointers (slow/fast) | Cycle detection, finding middle node |
| Prev/Curr/Next pointers | Reversing a list |
| Recursion | When iterative feels awkward (merge, reverse) |
Complexity Cheat Sheet
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Access by index | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at tail | O(n) / O(1) with tail pointer | O(1) with tail pointer |
| Delete (given node) | O(n) to find prev | O(1) — we have prev pointer |
| Search | O(n) | O(n) |
The main takeaway: linked lists trade random access for efficient insertion/deletion. In interviews, watch for problems where we need to manipulate pointers — that’s where linked lists shine.