C# LinkedList Remove: Delete Nodes Efficiently

When you need to remove elements from a LinkedList<T> in C#, the approach you choose depends on whether you already have a reference to the node or only the value. The c# linkedlist remove operations are straightforward, but their runtime cost varies significantly. This article explains each removal method, the underlying mechanics, and the performance tradeoffs you should consider before using a linked list in your own code.

Removing a Node by Reference (O(1))

The most efficient way to remove an element from a LinkedList<T> is to call Remove(LinkedListNode<T> node). This method expects a reference to the exact node you want to delete. Because the list is doubly linked, the node holds references to its previous and next neighbors. The removal operation simply updates those two neighbors to point to each other, bypassing the node entirely. This is a constant-time operation, O(1), regardless of the list size.

LinkedList<string> list = new LinkedList<string>();
list.AddLast("A");
list.AddLast("B");
list.AddLast("C");

LinkedListNode<string> nodeB = list.Find("B");
list.Remove(nodeB);

After this code runs, the list contains "A" and "C". The nodeB reference is no longer valid for use with this list; its List property becomes null. If you try to call Remove again with the same node, you'll get an InvalidOperationException because the node is not part of any list.

The key requirement here is that you must have a LinkedListNode<T> reference. You cannot pass a value directly to this overload. If you only have the value, you need to find the node first, which brings us to the next method.

Removing by Value: The O(n) Search

The Remove(T value) overload searches the list for the first occurrence of the specified value and removes it. The search uses the default equality comparer for the type T, which is EqualityComparer<T>.Default. This means for reference types it uses reference equality unless you override Equals and GetHashCode; for value types it uses the default structural comparison.

LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(10);
numbers.AddLast(20);
numbers.AddLast(30);

bool removed = numbers.Remove(20);

Here removed becomes true and the list now contains 10 and 30. If the value does not exist, Remove returns false and leaves the list unchanged. The runtime cost is O(n) because the method must traverse the list from the head until it finds a matching node. In the worst case, it checks every node.

This method is convenient, but for large lists with frequent removals by value, the linear scan can become a bottleneck. If you need to remove many elements by value, consider whether a HashSet<T> or a Dictionary<T, LinkedListNode<T>> would give you faster lookups while still allowing O(1) node removal.

Removing the First and Last Elements

LinkedList<T> provides two specialized methods: RemoveFirst() and RemoveLast(). Both operate in O(1) time because they directly manipulate the head or tail pointers. They are useful when you are using the list as a queue or a stack.

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

queue.RemoveFirst(); // removes "first"
queue.RemoveLast();  // removes "third"

Calling either method on an empty list throws an InvalidOperationException. Always check Count before calling these methods if the list might be empty.

Clearing the Entire List

The Clear() method removes all nodes from the list. It sets the head and tail references to null and resets the count to zero. Internally, the method also clears the links on each node to allow the garbage collector to reclaim their memory. This cleanup is O(n) because it must traverse every node to null out its references. In practice, for most applications the cost is negligible unless the list contains millions of items.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.AddLast(3);
list.Clear();
Console.WriteLine(list.Count); // 0

After Clear(), the list is empty and can be reused. Any LinkedListNode<T> references you held become invalid and should not be used.

Iterating and Removing: The Invalid Operation Pitfall

A common mistake is trying to remove elements while iterating with a foreach loop. The LinkedList<T> collection does not support modification during enumeration. If you call Remove inside a foreach, the enumerator becomes invalid and the next MoveNext call throws an InvalidOperationException.

// This throws InvalidOperationException
foreach (var item in list)
{
    if (condition)
        list.Remove(item);
}

To remove elements while iterating, you have two safe options. The first is to iterate backward using a while loop and the Last property:

LinkedListNode<int>? node = list.Last;
while (node != null)
{
    var previous = node.Previous;
    if (ShouldRemove(node.Value))
        list.Remove(node);
    node = previous;
}

This works because you save the previous node before removing the current one. The second option is to collect the nodes to remove in a separate list and then remove them after the iteration completes. The backward approach is more memory-efficient and is the pattern you'll see in most production code.

Performance and Memory Characteristics

Removing a node from a LinkedList<T> is O(1) only when you already hold a reference to the node. If you need to find the node by value, the search is O(n). This distinction is the most important factor when deciding whether a linked list is appropriate for your workload.

The memory overhead of a linked list is higher than a List<T> because each element is wrapped in a LinkedListNode<T> that stores two additional references. This also hurts cache locality because nodes are scattered across the heap, unlike an array-backed list where elements are contiguous. For scenarios where you frequently insert or remove elements in the middle of a large collection and you can maintain node references, the O(1) removal can outweigh the memory cost. For most other cases, List<T> offers better performance due to its contiguous storage and lower overhead.

The table below summarizes the removal methods and their complexities:

Note that Remove(node) does not throw if the node is null; it throws ArgumentNullException. It also throws InvalidOperationException if the node belongs to a different list or has already been removed.

When to Use LinkedList Over List for Removal

The decision to use LinkedList<T> instead of List<T> should be driven by your access patterns. If you frequently remove elements from the middle of a collection and you can store references to the nodes when you insert them, LinkedList<T> gives you O(1) removal. For example, a cache eviction policy that needs to move items to the front or back can benefit from a linked list combined with a dictionary mapping keys to nodes.

Dictionary<string, LinkedListNode<string>> index = new();
LinkedList<string> order = new();

void Add(string key)
{
    var node = order.AddLast(key);
    index[key] = node;
}

void Remove(string key)
{
    if (index.TryGetValue(key, out var node))
    {
        order.Remove(node); // O(1)
        index.Remove(key);
    }
}

This pattern is common in LRU cache implementations. Without the node reference, removal by value forces a linear search, and List<T> may be the better choice because its Remove method also does a linear search but benefits from better cache locality. In practice, if you are removing by value and the collection is not huge, the difference is often negligible. Profile your application to see whether the extra memory and pointer chasing of a linked list are justified by the removal speed you gain.