Singly Linked List

Implementation and API reference for singly linked list data structure

Singly Linked List

A linear data structure where each element (node) contains a value and a reference to the next node in the sequence.

Overview

Singly linked lists provide efficient insertion and deletion at the head (O(1)) but require O(n) time for access to arbitrary positions. Perfect for scenarios with frequent insertions and deletions.

Implementation

Node Structure

class Node<T = number> {
  value: T;
  next: Node<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

Reference: node.ts:1-9

Class Definition

class SinglyLinkedList<T = number> {
  head: Node<T> | null = null;
  size = 0;
  
  // ... methods
}

Reference: singly-linked-list.ts:3-6

API Reference

push(value: T): void

Adds an element to the end of the linked list.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
// List: (1) -> (2) -> (3) ->

Complexity: O(n)

Reference: singly-linked-list.ts:10-12

---

insert(value: T, index: number): void

Inserts a new element at the specified position.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(3);
list.insert(2, 1);
// List: (1) -> (2) -> (3) ->

Parameters:

• value: The value to insert
• index: Position to insert at (0-based)

Complexity:

• Insert at head: O(1)
• Insert at tail: O(n)
• Insert at arbitrary position: O(n)

Reference: singly-linked-list.ts:17-56

---

pop(): Node<T> | null

Removes and returns the last element from the linked list.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
const last = list.pop(); // returns node with value 2
// List: (1) ->

Complexity: O(n)

Reference: singly-linked-list.ts:61-85

---

at(index: number): Node<T> | null

Returns the element at the given index without removing it.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
const node = list.at(1); // returns node with value 2

Complexity: O(n)

Reference: singly-linked-list.ts:90-103

---

remove(value: T): void

Removes the first occurrence of an element from the list.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
list.remove(2);
// List: (1) -> (3) ->

Complexity: O(n)

Reference: singly-linked-list.ts:108-128

---

removeAt(index: number): void

Removes an element from the specified position in the list.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
list.removeAt(1);
// List: (1) -> (3) ->

Complexity: O(n)

Reference: singly-linked-list.ts:133-157

---

isEmpty(): boolean

Returns true if the list is empty, false otherwise.

const list = new SinglyLinkedList<number>();
console.log(list.isEmpty()); // true
list.push(1);
console.log(list.isEmpty()); // false

Complexity: O(1)

Reference: singly-linked-list.ts:162-164

---

toString(): string

Returns a string representation of the list.

const list = new SinglyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
console.log(list.toString()); // "(1) -> (2) -> (3) -> "

Complexity: O(n)

Reference: singly-linked-list.ts:169-183

Problems & Solutions

Problem 1: Partition List

Partition a linked list around a value x, such that all nodes less than x come before nodes greater than or equal to x.

/**
 * Time complexity: O(n)
 * Space complexity: O(1)
 */
function partitionList(list: SinglyLinkedList<number>, x: number) {
  let current = list.head;
  
  for (let i = 0; current?.next; i++) {
    const next = current.next;

    if (current.next.value < x) {
      current.next = next.next;

      // Move it to the left (head)
      const temp = list.head;
      list.head = next;
      next.next = temp;
    } else {
      current = next;
    }
  }
}

// Example: [3,5,8,5,10,2,1], x = 5
// Result: [1,2,3,5,8,5,10]

Reference: singly-linked-list.problems.test.ts:5-42

---

Problem 2: Add Two Numbers

Add two numbers represented by linked lists, where each node contains a single digit stored in reverse order.

/**
 * Time complexity: O(n * m)
 * Space complexity: O(n)
 */
function addTwoNumbers(
  n1: SinglyLinkedList<number>,
  n2: SinglyLinkedList<number>
): SinglyLinkedList<number> {
  const output = new SinglyLinkedList<number>();
  let current1 = n1.head;
  let current2 = n2.head;
  let carry = 0;

  while (current1) {
    if (current2) {
      const sum = current1.value + current2.value + carry;

      if (sum >= 10) {
        output.push(sum % 10);
        carry = Math.floor(sum / 10);
      } else {
        output.push(sum);
        carry = 0;
      }

      current1 = current1.next;
      current2 = current2.next;
    } else {
      output.push(current1.value + carry);
      carry = 0;
      current1 = current1.next;
    }
  }

  return output;
}

// Example: 617 + 295 = 912
// Input: (7) -> (1) -> (6) + (5) -> (9) -> (2)
// Output: (2) -> (1) -> (9)

Reference: singly-linked-list.problems.test.ts:45-94

Complexity Summary

Operation	Time Complexity	Space Complexity
push	O(n)	O(1)
insert (head)	O(1)	O(1)
insert (tail)	O(n)	O(1)
insert (arbitrary)	O(n)	O(1)
pop	O(n)	O(1)
at	O(n)	O(1)
remove	O(n)	O(1)
removeAt	O(n)	O(1)
isEmpty	O(1)	O(1)
toString	O(n)	O(1)

Key Characteristics

Advantages:

• Dynamic size
• Efficient insertion/deletion at head (O(1))
• No memory waste
• Easy to implement

Disadvantages:

• No random access (O(n) to reach arbitrary position)
• Extra memory for pointers
• Not cache-friendly
• No backward traversal

Use Cases

• Stack implementation: Fast push/pop at head
• Queue implementation: When combined with tail pointer
• Dynamic memory allocation: When size is unknown
• Undo functionality: Storing state history

For frequent access to tail, consider maintaining a tail pointer or use a Doubly Linked List instead.

Related Data Structures

Doubly Linked List

Bidirectional traversal support

Stack

Built using singly linked list

Queue

Built using singly linked list