Using LinkedListNode for Node Manipulation in C

The LinkedListNode<T> class in C# represents an individual element within a LinkedList<T>, providing direct access to its stored value as well as references to adjacent nodes. By operating directly on LinkedListNode<T> references rather than values, you can execute insertions, removals, and relocations in \(O(1)\) constant time. This guide covers how to access nodes, traverse linked lists bi-directionally, insert elements relative to an existing node, and move nodes efficiently without unnecessary memory allocations.

Understanding LinkedListNode<T> Properties

A LinkedListNode<T> exposes four core properties:

• Value: Gets or sets the data stored within the node.
• Next: Returns a reference to the next LinkedListNode<T> in the sequence, or null if it is the last node.
• Previous: Returns a reference to the previous LinkedListNode<T>, or null if it is the first node.
• List: Returns the parent LinkedList<T> that owns the node, or null if the node is unattached.

Accessing Nodes and Bidirectional Traversal

To perform node-level manipulations, you must first obtain a node reference. You can retrieve nodes from the list using properties like First and Last, or methods like Find(). Once you have a node reference, you can traverse forward or backward without indexing.

using System;
using System.Collections.Generic;

var list = new LinkedList<string>();
list.AddLast("Alpha");
list.AddLast("Beta");
list.AddLast("Gamma");

// Retrieve reference to the first node
LinkedListNode<string> current = list.First;

// Forward traversal
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

// Backward traversal starting from the tail
LinkedListNode<string> tail = list.Last;
while (tail != null)
{
    Console.WriteLine(tail.Value);
    tail = tail.Previous;
}

Inserting Relative to a Target Node

Unlike arrays or List<T> where inserting an item requires shifting subsequent elements, inserting adjacent to a LinkedListNode<T> updates only pointer references. LinkedList<T> provides AddBefore and AddAfter methods that accept a target node and a new value or node.

LinkedListNode<string> betaNode = list.Find("Beta");

if (betaNode != null)
{
    // Insert a new value directly before 'Beta'
    list.AddBefore(betaNode, "Inserted-Before-Beta");

    // Insert a new node directly after 'Beta'
    var newNode = new LinkedListNode<string>("Inserted-After-Beta");
    list.AddAfter(betaNode, newNode);
}

Removing Nodes in \(O(1)\) Time

When calling list.Remove("value"), the linked list must search sequentially (\(O(N)\)) to locate the element. Passing the LinkedListNode<T> reference directly to list.Remove(node) bypasses the search step, removing the element in \(O(1)\) time.

LinkedListNode<string> nodeToRemove = list.Find("Beta");

if (nodeToRemove != null)
{
    // O(1) removal
    list.Remove(nodeToRemove);
}

Moving Nodes Without Reallocation

Because a LinkedListNode<T> is an object reference, you can detach it from one position and attach it to another within the same list without allocating new memory. This technique is commonly used in data structures such as Least Recently Used (LRU) caches.

// Move a node to the beginning of the list
LinkedListNode<string> targetNode = list.Last;

if (targetNode != null && targetNode != list.First)
{
    list.Remove(targetNode);     // Detach node (targetNode.List becomes null)
    list.AddFirst(targetNode);   // Reattach as head
}

A LinkedListNode<T> cannot belong to more than one list at a time. Attempting to add a node to a list while its List property is not null throws an InvalidOperationException. Always remove the node from its current list before inserting it into another position or list.