Singly linked lists
Chain nodes together with references, implement add, find and remove, reverse a list in place, and learn the fast/slow pointer trick.
Next is null.
// Build 3 → 8 → 15 by handvar head = new Node<int>(3);head.Next = new Node<int>(8);head.Next.Next = new Node<int>(15); for (var n = head; n != null; n = n.Next) // the standard way to walk a list Console.Write($"{n.Value} → ");Console.WriteLine("null"); public class Node<T>{ public T Value; public Node<T>? Next; public Node(T value) => Value = value;}3 → 8 → 15 → null
Next references. Try the operations:
A complete singly linked list
public class SinglyLinkedList<T>{ private Node<T>? _head, _tail; public int Count { get; private set; } public void AddFirst(T value) // O(1) { var node = new Node<T>(value) { Next = _head }; _head = node; _tail ??= node; // first node is also the tail Count++; } public void AddLast(T value) // O(1) thanks to _tail { var node = new Node<T>(value); if (_tail is null) _head = _tail = node; else { _tail.Next = node; _tail = node; } Count++; } public bool Contains(T value) // O(n) { for (var n = _head; n != null; n = n.Next) if (EqualityComparer<T>.Default.Equals(n.Value, value)) return true; return false; } public bool Remove(T value) // O(n) to find, O(1) to unlink { Node<T>? prev = null; for (var n = _head; n != null; prev = n, n = n.Next) { if (!EqualityComparer<T>.Default.Equals(n.Value, value)) continue; if (prev is null) _head = n.Next; // removing the head else prev.Next = n.Next; // skip over n if (n == _tail) _tail = prev; // removing the tail Count--; return true; } return false; }}Array vs linked list
| Operation | Array / List<T> | Singly linked list |
|---|---|---|
O(1) | O(n) | |
O(n) | O(1) | |
O(1) amortised | O(1) with a tail reference | |
O(n) (shift) | O(1) | |
O(n) | O(n) | |
Classic: reverse a linked list
prev (already reversed part), current, and next (saved before we break the link).
static Node<int>? Reverse(Node<int>? head){ Node<int>? prev = null; var current = head; while (current != null) { var next = current.Next; // 1. remember the rest of the list current.Next = prev; // 2. turn this arrow around prev = current; // 3. step forward current = next; } return prev; // prev is the new head} var head = new Node<int>(1) { Next = new Node<int>(2) { Next = new Node<int>(3) } };for (var n = Reverse(head); n != null; n = n.Next) Console.Write(n.Value + " ");3 2 1
The fast and slow pointer trick
static bool HasCycle(Node<int>? head){ var slow = head; var fast = head; while (fast?.Next != null) { slow = slow!.Next; // 1 step fast = fast.Next.Next; // 2 steps if (slow == fast) return true; } return false; // fast fell off the end: no cycle}Middle(Node<int> head) that returns the value of the middle node in one pass, without counting the nodes first. For an even number of nodes return the second of the two middle nodes. Test with 1 → 2 → 3 → 4 → 5 and 1 → 2 → 3 → 4 → 5 → 6.
Show a hint
fast != null && fast.Next != null.
Show the solution
static int Middle(Node<int> head){ var slow = head; var fast = head; while (fast != null && fast.Next != null) { slow = slow.Next!; fast = fast.Next.Next; } return slow.Value;} static Node<int> Build(params int[] values){ Node<int>? head = null; for (int i = values.Length - 1; i >= 0; i--) head = new Node<int>(values[i]) { Next = head }; return head!;} Console.WriteLine(Middle(Build(1, 2, 3, 4, 5)));Console.WriteLine(Middle(Build(1, 2, 3, 4, 5, 6)));3 4
Remember
A linked list is a chain of nodes; each node holds a value and a Nextreference.Adding or removing at the front is O(1); reaching the k-th node is O(k). Keep a tail reference to make adding at the end O(1). Reversal and fast/slow pointers are the classic linked list techniques; always test empty, one-node, head and tail cases.