Learn the fundamental operations that make linked lists powerful: insertion, deletion, traversal, and search. Watch them in action with interactive animations!

Core Operations Overview

🎯 Essential Operations

Every linked list must support these fundamental operations. Understanding their implementation and complexity is crucial for choosing the right data structure for your problem.

Traversal

O(n)

Visit each node from head to tail sequentially

Detailed Steps:

Start with pointer at head node
Process/visit current node data
Follow next pointer to move forward
Repeat until reaching NULL pointer
Total visits = number of nodes

Time

O(n)

Space

O(1)

Insertion

O(1)

Add new node at beginning, end, or specific position

Detailed Steps:

Allocate memory for new node
Set data value in new node
Update pointer connections
Handle head/tail pointer updates
Consider edge cases (empty list)

Time

O(1)

Space

O(1)

Deletion

O(1)

Remove node from beginning, end, or specific position

Detailed Steps:

Locate the target node to delete
Update previous node's next pointer
Handle head pointer if deleting first
Free the memory of deleted node
Handle edge cases (single node, empty list)

Time

O(1)

Space

O(1)

Search

O(n)

Find node with specific value or position

Detailed Steps:

Start from head node
Compare current node data with target
If match found, return node/position
Otherwise, move to next node
Return null if not found after full traversal

Time

O(n)

Space

O(1)

Interactive Animations

Insert at Head

Adding a new node at the beginning of the list

Step 1: Create new node

HEAD

Node

New

NULL

Code Implementation

💻 Implementation Details

Here are clean, production-ready implementations of each operation. Study the pointer manipulations and edge case handling to master linked list programming.

Traversal Implementation

Time: O(n)Space: O(1)

function traverse(head) {
  let current = head;
  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
}

Key Points: Focus on pointer updates, memory management, and handling edge cases like empty lists.

Insertion Implementation

Time: O(1)Space: O(1)

function insertAtHead(head, data) {
  let newNode = new Node(data);
  newNode.next = head;
  return newNode; // new head
}

Key Points: Focus on pointer updates, memory management, and handling edge cases like empty lists.

Deletion Implementation

Time: O(1)Space: O(1)

function deleteHead(head) {
  if (head === null) return null;
  let temp = head.next;
  delete head; // free memory
  return temp; // new head
}

Key Points: Focus on pointer updates, memory management, and handling edge cases like empty lists.

Search Implementation

Time: O(n)Space: O(1)

function search(head, target) {
  let current = head;
  let position = 0;
  while (current !== null) {
    if (current.data === target) {
      return position;
    }
    current = current.next;
    position++;
  }
  return -1; // not found
}

Key Points: Focus on pointer updates, memory management, and handling edge cases like empty lists.

Multi-Language Implementation Gallery

🌐 Cross-Language Perspective

Compare how core linked list structures and operations look across TypeScript, C, and Python. Note differences in memory management, syntax verbosity, and pointer handling. Switching languages reinforces the underlying concepts independent of syntax.

Implementation Gallery

TypeScript Implementationtypescript

class ListNode<T> {
  constructor(
    public data: T,
    public next: ListNode<T> | null = null
  ) {}
}

class SinglyLinkedList<T> {
  head: ListNode<T> | null = null;

  insertHead(data: T) {
    const node = new ListNode(data, this.head);
    this.head = node;
  }

  search(target: T): ListNode<T> | null {
    let cur = this.head;
    while (cur) {
      if (cur.data === target) return cur;
      cur = cur.next;
    }
    return null;
  }

  reverse() {
    let prev: ListNode<T> | null = null;
    let cur = this.head;
    while (cur) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    this.head = prev;
  }
}

GC handles memory; no manual free()

Generics for type safety

Methods run in O(n) where appropriate

Reflection Tips: Identify what code changes between languages and what remains conceptually identical. This helps you separate algorithmic thinking from language-specific boilerplate.

Time Complexity Analysis

Operation	Singly	Doubly	Circular
Access (index)	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n)
Insert (head)	O(1)	O(1)	O(1)
Insert (end)	O(n)	O(1)*	O(1)*
Delete (head)	O(1)	O(1)	O(1)
Delete (end)	O(n)	O(1)*	O(1)*

* Assumes a maintained tail pointer.

Performance & Memory Notes

Cache Locality

Arrays leverage spatial locality; CPUs prefetch sequential memory. Linked lists scatter nodes causing more cache misses → real-world slowdowns despite similar Big-O.

Memory Overhead

Each node stores at least one pointer. Rough overhead approx: pointer_size / (data_size + pointer_size). For small data (e.g. int32), pointer overhead can exceed 50%.

Allocation Cost

Frequent per-node allocations stress allocator & fragment memory. Pools or slab allocators mitigate but add complexity.

When Lists Win

Unpredictable growth with frequent head ops
Iterator stability under insert/delete
Concatenation via tail.next = other_head

When Arrays Win

Heavy traversal/search usage
Frequent indexing needs
Cache-sensitive inner loops

Rule of Thumb: Start with a dynamic array (vector). Migrate to a list only when profiling reveals head/tail insertion or stable iterator requirements dominate and memory overhead is acceptable.

Operations Knowledge Check

Why is deleting a node in the middle of a singly list O(n)?

MEDIUM

Which operation is inherently O(n) even with a tail pointer?

HARD

Previous: Types Next: Problems

class ListNode<T> { constructor( public data: T, public next: ListNode<T> | null = null ) {} } class SinglyLinkedList<T> { head: ListNode<T> | null = null; insertHead(data: T) { const node = new ListNode(data, this.head); this.head = node; } search(target: T): ListNode<T> | null { let cur = this.head; while (cur) { if (cur.data === target) return cur; cur = cur.next; } return null; } reverse() { let prev: ListNode<T> | null = null; let cur = this.head; while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } this.head = prev; } }

Operation

Singly

Doubly

Circular

Access (index)

O(n)

Insert (head)

O(1)

Insert (end)

O(n)

O(1)*

Delete (head)

O(1)

Delete (end)

O(n)

O(1)*