Linked List | Murad's Blog

A linear data structure where each element (node) holds a value and a pointer to the next node. No contiguous memory required — unlike arrays.

Node Structure

text

Node:
  value
  next  → Node | null

// Doubly linked
Node:
  value
  next  → Node | null
  prev  → Node | null

Types

Type	Pointers	Notes
Singly	next only	Less memory, one-directional traversal
Doubly	next + prev	Easier deletion, 2× pointer overhead
Circular	tail.next → head	Used in round-robin, buffering

Core Operations

Traversal

text

traverse(head):
  curr = head
  while curr != null:
    visit(curr)
    curr = curr.next

	Time	Space
Complexity	O(n)	O(1)

Insert at Head

text

insertHead(head, val):
  node = Node(val)
  node.next = head
  head = node
  return head

	Time	Space
Complexity	O(1)	O(1)

Insert at Tail

text

insertTail(head, val):
  node = Node(val)
  if head == null: return node
  curr = head
  while curr.next != null: curr = curr.next
  curr.next = node
  return head

	Time	Space
Complexity	O(n)	O(1)

O(1) if you maintain a tail pointer.

Delete by Value

text

delete(head, val):
  if head.value == val: return head.next
  curr = head
  while curr.next != null:
    if curr.next.value == val:
      curr.next = curr.next.next
      return head
    curr = curr.next
  return head

	Time	Space
Complexity	O(n)	O(1)

Reverse a Linked List

Classic interview problem. Three-pointer iterative approach.

text

reverse(head):
  prev = null
  curr = head
  while curr != null:
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  return prev

	Time	Space
Complexity	O(n)	O(1)

Detect Cycle (Floyd's Algorithm)

Two pointers — slow moves 1 step, fast moves 2. If they meet, there's a cycle.

text

hasCycle(head):
  slow = head
  fast = head
  while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
    if slow == fast: return true
  return false

	Time	Space
Complexity	O(n)	O(1)

Find Middle Node

Same two-pointer trick — when fast reaches end, slow is at the middle.

text

findMiddle(head):
  slow = head
  fast = head
  while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
  return slow

	Time	Space
Complexity	O(n)	O(1)

Array vs Linked List

Operation	Array	Linked List
Access by index	O(1)	O(n)
Insert at head	O(n)	O(1)
Insert at tail	O(1) amortized	O(n) / O(1) with tail ptr
Delete	O(n)	O(n) search + O(1) delete
Memory	Contiguous	Scattered + pointer overhead

Quick Reference

Operation	Singly	Doubly
Insert head	O(1)	O(1)
Insert tail	O(n)	O(1) with tail ptr
Delete head	O(1)	O(1)
Delete tail	O(n)	O(1) with tail ptr
Search	O(n)	O(n)
Reverse	O(n)	O(n)