DSASingly Linked List

Singly Linked List

A singly linked list is the simplest form of a linked list. Each node stores a value and a single next pointer. Traversal goes in one direction only — from head to tail. In this page you will build a complete, production-quality implementation from scratch with every common operation.

Node Class

Everything starts with the Node class. It is intentionally minimal — just data and a pointer.

JS
class Node {
  /**
   * @param {*} val - The value to store in this node.
   */
  constructor(val) {
    this.val = val    // the data payload
    this.next = null  // reference to the next Node (null = no next node)
  }
}
LinkedList Class — Scaffold

The LinkedList class owns the head and tail pointers and a size counter. Every method you add will manipulate these three fields.

JS
class LinkedList {
  constructor() {
    this.head = null  // points to the first Node; null when empty
    this.tail = null  // points to the last Node;  null when empty
    this.size = 0     // number of nodes currently in the list
  }
}
Note
Tracking `tail` separately lets `insertAtTail` run in O(1) instead of O(n). Tracking `size` lets `length()` return in O(1) instead of O(n). Both are optional but strongly recommended.
insertAtHead(val) — O(1)

Prepending to a linked list is the operation that makes it shine. No shifting required — you create one new node and update two pointers.

Steps:

  1. Create a new Node(val).

  2. Point the new node's next at the current head.

  3. Set head to the new node.

  4. If the list was empty (tail === null), set tail to the new node too.

  5. Increment size.

Before:  head --> [20] --> [30] --> null

insertAtHead(10):

Step 1:  newNode = [10 | null]
Step 2:  newNode.next = head  =>  [10] --> [20] --> [30] --> null
Step 3:  head = newNode       =>  head points to [10]

After:   head --> [10] --> [20] --> [30] --> null

JS
insertAtHead(val) {
  const newNode = new Node(val)   // O(1) — allocate one node

  newNode.next = this.head        // new node points to old head (may be null)
  this.head = newNode             // head now points to new node

  // Special case: if the list was empty, tail must also point to the new node
  if (this.tail === null) {
    this.tail = newNode
  }

  this.size++
  return this  // allow method chaining
}
insertAtTail(val) — O(1) with tail pointer

Appending is O(1) only because we maintain the tail pointer. Without it, you would traverse the whole list every time — O(n).

Steps:

  1. Create a new Node(val).

  2. Point the current tail's next at the new node.

  3. Advance tail to the new node.

  4. If the list was empty, set head to the new node too.

  5. Increment size.

Before:  head --> [10] --> [20] --> null   (tail points to [20])

insertAtTail(30):

Step 1:  newNode = [30 | null]
Step 2:  tail.next = newNode  =>  [20] --> [30]
Step 3:  tail = newNode       =>  tail points to [30]

After:   head --> [10] --> [20] --> [30] --> null
                                    tail --^

JS
insertAtTail(val) {
  const newNode = new Node(val)   // O(1)

  if (this.tail === null) {
    // Empty list — new node is both head and tail
    this.head = newNode
    this.tail = newNode
  } else {
    this.tail.next = newNode   // current last node points forward to new node
    this.tail = newNode        // tail pointer advances to new node
  }

  this.size++
  return this
}
insertAt(index, val) — O(n)

Inserting at an arbitrary position requires traversing to the node just before the target index, then rewiring two pointers.

Steps:

  1. Validate the index (0 to size, inclusive).

  2. Delegate to insertAtHead if index is 0.

  3. Delegate to insertAtTail if index equals size.

  4. Otherwise traverse to the node at index - 1 (call it prev).

  5. Set newNode.next = prev.next — new node points to the displaced node.

  6. Set prev.next = newNode — predecessor now points to new node.

  7. Increment size.

List:  [10] --> [20] --> [40] --> null    (inserting 30 at index 2)

Before pointer rewire:
  prev = [20]
  newNode = [30]
  newNode.next = prev.next  =>  [30] --> [40]
  prev.next    = newNode    =>  [20] --> [30]

