Singly Linked List

A Singly Linked List is a linear data structure where each element (node) contains data and a pointer to the next node. Unlike arrays, linked lists don't have fixed sizes and allow efficient insertion/deletion at any position.

The list maintains a head pointer that points to the first node. The last node's next pointer is null, indicating the end of the list. This structure provides O(1) insertion/deletion at the head but O(n) access time for arbitrary elements.

Singly linked lists are fundamental building blocks for more complex data structures like stacks, queues, and adjacency lists for graphs.

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

Basic Operations

Operation	Time Complexity	Description
Insertion at Head	O(1)	Add new node at beginning by updating head pointer
Insertion at Tail	O(n)	Traverse to end and add new node (O(1) with tail pointer)
Deletion at Head	O(1)	Remove first node by updating head pointer
Deletion by Value	O(n)	Traverse list to find and remove specific node
Search	O(n)	Traverse list to find element
Access by Index	O(n)	Traverse list until reaching desired position

Implementation

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  // Check if list is empty
  isEmpty() {
    return this.head === null;
  }
  // Insert at head
  insertFirst(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

Insertion at Head

1. Create new node with given data
2. Set new node's next to current head
3. Update head pointer to new node
4. Increment list size counter

head →

[A|•] → [B|•] → null

↓ Insert X at head ↓

head →

[X|•] → [A|•] → [B|•] → null

Deletion Operations

1. Check if list is empty (head === null)
2. If deleting head, update head to head.next
3. For middle deletion, find previous node and update its next pointer
4. Decrement list size counter
5. Return deleted data (if needed)

head →

[X|•] → [A|•] → [B|•] → null

↓ Delete A ↓

head →

[X|•] → [B|•] → null

Operation Visualization

Operation	List State
Initialization	head → null
insertFirst(10)	head → [10\|•] → null
insertFirst(20)	head → [20\|•] → [10\|•] → null
insertLast(30)	head → [20\|•] → [10\|•] → [30\|•] → null
deleteFirst()	head → [10\|•] → [30\|•] → null
delete(30)	head → [10\|•] → null

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

Node Value

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

Explore Other Types

Doubly Linked List

Circular Linked List