Kata: Implement a Linked List

Table of contents

Problem Statement

Implement a singly linked list that supports the following operations:

• prepend(value) — insert at the head, O(1)
• append(value) — insert at the tail, O(n) or O(1) with tail pointer
• delete(value) — remove first occurrence, O(n)
• find(value) — search for a value, O(n)
• reverse() — reverse the list in place, O(n)
• toArray() — convert to array for inspection

Concepts

A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. Unlike arrays, linked lists allow O(1) insertion/deletion at known positions but require O(n) for random access.

TypeScript: This kata uses generics extensively. See TypeScript Core Concepts.

Python: You’ll implement the iterator protocol (__iter__, __len__). See Python Core Concepts.

Boilerplate

TypeScript

// linked-list.ts
class ListNode<T> {
  constructor(
    public value: T,
    public next: ListNode<T> | null = null
  ) {}
}

class LinkedList<T> {
  private head: ListNode<T> | null = null;

  prepend(value: T): void {
    // TODO
  }

  append(value: T): void {
    // TODO
  }

  delete(value: T): void {
    // TODO
  }

  find(value: T): ListNode<T> | null {
    // TODO
    return null;
  }

  reverse(): void {
    // TODO
  }

  toArray(): T[] {
    // TODO
    return [];
  }
}

PHP

// LinkedList.php
class ListNode {
    public function __construct(
        public readonly mixed $value,
        public ?ListNode $next = null,
    ) {}
}

class LinkedList {
    private ?ListNode $head = null;

    public function prepend(mixed $value): void { /* TODO */ }
    public function append(mixed $value): void { /* TODO */ }
    public function delete(mixed $value): void { /* TODO */ }
    public function find(mixed $value): ?ListNode { /* TODO */ return null; }
    public function reverse(): void { /* TODO */ }
    public function toArray(): array { /* TODO */ return []; }
}

Python

# linked_list.py
from __future__ import annotations
from typing import Iterator

class ListNode[T]:
    def __init__(self, value: T, next_node: ListNode[T] | None = None) -> None:
        self.value = value
        self.next = next_node

class LinkedList[T]:
    def __init__(self) -> None:
        self._head: ListNode[T] | None = None

    def prepend(self, value: T) -> None: ...
    def append(self, value: T) -> None: ...
    def delete(self, value: T) -> None: ...
    def find(self, value: T) -> ListNode[T] | None: ...
    def reverse(self) -> None: ...

    def __iter__(self) -> Iterator[T]: ...
    def __len__(self) -> int: ...
    def __repr__(self) -> str: ...

Hints

Solution

TypeScript

class ListNode<T> {
  constructor(
    public value: T,
    public next: ListNode<T> | null = null
  ) {}
}

class LinkedList<T> {
  private head: ListNode<T> | null = null;

  prepend(value: T): void {
    this.head = new ListNode(value, this.head);
  }

  append(value: T): void {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }

  delete(value: T): void {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  find(value: T): ListNode<T> | null {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  reverse(): void {
    let prev: ListNode<T> | null = null;
    let current = this.head;
    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    this.head = prev;
  }

  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

Python

from __future__ import annotations
from typing import Iterator

class ListNode[T]:
    def __init__(self, value: T, next_node: ListNode[T] | None = None) -> None:
        self.value = value
        self.next = next_node

class LinkedList[T]:
    def __init__(self) -> None:
        self._head: ListNode[T] | None = None
        self._size = 0

    def prepend(self, value: T) -> None:
        self._head = ListNode(value, self._head)
        self._size += 1

    def append(self, value: T) -> None:
        node = ListNode(value)
        if not self._head:
            self._head = node
        else:
            current = self._head
            while current.next:
                current = current.next
            current.next = node
        self._size += 1

    def delete(self, value: T) -> None:
        if not self._head:
            return
        if self._head.value == value:
            self._head = self._head.next
            self._size -= 1
            return
        current = self._head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                self._size -= 1
                return
            current = current.next

    def find(self, value: T) -> ListNode[T] | None:
        current = self._head
        while current:
            if current.value == value:
                return current
            current = current.next
        return None

    def reverse(self) -> None:
        prev = None
        current = self._head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self._head = prev

    def __iter__(self) -> Iterator[T]:
        current = self._head
        while current:
            yield current.value
            current = current.next

    def __len__(self) -> int:
        return self._size

    def __repr__(self) -> str:
        return " -> ".join(str(v) for v in self)

Complexity Analysis

Append can be made O(1) by maintaining a tail pointer.

Cross-Language Notes

PHP: PHP provides SplDoublyLinkedList as a built-in doubly linked list. See PHP Core Concepts. PHP arrays are actually ordered hash maps, so a separate linked list implementation is needed for true linked list behavior.

Python: Python lists are dynamic arrays, not linked lists. For queue-like behavior, use collections.deque which provides O(1) operations at both ends. See Python Core Concepts.

Rust: Implementing a linked list in Rust is a classic exercise in ownership and borrowing. The book Learn Rust With Entirely Too Many Linked Lists is an excellent deep dive.