After:  [10] --> [20] --> [30] --> [40] --> null

JS
insertAt(index, val) {
  // Guard: index must be within [0, size]
  if (index < 0 || index > this.size) {
    throw new RangeError(`Index ${index} out of bounds (size: ${this.size})`)
  }

  // Reuse the O(1) head/tail methods for the edge cases
  if (index === 0)         return this.insertAtHead(val)
  if (index === this.size) return this.insertAtTail(val)

  // Traverse to the node just before the target position
  const newNode = new Node(val)
  let prev = this.head
  for (let i = 0; i < index - 1; i++) {
    prev = prev.next   // advance one step per iteration
  }

  // Splice the new node in between prev and prev.next
  newNode.next = prev.next  // new node points to the displaced successor
  prev.next    = newNode    // predecessor points to new node

  this.size++
  return this
}
deleteByValue(val) — O(n)

Deletes the first node whose val matches the target. You need a reference to the node before the one you want to delete, so you can bridge over it.

Steps:

  1. If the list is empty, return false.

  2. If head.val matches, advance head and decrement size. Update tail if the list became empty.

  3. Otherwise, walk the list keeping a prev pointer one step behind current.

  4. When current.val matches, set prev.next = current.next to skip over it.

  5. If the deleted node was tail, update tail = prev.

  6. Return true if deleted, false if not found.

List:  [10] --> [20] --> [30] --> null

deleteByValue(20):
  prev = [10], current = [20]  => match!
  prev.next = current.next     => [10] --> [30] --> null

After:  [10] --> [30] --> null

JS
deleteByValue(val) {
  if (this.head === null) return false   // empty list — nothing to delete

  // Special case: the head node itself is the target
  if (this.head.val === val) {
    this.head = this.head.next           // advance head past the deleted node
    if (this.head === null) {
      this.tail = null                   // list is now empty
    }
    this.size--
    return true
  }

  // General case: traverse looking for the target
  let prev    = this.head
  let current = this.head.next

  while (current !== null) {
    if (current.val === val) {
      prev.next = current.next           // bridge over the deleted node

      if (current.next === null) {
        this.tail = prev                 // deleted node was the tail — update tail
      }

      this.size--
      return true
    }

    prev    = current
    current = current.next
  }

  return false   // value not found in the list
}
deleteAt(index) — O(n)

Deletes the node at a specific index. Same bridging technique, but you stop at a position rather than a value.

JS
deleteAt(index) {
  if (index < 0 || index >= this.size) {
    throw new RangeError(`Index ${index} out of bounds (size: ${this.size})`)
  }

  // Remove the head
  if (index === 0) {
    const removed = this.head.val
    this.head = this.head.next
    if (this.head === null) this.tail = null
    this.size--
    return removed
  }

  // Traverse to the node just before the target index
  let prev = this.head
  for (let i = 0; i < index - 1; i++) {
    prev = prev.next
  }

  const toDelete = prev.next               // the node we are removing
  prev.next = toDelete.next                // bridge over it

  if (toDelete.next === null) {
    this.tail = prev                       // removed the tail — update tail pointer
  }

  this.size--
  return toDelete.val   // return the deleted value
}
search(val) — O(n)

Returns the index of the first node with the given value, or -1 if not found. No shortcuts exist — every node must potentially be visited.

JS
search(val) {
  let current = this.head
  let index   = 0

  while (current !== null) {
    if (current.val === val) {
      return index   // found — return the 0-based position
    }
    current = current.next
    index++
  }

  return -1   // not found
}

// Usage:
// list.search(20) => 1   (if [10] --> [20] --> [30])
// list.search(99) => -1
reverse() — O(n) iterative

Reversing a singly linked list in-place is a classic interview problem. The trick is to maintain three pointers as you scan: prev, current, and next. Each iteration flips one next pointer.

