Linked List

Level: Intermediate 30–60 min

Concepts: Data StructuresAlgorithmsEdge Cases

Solutions: C# | TypeScript | Python

---

Implement a singly linked list with standard operations. No built-in list or array types allowed for the underlying storage.

Requirements

Build a linked list that supports:

Core Operations

• append(value) — add a value to the end
• prepend(value) — add a value to the beginning
• size() — return the number of elements
• get(index) — return the value at the given index (0-based)
• remove(index) — remove the element at the given index and return its value
• toArray() — return all values as an array (for testing convenience)

Search Operations

• contains(value) — return true if the value exists in the list
• indexOf(value) — return the index of the first occurrence, or -1 if not found

Insert Operations

• insertAt(index, value) — insert a value at the given index, shifting subsequent elements

Test Cases

Operation	List State	Result
append(1)	[1]	—
append(2)	[1, 2]	—
prepend(0)	[0, 1, 2]	—
size()	[0, 1, 2]	3
get(0)	[0, 1, 2]	0
get(2)	[0, 1, 2]	2
get(5)	[0, 1, 2]	Error: index out of bounds
remove(1)	[0, 2]	1 (removed value)
remove(0)	[2]	0 (removed value)
contains(2)	[2]	true
contains(99)	[2]	false
indexOf(2)	[2]	0
insertAt(0, 5)	[5, 2]	—
insertAt(1, 7)	[5, 7, 2]	—

Edge cases:

• get(-1) → error
• remove(0) on empty list → error
• append to empty list → list of one element
• remove the only element → empty list
• insertAt(size(), value) → equivalent to append

Bonus

• Implement reverse() — reverse the list in place
• Implement sort() — sort the list (merge sort is natural for linked lists)
• Convert to a doubly linked list with previous pointers
• Implement an iterator/generator so the list works with for...of loops
• Detect cycles — given a potentially corrupted list, determine if it contains a cycle

Hint

Start with append and size. You need a Node class with value and next. The list tracks the head node. Build get(index) next — most other operations depend on traversing to a specific position. Handle the empty list and single-element list cases explicitly before generalizing.

Reference Walkthrough

Reference implementations in C#, TypeScript, and Python live at tddbuddy-reference-katas/linked-list. This is an F1 kata — 18 scenarios covering the append/prepend/get/remove/insertAt/contains/indexOf/size surface, shared across all three languages, backed by a single head pointer and per-node next links.

• C# (.NET 8, xUnit, FluentAssertions 6.12.0) — walkthrough
• TypeScript (Node 20, Vitest 1.6, TS 5 strict) — walkthrough
• Python (3.11, pytest) — walkthrough

This kata ships in Agent Full-Bake mode at high gear. It bends the F1 rule slightly — a linked list is a data structure with identity and mutable state, not a pure input→output function — but the F1 discipline still holds: no test data builders, no domain value types beyond the list itself. Tests construct scenarios by calling the list’s own operations (append, prepend, insertAt), so the list is the SUT. The Node type is a module-private storage detail in every language, never exposed through the public surface. Out-of-range errors use the idiomatic exception per language (ArgumentOutOfRangeException, RangeError, IndexError) with a byte-identical message string. See the repo’s Gears section for when high gear is the right call.