C# LinkedList AddFirst and AddLast: Usage and Performance

c# linkedlist addfirst addlast requires a clear understanding of the core syntax, runtime behavior, and practical implementation patterns demonstrated in the examples below.

When you need to insert elements at both ends of a collection in C#, LinkedList<T> provides AddFirst and AddLast methods that run in constant time. This article explains how to use them, how they behave, and when they are a better choice than List<T>.

The Role of AddFirst and AddLast in LinkedList<T>

LinkedList<T> is a doubly linked list. Each node holds a value and references to the previous and next nodes. Because the list tracks its head and tail explicitly, adding an element at either end does not require shifting other elements. The AddFirst method inserts a new node at the head, and AddLast appends a new node at the tail. Both operations are O(1) in time and do not trigger array resizing or copying, unlike List<T> which stores elements in a contiguous array.

Basic Usage of AddFirst and AddLast

Using these methods is straightforward. You create a LinkedList<T> instance and call AddFirst or AddLast with a value of type T. The methods return a LinkedListNode<T> that you can later use for removal or insertion relative to that node.

var list = new LinkedList<string>();

list.AddLast("middle");
list.AddFirst("first");
list.AddLast("last");

Console.WriteLine(string.Join(", ", list)); // first, middle, last

AddFirst and AddLast also accept a LinkedListNode<T> if you already have a node instance. This can be useful when you want to reuse a node or insert a node that was detached from another list.

var node = new LinkedListNode<int>(42);
list.AddFirst(node);

After insertion, the node's List property points to the current list, and its Previous and Next references are updated automatically.

How AddFirst and AddLast Differ from List<T> Insertions

List<T> exposes Insert(0, item) and Add(item) for front and back insertions. Insert(0, item) is O(n) because every existing element must be shifted to make room. Add(item) is amortized O(1) but can be O(n) when the internal array needs to grow. In contrast, LinkedList<T> guarantees O(1) for both AddFirst and AddLast, regardless of the number of elements. This difference becomes significant when you frequently add to the front of a large collection.

Another distinction is memory layout. List<T> stores elements contiguously, which improves cache locality during iteration. LinkedList<T> allocates a separate node object per element, so iteration involves pointer chasing and can be slower in practice despite the same O(n) traversal complexity. The choice between the two should depend on your dominant operation: if you need many front insertions or removals, LinkedList<T> wins; if you mostly iterate or index into the collection, List<T> is usually better.

Performance Characteristics of AddFirst and AddLast

The O(1) claim for AddFirst and AddLast holds because the list always has direct references to the head and tail nodes. When you call AddFirst, the method creates a new node, sets its Next to the current head, and updates the head reference. Similarly, AddLast sets the new node as the tail. No other nodes are touched. This behavior is consistent across all .NET versions that support LinkedList<T>.

Memory allocation is the only notable cost. Each insertion allocates a new LinkedListNode<T> object. If you are inserting millions of items, the allocation overhead may outweigh the benefit of avoiding array copies. In scenarios where the total number of elements is known and front insertions are rare, a List<T> with Insert might still be acceptable. For high-frequency front insertions, however, LinkedList<T> avoids the repeated shifting that would make List<T> impractical.

Edge Cases: Null Values and Empty Lists

LinkedList<T> allows null as a value for reference types. Calling AddFirst(null) or AddLast(null) is valid and creates a node with a null Value. The list itself is not null; only the node's value is. This can be useful when you need to represent a sentinel or a placeholder.

When the list is empty, AddFirst and AddLast behave identically: they create the first node, which becomes both head and tail. The node's Previous and Next are both null. If you call AddFirst on an empty list, the new node is the head; calling AddLast also makes it the tail. The order of operations matters only when the list already has elements.

Another edge case is adding a node that already belongs to another list. LinkedList<T> does not allow a node to be in two lists at once. If you attempt to add a node whose List property is not null, the method throws an InvalidOperationException. To move a node, you must first remove it from its current list.

Thread Safety and Concurrent Modifications

LinkedList<T> is not thread-safe. If multiple threads call AddFirst or AddLast concurrently, the internal state can become corrupted because the head and tail references are updated without synchronization. The documentation recommends wrapping the list in a lock or using a concurrent collection like ConcurrentQueue<T> if you need thread-safe operations. For read-only scenarios, you can safely iterate the list from multiple threads as long as no thread modifies it.

If you need to perform a series of insertions atomically, you must synchronize the entire sequence. For example, a lock around several AddFirst calls ensures that no other thread observes a partially updated list. The same applies to any combination of AddFirst and AddLast. There is no built-in optimistic concurrency control in LinkedList<T>.

When to Prefer LinkedList Over List (or Vice Versa)

Choose LinkedList<T> when your application frequently adds or removes elements at the front, and when you do not need random access by index. Typical use cases include implementing a queue with both ends active, an LRU cache where you move items to the front, or a history buffer where you trim from the tail. In these scenarios, the O(1) nature of AddFirst and AddLast directly improves throughput.

Choose List<T> when you need indexed access, when you iterate over the collection often, or when the collection size is small enough that the O(n) insertion cost is negligible. For a few hundred elements, the difference between List<T>.Insert(0, ...) and LinkedList<T>.AddFirst is rarely measurable. The decision should be based on the expected size and the ratio of insertions to reads. If you are unsure, profile your actual workload rather than relying on asymptotic complexity alone.

One final consideration is memory footprint. LinkedList<T> uses more memory per element because of the node object and the two references. If you are working with millions of small value types, the overhead can be substantial. In such cases, a List<T> or even an array may be more memory-efficient, even if you occasionally need to shift elements. The O(1) insertion guarantee is valuable, but it is not free.