Doubly and circular linked lists
Add a Prev reference to remove any node in O(1), use .NET’s LinkedList<T>, close the list into a circle, and build an LRU cache.
Next and Prev.
public class DNode<T>{ public T Value; public DNode<T>? Prev, Next; public DNode(T value) => Value = value;} // null ← A ⇄ B ⇄ C ⇄ D → null (head = A, tail = D)Prev, a node knows both neighbours. If you have a reference to a node, you can unlink it in O(1) without searching. Step through the pointer changes:
| Operation | Singly linked | Doubly linked |
|---|---|---|
O(1) | O(1) | |
O(1) | O(1) | |
O(n): need the node before the tail | O(1): tail.Prev | |
O(n): find its predecessor | O(1) | |
O(n) | ||
LinkedList<T> in .NET
LinkedList<T> is a doubly linked list. Its nodes are LinkedListNode<T> objects, and methods that take a node are O(1):
var playlist = new LinkedList<string>();playlist.AddLast("Intro");playlist.AddLast("Song A");var outro = playlist.AddLast("Outro"); // returns the node var b = playlist.AddBefore(outro, "Song B"); // O(1): we hold the nodeplaylist.AddFirst("Warm-up");playlist.Remove(b); // O(1) unlink by node Console.WriteLine(string.Join(" → ", playlist));Console.WriteLine($"First: {playlist.First!.Value}, Last: {playlist.Last!.Value}");Console.WriteLine($"Before Outro: {outro.Previous!.Value}");Warm-up → Intro → Song A → Outro First: Warm-up, Last: Outro Before Outro: Song A
Circular linked lists
Next points back to the first node (and in a doubly circular list, the first node’s Prev points to the last). There is no null at the end; you stop when you are back where you started. Circular lists are handy for things that go round and round: players taking turns, round-robin scheduling of tasks, or a repeating animation sequence.
// A circular singly linked list of playersvar a = new Node<string>("Asha");var b = new Node<string>("Bala");var c = new Node<string>("Chen");a.Next = b; b.Next = c; c.Next = a; // close the circle var turn = a;for (int i = 0; i < 7; i++){ Console.Write(turn.Value + " "); turn = turn.Next!; // never null}Asha Bala Chen Asha Bala Chen Asha
Sentinel (dummy) nodes
head or tail being null. A common trick is a permanent sentinel node that sits before the first real node (and often after the last). The list is never truly empty, so every insert and remove can use the same code with no special cases for the ends.
Real use: an LRU cache
Dictionary) and move items to the front or drop the oldest quickly (a doubly linked list). Together, every operation is O(1).
var cache = new LruCache(2);cache.Put("A", "Tower A.ifc");cache.Put("B", "Tower B.ifc");Console.WriteLine(cache.Get("A")); // A is now most recentcache.Put("C", "Tower C.ifc"); // full: evicts BConsole.WriteLine(cache.Get("B") ?? "B was evicted");Console.WriteLine(cache.Get("C")); public class LruCache{ private readonly int _capacity; private readonly Dictionary<string, LinkedListNode<(string Key, string Value)>> _map = new(); private readonly LinkedList<(string Key, string Value)> _order = new(); // front = most recent public LruCache(int capacity) => _capacity = capacity; public string? Get(string key) { if (!_map.TryGetValue(key, out var node)) return null; _order.Remove(node); // O(1): we have the node _order.AddFirst(node); // mark as most recently used return node.Value.Value; } public void Put(string key, string value) { if (_map.TryGetValue(key, out var existing)) _order.Remove(existing); else if (_map.Count == _capacity) { var oldest = _order.Last!; // least recently used _order.RemoveLast(); _map.Remove(oldest.Value.Key); } _map[key] = _order.AddFirst((key, value)); }}Tower A.ifc B was evicted Tower C.ifc
LinkedList<int> with the numbers 1 to 8, remove every second node (2, 4, 6, 8) in a single pass, using node references so each removal is O(1).
Show a hint
var node = list.First;. Save node.Next before removing it, because a removed node’s Next becomes null.
Show the solution
var list = new LinkedList<int>(Enumerable.Range(1, 8)); var node = list.First;while (node?.Next != null){ var toRemove = node.Next; // the second of each pair node = toRemove.Next; // move on first: toRemove.Next becomes null after Remove list.Remove(toRemove); // O(1) by node} Console.WriteLine(string.Join(" ", list));1 3 5 7
Remember
A doubly linked list adds a Prevreference, so any node you hold can be removed in O(1)..NET’s LinkedList<T>is doubly linked; only the node-based methods are O(1).In a circular list the last node links back to the first; stop when you return to the start. Dictionary + doubly linked list = LRU cache with O(1) get and put.