Working with LinkedListNode in C#

Working effectively with LinkedListNode<T> in C# requires understanding its role inside the LinkedList<T> collection and how to use node references safely. The examples below demonstrate traversal, insertion, removal, and the performance tradeoffs that matter when you choose a linked list.

In C#, LinkedListNode<T> is the fundamental building block of the LinkedList<T> collection. Each node holds a value and references to its predecessor and successor, forming a doubly linked list. Understanding how to work with LinkedListNode<T> directly gives you precise control over insertion, removal, and traversal without the overhead of index-based operations.

What LinkedListNode Represents in a Doubly Linked List

LinkedListNode<T> is a class that encapsulates a single element in a LinkedList<T>. It exposes three key properties: Value (the stored data), Previous (the preceding node or null if it's the first), and Next (the following node or null if it's the last). The List property points back to the owning LinkedList<T>.

Unlike List<T> which stores elements in a contiguous array, a linked list stores nodes independently in memory. This means you can insert or remove a node in O(1) time if you already have a reference to the node, but you cannot access elements by index. The node references themselves are what make these operations possible.

LinkedList<string> list = new LinkedList<string>();
list.AddLast("first");
list.AddLast("second");

LinkedListNode<string> secondNode = list.Last;
Console.WriteLine(secondNode.Value);       // second
Console.WriteLine(secondNode.Previous.Value); // first
Console.WriteLine(secondNode.Next == null);   // True

Accessing Node Values and Neighbors

The Value property is mutable, so you can update the data stored in a node without changing its position in the list. The Previous and Next properties are read-only and reflect the current state of the list. When a node is detached from a list, these properties become null.

A common mistake is to assume that Previous and Next remain valid after structural modifications. For example, if you remove a node from the middle of the list, its Previous and Next are set to null, and the adjacent nodes are linked together. If you still hold a reference to the removed node, you can no longer use it to traverse the original list.

LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(1);
numbers.AddLast(2);
numbers.AddLast(3);

LinkedListNode<int> node2 = numbers.Find(2);
numbers.Remove(node2);

Console.WriteLine(node2.Previous == null); // True
Console.WriteLine(node2.Next == null);     // True

Traversing a LinkedList Using LinkedListNode

Traversal is straightforward using the Next property from the first node. Because the list is doubly linked, you can also traverse backward from the last node using Previous. This is useful for reverse iteration without allocating a separate array.

LinkedList<string> tasks = new LinkedList<string>();
tasks.AddLast("compile");
tasks.AddLast("test");
tasks.AddLast("deploy");

for (LinkedListNode<string> node = tasks.First; node != null; node = node.Next)
{
    Console.WriteLine(node.Value);
}

// Backward traversal
for (LinkedListNode<string> node = tasks.Last; node != null; node = node.Previous)
{
    Console.WriteLine(node.Value);
}

Note that First and Last are properties on LinkedList<T> that return the corresponding node or null if the list is empty. The Find method returns the first node whose value equals the specified value using the default equality comparer for T, or null if not found. This is an O(n) operation because the list is not indexed.

Inserting and Removing Nodes with LinkedListNode References

One of the primary reasons to use LinkedListNode<T> is to perform constant-time insertions and removals when you have a reference to a specific node. The LinkedList<T> class provides methods like AddBefore, AddAfter, AddFirst, and AddLast, all of which accept a node reference or a value.

LinkedList<string> list = new LinkedList<string>();
LinkedListNode<string> root = list.AddFirst("root");
list.AddAfter(root, "child");
list.AddBefore(root, "parent");

// Result: parent, root, child

When you have a node, inserting before or after it is O(1) because the list only needs to adjust the Previous and Next references of the affected nodes. The same applies to removal: Remove(node) detaches the node in O(1). However, if you only have the value and need to find the node first, the total cost becomes O(n).

LinkedListNode<string> target = list.Find("child");
if (target != null)
{
    list.AddBefore(target, "grandchild");
}

Be careful when modifying a list while iterating with a for loop that uses node.Next. If you remove the current node, node.Next becomes null after removal, so you must capture the next node before removing the current one.

LinkedListNode<string> node = list.First;
while (node != null)
{
    LinkedListNode<string> next = node.Next;
    if (node.Value.StartsWith("temp"))
    {
        list.Remove(node);
    }
    node = next;
}

Performance Characteristics of LinkedListNode Operations

Understanding the performance of LinkedListNode<T> is essential for deciding when to use it. The key advantage is O(1) insertion and removal when you have the node reference. This contrasts with List<T>, where inserting or removing an element in the middle requires shifting subsequent elements, an O(n) operation.

However, finding a node by value is O(n) because the list is not indexed. Accessing an element by position is also O(n) since you must traverse from the head or tail. The memory overhead is higher than an array-based list because each node stores two references plus the object overhead.

These characteristics make LinkedList<T> suitable for scenarios where you frequently insert or remove nodes at arbitrary positions, especially when you already have node references. For most other cases, List<T> is more cache-friendly and can provide faster iteration because it uses contiguous memory.

When to Use LinkedListNode Instead of Other Collection Types

Choose LinkedList<T> and its nodes when your workload is dominated by insertions and deletions at known positions, and you do not need index-based access. LinkedList<T> supports O(1) operations at both ends, so it can be used to implement a deque. For a plain FIFO queue, Queue<T> is the simpler built-in option; for LIFO access, Stack<T> is purpose-built. LinkedList<T> is especially useful when you already hold node references and need to add or remove items at known positions.

Another scenario is building a custom LRU cache. You need to move an item to the front whenever it is accessed. With LinkedListNode<T>, you can remove the node and add it to the front in O(1) time, provided you store the node reference in a dictionary keyed by the item. This avoids the O(n) removal cost of a List<T>.

If you need to access elements by index frequently, or if your collection size is small and you value simplicity, List<T> is usually the better choice. The performance difference for small collections is negligible, and the reduced memory footprint and better cache locality of List<T> often win in practice.

Common Pitfalls with LinkedListNode References

One common pitfall is holding onto a node reference after the list has been modified. If you insert or remove other nodes, the Previous and Next of your referenced node may change, but the node itself remains valid. However, if you remove the node itself, it becomes detached and cannot be used to navigate the list. Always re-fetch nodes from the list when you need to traverse after structural changes.

Another issue is using Find in a loop that also modifies the list. Since each call starts from the First node, repeated calls can become O(n^2) if you remove many nodes this way. Instead, iterate once and collect the nodes to remove, then remove them after the iteration.

List<LinkedListNode<string>> toRemove = new List<LinkedListNode<string>>();
for (LinkedListNode<string> node = list.First; node != null; node = node.Next)
{
    if (node.Value == "obsolete")
    {
        toRemove.Add(node);
    }
}
foreach (LinkedListNode<string> node in toRemove)
{
    list.Remove(node);
}

Finally, remember that LinkedListNode<T> is a reference type. If you store nodes in a dictionary or another collection, the node's Value can be updated, but the node's position in the list is managed solely by the LinkedList<T>. Previous and Next are read-only; use the LinkedList<T> methods to restructure the list so those links stay consistent.