The three-pointer dance:

Initial:  null  <--  [10] --> [20] --> [30] --> null
                       ^
                     current

Step 1:  save next = current.next  (= [20])
         current.next = prev       (flip: [10] --> null)
         prev = current            (prev advances to [10])
         current = next            (current advances to [20])

Step 2:  save next = current.next  (= [30])
         current.next = prev       (flip: [20] --> [10])
         prev = current            (prev advances to [20])
         current = next            (current advances to [30])

Step 3:  save next = current.next  (= null)
         current.next = prev       (flip: [30] --> [20])
         prev = current            (prev advances to [30])
         current = next            (current = null — loop ends)

Result:  null <-- [10] <-- [20] <-- [30]
                                     ^
                                   new head

JS
reverse() {
  let prev    = null
  let current = this.head

  // The old head becomes the new tail — save it before the loop
  this.tail = this.head

  while (current !== null) {
    const next   = current.next  // save the forward link before overwriting it
    current.next = prev          // flip: point this node backwards
    prev         = current       // advance prev one step forward
    current      = next          // advance current one step forward
  }

  // When the loop ends, prev points to the last node we processed — the new head
  this.head = prev

  return this
}

// Example:
// Before: [10] --> [20] --> [30]
// After:  [30] --> [20] --> [10]
Tip
The iterative approach uses O(1) extra space. A recursive approach also works but uses O(n) call-stack space — avoid it for large lists.
length() — O(1)

Because we track size as we insert and delete, length() is a simple getter — no traversal needed.

JS
length() {
  return this.size
  // O(1) — we maintain size as insertions/deletions happen
}

// Without the size counter you would have to do:
// let count = 0; let c = this.head; while (c) { count++; c = c.next; } return count;
// That is O(n) — avoid it when possible
print() — O(n)

Useful for debugging. Traverses the list and logs each value, separated by arrows to mirror the visual diagram.

JS
print() {
  if (this.head === null) {
    console.log('(empty list)')
    return
  }

  const parts = []
  let current = this.head

  while (current !== null) {
    parts.push(current.val)
    current = current.next
  }

  console.log(parts.join(' --> ') + ' --> null')
}

// Output example:  10 --> 20 --> 30 --> null
Complete Implementation

Here is the full class with every method assembled together, ready to copy and use:

JS
class Node {
  constructor(val) {
    this.val  = val
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.size = 0
  }

  // ---- Insertion -----------------------------------------------------------

  insertAtHead(val) {
    const newNode = new Node(val)
    newNode.next  = this.head
    this.head     = newNode
    if (this.tail === null) this.tail = newNode
    this.size++
    return this
  }

  insertAtTail(val) {
    const newNode = new Node(val)
    if (this.tail === null) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail      = newNode
    }
    this.size++
    return this
  }

  insertAt(index, val) {
    if (index < 0 || index > this.size) {
      throw new RangeError(`Index ${index} out of bounds (size: ${this.size})`)
    }
    if (index === 0)         return this.insertAtHead(val)
    if (index === this.size) return this.insertAtTail(val)

    const newNode = new Node(val)
    let prev = this.head
    for (let i = 0; i < index - 1; i++) prev = prev.next
    newNode.next = prev.next
    prev.next    = newNode
    this.size++
    return this
  }

  // ---- Deletion ------------------------------------------------------------

  deleteByValue(val) {
    if (this.head === null) return false

    if (this.head.val === val) {
      this.head = this.head.next
      if (this.head === null) this.tail = null
      this.size--
      return true
    }

    let prev    = this.head
    let current = this.head.next

    while (current !== null) {
      if (current.val === val) {
        prev.next = current.next
        if (current.next === null) this.tail = prev
        this.size--
        return true
      }
      prev    = current
      current = current.next
    }

    return false
  }

  deleteAt(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`Index ${index} out of bounds (size: ${this.size})`)
    }

    if (index === 0) {
      const removed = this.head.val
      this.head     = this.head.next
      if (this.head === null) this.tail = null
      this.size--
      return removed
    }

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

    const toDelete = prev.next
    prev.next      = toDelete.next
    if (toDelete.next === null) this.tail = prev
    this.size--
    return toDelete.val
  }

  // ---- Search --------------------------------------------------------------

  search(val) {
    let current = this.head
    let index   = 0
    while (current !== null) {
      if (current.val === val) return index
      current = current.next
      index++
    }
    return -1
  }

  // ---- Utility -------------------------------------------------------------

  reverse() {
    let prev    = null
    let current = this.head
    this.tail   = this.head

    while (current !== null) {
      const next   = current.next
      current.next = prev
      prev         = current
      current      = next
    }

    this.head = prev
    return this
  }

  length() {
    return this.size
  }

  print() {
    if (this.head === null) { console.log('(empty list)'); return }
    const parts = []
    let current = this.head
    while (current !== null) {
      parts.push(current.val)
      current = current.next
    }
    console.log(parts.join(' --> ') + ' --> null')
  }
}
Usage Examples

