Types

Singly Linked List

Singly Linked List

A singly linked list is a chain of nodes where each node holds a value and a single pointer to the node after it. There's no fixed size to worry about: nodes are created and linked in as needed, which is what makes insertion and deletion so cheap compared to an array.

A head pointer marks where the chain starts, and the last node's pointer is simply null, marking where it ends. Adding or removing right at the head is O(1), but reaching some node in the middle means walking node-by-node from the start, which costs O(n).

It's one of the simplest data structures around, which is exactly why it shows up as the foundation for stacks, queues, and even graph adjacency lists.

Key Property: Each node contains data and a single pointer to the next node, forming a unidirectional chain.

How It Lives in Memory

Unlike an array, a linked list's nodes aren't stored in one contiguous block of memory. Each node is allocated separately, wherever the runtime finds room, and gets linked to the next one purely through its pointer, so the "list" only exists because of those pointers, not because of physical ordering in memory.

That's the trade-off worth knowing: arrays are cache-friendly because reading array[i] and array[i+1] usually pulls both into the same cache line, while a linked list's scattered nodes mean each traversal step is likely a cache miss. It's part of why linked lists, despite matching or beating arrays on paper for insertion and deletion, can still lose to arrays in practice for pure iteration.

Basic Operations

OperationTime ComplexityDescription
Insertion at HeadO(1)Add new node at beginning by updating head pointer
Insertion at TailO(n)Traverse to end and add new node (O(1) with tail pointer)
Deletion at HeadO(1)Remove first node by updating head pointer
Deletion by ValueO(n)Traverse list to find and remove specific node
SearchO(n)Traverse list to find element
Access by IndexO(n)Traverse list until reaching desired position

Insertion at Head

A new node is created pointing to the current head, then the head pointer is repointed to the new node. No traversal is needed, so this runs in O(1).

headABnull

↓ insert X at head ↓

headXABnull

Insertion at Tail

Without a tail pointer, adding a node at the end means walking the whole chain first to find the current last node, then attaching the new one after it. That traversal is what makes this O(n) instead of O(1).

headABnull

↓ insert C at tail ↓

headABCnull

Optimization: A plain singly linked list only tracks head, which is why "Insertion at Tail" costs O(n): you have to walk the whole chain to find the last node before you can attach a new one. A common optimization is to also keep a tail pointer that always points at the last node. With that in hand, insertion at the tail drops to O(1) too, at the cost of a little extra bookkeeping (the tail pointer has to be updated on every tail insertion and, trickier, on deleting the last node).

Deletion

The node before the one being removed has its pointer redirected past it to the following node. Removing the head is O(1); removing from the middle first requires walking to the node before it, making it O(n).

headXABnull

↓ delete A ↓

headXBnull

Search & Traversal

Searching means starting at head and following next pointers one node at a time, comparing each node's value against the target, until either a match is found or the chain runs out (next is null). There's no way to jump ahead or look backward, so in the worst case (value at the end, or not present at all) every node gets visited, making search O(n) just like deletion by value.

head537null

Pros and Cons

Advantages

  • Dynamic size - grows as needed
  • Efficient insertion/deletion at head
  • No memory waste (only allocates needed nodes)

Limitations

  • No random access - must traverse from head
  • Extra memory for next pointers
  • Not cache-friendly (nodes scattered in memory)

Applications

  • Implementing stacks and queues
  • Memory management systems
  • Undo functionality in software
  • Hash table collision handling
  • Polynomial representation and arithmetic
  • Browser history navigation

Note: Singly linked lists are preferred when you need constant-time insertions/deletions at the beginning and don't require backward traversal.

Visualize Singly Linked List Operations

Linked List Memory Representation

No nodes in the list yet. Add your first node!

Test Your Knowledge before moving forward!

Linked List Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Singly Linked List Implementation

// Singly Linked List Implementation in JavaScript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // Insert at beginning
  insertFirst(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // Insert at end
  insertLast(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // Insert at index
  insertAt(data, index) {
    if (index < 0 || index > this.size) return;
    if (index === 0) return this.insertFirst(data);
    if (index === this.size) return this.insertLast(data);

    const newNode = new Node(data);
    let current = this.head;
    let previous;
    let count = 0;

    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }

    newNode.next = current;
    previous.next = newNode;
    this.size++;
  }

  // Get at index
  getAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.head;
    let count = 0;
    while (count < index) {
      current = current.next;
      count++;
    }
    return current.data;
  }

  // Remove at index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.head;
    if (index === 0) {
      this.head = current.next;
    } else {
      let previous;
      let count = 0;
      while (count < index) {
        previous = current;
        current = current.next;
        count++;
      }
      previous.next = current.next;
    }
    this.size--;
    return current.data;
  }

  // Clear list
  clear() {
    this.head = null;
    this.size = 0;
  }

  // Print list data
  print() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

// Usage Example
const list = new SinglyLinkedList();
list.insertFirst(100);
list.insertFirst(200);
list.insertLast(300);
list.insertAt(500, 1);
list.print(); // 200, 500, 100, 300
list.removeAt(2);
console.log(list.getAt(1)); // 500

Done With the Learning

Mark Singly Linked List as done and view it on your dashboard

Explore Other Types

Doubly Linked List

Circular Linked List