Linked List

Level: Intermediate 30–60 min

Concepts: Data StructuresAlgorithmsEdge Cases

---

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.