JS
const list = new LinkedList()

// Build the list: 10 --> 20 --> 30 --> 40
list.insertAtTail(20)
list.insertAtHead(10)
list.insertAtTail(40)
list.insertAt(2, 30)  // insert 30 at index 2

list.print()          // 10 --> 20 --> 30 --> 40 --> null
console.log(list.length())     // 4

// Search
console.log(list.search(30))   // 2
console.log(list.search(99))   // -1

// Delete
list.deleteByValue(20)
list.print()          // 10 --> 30 --> 40 --> null

list.deleteAt(0)
list.print()          // 30 --> 40 --> null

// Reverse
list.insertAtHead(10)
list.print()          // 10 --> 30 --> 40 --> null
list.reverse()
list.print()          // 40 --> 30 --> 10 --> null
Complexity Summary

Operation

Time

Space

Notes

insertAtHead

O(1)

O(1)

Update head pointer — no traversal

insertAtTail

O(1)

O(1)

Update tail pointer directly

insertAt(i)

O(n)

O(1)

Traverse to index i-1 first

deleteByValue

O(n)

O(1)

Must scan to find the value

deleteAt(i)

O(n)

O(1)

Traverse to index i-1 first

search

O(n)

O(1)

Linear scan; no index shortcut

reverse

O(n)

O(1)

Single pass, three pointers

length

O(1)

O(1)

Maintained by size counter

print

O(n)

O(n)

Builds output array then logs

Common Pitfalls

  • Forgetting to update tail — whenever you insert into an empty list or delete the last node, both head and tail must be updated together.

  • Off-by-one in insertAt / deleteAt — traverse to index i - 1 (the predecessor), not index i itself.

  • Lost tail after deleteByValue — after removing a node, check if current.next === null; if so, update this.tail = prev.

  • Reversing without saving the old head — the old head becomes the new tail before the loop begins. Save it first.

  • Infinite loops in circular lists — if you ever accidentally set a node's next to point back to itself or an ancestor, traversal will loop forever.

Warning
When debugging a linked list, add a `print()` call after every mutation to verify the structure is exactly what you expect. Pointer bugs are invisible until you traverse the list.
Key Takeaways

  1. A singly linked list stores nodes connected by a single next pointer — O(1) head insertions, O(n) everything else.

  2. Track both head and tail to get O(1) appends. Track size to get O(1) length.

  3. Every mutating operation has two responsibilities: update the data pointers AND keep head, tail, and size consistent.

  4. Deleting a node requires a reference to its predecessor — traverse one step before the target.

  5. Reversing in-place uses three pointers (prev, current, next) and runs in O(n) time with O(1) space.

  6. The same traversal skeleton — let c = head; while (c !== null) { ...; c = c.next } — powers every linked list algorithm.