Singly Linked List

Build a complete singly linked list class with insert and remove at head, tail, and arbitrary index, plus traversal and length tracking.

6 min read Level 2/5 #dsa#linked-list#singly-linked-list

What you'll learn

Implement insert and remove at head and tail in O(1) and O(n) time
Write index-based operations that walk the chain correctly
Read a complexity table and choose the right operation for a given scenario

A singly linked list stores a head pointer and a size counter. Every node has a val and a next reference; the last node’s next is null. All navigation moves in one direction — forward.

Node and List Skeleton

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

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

Insert at Head — O(1)

prepend(val) {
  this.head = new ListNode(val, this.head);
  this.size++;
}

The new node’s next is the old head. Reassigning this.head takes constant time regardless of list length.

Insert at Tail — O(n)

append(val) {
  const node = new ListNode(val);
  if (!this.head) {
    this.head = node;
  } else {
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = node;
  }
  this.size++;
}

We must walk the entire list to find the last node — O(n). A tail pointer turns this into O(1) and is covered in the doubly linked list lesson.

Insert at Index — O(n)

insertAt(index, val) {
  if (index < 0 || index > this.size) throw new RangeError("index out of range");
  if (index === 0) return this.prepend(val);

  let prev = this.head;
  for (let i = 0; i < index - 1; i++) prev = prev.next;

  prev.next = new ListNode(val, prev.next);
  this.size++;
}

Remove at Head — O(1)

removeHead() {
  if (!this.head) return null;
  const val = this.head.val;
  this.head = this.head.next;  // old head becomes unreachable → GC'd
  this.size--;
  return val;
}

Remove at Index — O(n)

removeAt(index) {
  if (index < 0 || index >= this.size) throw new RangeError("index out of range");
  if (index === 0) return this.removeHead();

  let prev = this.head;
  for (let i = 0; i < index - 1; i++) prev = prev.next;

  const val = prev.next.val;
  prev.next = prev.next.next;
  this.size--;
  return val;
}

Traversal

toArray() {
  const result = [];
  let curr = this.head;
  while (curr) {
    result.push(curr.val);
    curr = curr.next;
  }
  return result;
}

Operation Complexity

Operation	Time	Space
prepend (insert head)	O(1)	O(1)
append (insert tail)	O(n)	O(1)
insertAt(i)	O(n)	O(1)
removeHead	O(1)	O(1)
removeAt(i)	O(n)	O(1)
toArray / traversal	O(n)	O(n)
Access by index	O(n)	O(1)

Up Next

Add a prev pointer to each node and keep a tail reference to unlock O(1) insertion and removal at both ends.

Doubly Linked List →