LinkedList<T> is the BCL's doubly linked list. Each element sits in its own node that holds a reference to the next node and the previous node, which makes inserting or removing in the middle cheap as long as you already have the node in hand. This lesson covers how the list is shaped, how to navigate and mutate it through LinkedListNode<T>, and when it actually pays off over List<T>, which is the usual choice in .NET.

A doubly linked list is a chain of small objects called nodes. Each node carries three things: a value, a reference to the node after it, and a reference to the node before it. The list type holds a reference to the first node and the last node, and exposes operations that splice nodes into or out of the chain.

In LinkedList<T>, the node type is LinkedListNode<T>. The list type is LinkedList<T>. Both come from System.Collections.Generic and live in the standard BCL, no NuGet package needed.

That picture is the whole mental model. Each LinkedListNode<T> knows its value and its two neighbors. The LinkedList<T> instance knows the first node and the last node. There's no contiguous block of memory, no index, no resizable buffer. Just a chain of small objects connected by references.

The Next reference of the last node is null, and the Previous reference of the first node is also null. That's how you know you've hit the end when walking the chain in either direction.

Here's the same picture in code. You build it the way you'd expect:

AddLast attaches a node to the end of the chain, so the three calls leave you with Apple, Bread, Cereal in that order. Count is a stored field on the list, so reading it is O(1). First and Last are properties that return the first and last LinkedListNode<T> respectively, or null when the list is empty. The ! after cart.First is the null-forgiving operator, used here because the compiler can't tell from this code that the list is non-empty.

A few things are worth being explicit about before going further. The element type T can be any type, value or reference. There is no Capacity and no resize step, because the list grows one node at a time. There is no indexer (no cart[1]), and the reason for that is covered in its own section below.

There are three ways to make a LinkedList<T>. The first is the empty constructor, which gives you a list of zero nodes:

An empty list has Count == 0 and both First and Last are null. There are no nodes yet, so there's nothing for those properties to point at.

The second is the constructor that takes any IEnumerable<T> and copies the elements in order:

The constructor walks the source sequence once and calls AddLast for each element, in order. After it finishes, the list contains a node per element, with the first source element at First and the last source element at Last. This works with any IEnumerable<T>, so arrays, List<T>, query results, and other linked lists all work as sources.

The third is the protected constructor used by serialization, which you almost never call directly. Skip it for normal code.

The list does not pre-allocate a capacity, and there is no equivalent to List<T>.Capacity. Each node is a separate heap object created when you add it, and each one is reclaimed by the garbage collector when no references remain.

That pattern (empty list, then bulk-load) is common when the source isn't an IEnumerable<T> itself, for example when you're reading rows one at a time from a database, a file, or an API.

Most of the operations on LinkedList<T> either return a LinkedListNode<T> or take one as a parameter. The node is the handle you use to navigate, insert near, or remove a specific element. It's worth getting comfortable with its shape before using the list's methods.

A LinkedListNode<T> has four read-only properties:

Value is the only one you can write to, and that lets you change the element in a node without unlinking and relinking. Next, Previous, and List are wired up by the list itself when you add the node, and they update automatically when nodes around it move.

The first node's Value is Apple. Its Next is the second node, whose value is Bread. Its Previous is null, because there's no node before it. Its List is the cart instance, the list that owns it. ReferenceEquals confirms the node knows which list it lives in.

You can write to Value to update an element in place:

The chain didn't change, only the value inside the first node. Its Next, Previous, and List are the same references they were before. That distinction matters when you hold a reference to a node and don't want it invalidated by a small edit.

A node knows which list it belongs to, and the list enforces that a node lives in exactly one list at a time. If you try to add a node that's already in a list to a different list, you get an InvalidOperationException:

cartA.AddLast("Apple") returns the node it created and attached. Passing that same node to cartB.AddLast fails, because the node still belongs to cartA. To move it, you'd remove it from cartA first, which detaches it (sets node.List to null), and then add it to cartB. The list keeps these invariants on every mutation, so you can trust the node's List property.

A detached node, one you create directly with new LinkedListNode<T>(value), has all three of Next, Previous, and List set to null. It isn't part of any chain until you pass it to a list operation that splices it in.

First, Last, and Count are the three properties you'll use the most. They all run in constant time, because the list stores them as fields and updates them on every add and remove.

(The first two lines are the same because null.ToString() prints as empty in interpolation. You'd normally guard against the null with a check, the line is just showing the property values directly.)

When the list holds exactly one node, First and Last point to the same node. There's no separate "single-element" shape, the node just happens to have both Next and Previous set to null.

ReferenceEquals(cart.First, cart.Last) returns true because there's only one node. Its Next and Previous are both null. That's the base case to keep in mind when you write code that walks the list.

Count is a field, so it doesn't iterate. This is different from LINQ's Count() method on IEnumerable<T>, which has to walk every element on collections that don't implement ICollection<T>. LinkedList<T> implements ICollection<T>, so even when you call cart.Count() through LINQ, it uses the fast path.

If you check First against null, you've also implicitly checked whether the list is empty. They're equivalent: cart.First is null is true if and only if cart.Count == 0.

There are four "add" methods. AddFirst puts a new node at the start. AddLast puts a new node at the end. AddBefore and AddAfter insert a new node next to a node you already have in hand. Each one has two overloads: one that takes a value and one that takes a LinkedListNode<T> you've already constructed.

The value overload is the one you'll use most. It builds the node for you and returns it, so you can keep the reference if you want to insert near it later:

AddLast("Bread") creates a node and puts it at the end of the (currently empty) list, so it's also the first node. The variable bread holds a reference to that node. AddFirst("Apple") then splices a new "Apple" node before it. AddLast("Cereal") splices a new node after it. The chain is now Apple, Bread, Cereal.

AddBefore and AddAfter need a node to anchor on. They take the anchor as the first argument and the value (or node) as the second:

Both inserts target the bread node directly. AddBefore(bread, "Apple") splices "Apple" so that its Next is bread and bread.Previous becomes the new "Apple" node. AddAfter(bread, "Cereal") does the symmetric thing on the other side.

The picture for AddAfter looks like this. Before:

After AddAfter(bread, "Cereal"):

The list just rewires three references: bread.Next to point to the new "Cereal" node, the new node's Previous to point back to bread, and the new node's Next set to whatever bread.Next used to be (here null, since bread was the last node). No other nodes are touched. That's the property linked lists are famous for: insertion is constant time once you have the right node.

The node overload of each method is for when you've already built a node yourself or detached one from another list:

The node was constructed in detached form (its List was null). After AddAfter splices it in, its List now points at cart. The value, next, and previous fields all update along with the splice.

A common slip is to try to add a node that's already in another list. That throws InvalidOperationException, as the earlier example showed. The simple rule is "one node, one list at a time."

If you want to do many inserts at one end, prefer the value overload of AddLast (or AddFirst). It's less code to read and there's no separate new LinkedListNode<T>(...) allocation visible at the call site (it still happens, just inside the call).

The list exposes four ways to remove nodes. RemoveFirst and RemoveLast drop the node at the corresponding end. Remove(LinkedListNode<T>) removes a specific node you already have. Remove(T) removes the first node whose value equals the argument.

RemoveFirst and RemoveLast are the cheap ones. They run in O(1) because the list knows where both ends are:

After RemoveFirst, the old first node is detached and "Bread" becomes the new first. After RemoveLast, "Cereal" is detached and "Bread" is now both first and last, with Count == 1.

Calling either method on an empty list throws InvalidOperationException:

That's worth defending against. A quick if (cart.Count > 0) cart.RemoveFirst(); is enough when you don't want the exception path.

Remove(LinkedListNode<T>) removes a specific node. It's the fastest "remove from the middle" operation in the BCL when you already have the node, because the list only has to rewire two references:

The "Bread" node is unlinked. Apple's Next now points to Cereal, Cereal's Previous points back to Apple, and the removed node's List, Next, and Previous are all null. The node is detached and can be reused (it's eligible for adding to a different list, or back into the same one later).

If you pass a node that belongs to a different list, the method throws:

The list checks node.List against itself before doing anything. This is one of the protections the List property buys you, you can't accidentally splice a node out of the wrong chain.

Remove(T) is the value-based overload. It walks the list from First, comparing each node's value to the argument using the default equality comparer, and removes the first match:

The first "Bread" is removed and the method returns true. The second "Bread" is still in the list, because only the first match is removed. If no match is found, the method returns false and the list is unchanged.

The pattern that makes linked lists worth using is "hold a node reference, then remove it later in constant time." The classic example is an LRU cache, covered at the end of this lesson. The classic anti-pattern is treating it like List<T> and doing cart.Remove(somevalue) in a loop, which is O(n) per removal.

These three methods walk the list and look for a value. They're the only way to locate a node by value in a LinkedList<T>, and they're all linear in the size of the list.

Find(T) returns the first node whose value equals the argument, or null if no node matches:

The first call finds the first "Bread" node. Its Next is the "Cereal" node. The second call walks the whole list, finds no match, and returns null. The return type is LinkedListNode<T>?, so the ? and the is not null check are how you handle the miss case.

FindLast(T) does the same thing in reverse. It walks the list backward from Last and returns the last node whose value matches. It exists because, if you have two matching values and you want the second one, walking from Last is faster than walking from First past the first match:

Find returned the second-position "Bread" node, whose Next is "Cereal". FindLast returned the fourth-position "Bread" node, whose Next is null because it sits at the end. Two different nodes with the same value, located from opposite ends.

Contains(T) returns just true or false. Internally it calls Find and checks for null:

If you need the node afterwards (to remove it, insert near it, or read its neighbors), call Find directly. Contains throws away the node reference and you'd have to walk again, which doubles the work.

The equality used by all three methods comes from EqualityComparer<T>.Default. For strings that means ordinal equality. For value types it means the type's Equals implementation. For reference types it usually means reference equality, unless the type overrides Equals. If you have a custom record or class and want value-based equality, override Equals and GetHashCode on the type itself, the list always uses the default comparer and there's no overload that takes a custom comparer.

You can do cart[1] on a List<T>. You can't do it on a LinkedList<T>. There's no this[int] indexer on the type, and the omission is on purpose.

The reason is that getting the i-th node in a linked list requires walking i nodes from one of the ends. There's no way to jump to the middle of the chain, because no node knows its position, only its neighbors. So an indexer would advertise an operation that looks like O(1) but is actually O(i). Making people walk the list explicitly keeps the cost visible.

If you do need positional access, you walk:

That loop walks target steps from First. For position 2 with a 4-element list it's three reads (the start node, then two Next traversals). For position 9,000 in a 10,000-element list it's 9,001 reads. The cost grows with the position, and writing the walk by hand makes that growth obvious.

If your code does that a lot, you're using the wrong collection. List<T> is O(1) for indexed access and almost certainly faster overall for read-heavy workloads. Linked lists pay off when the index isn't the access pattern, when you have a node reference instead.

Two related things follow from the no-indexer rule. The first is that you can't ask for "the element at position 5" without paying for the walk. The second is that there's no IndexOf(T) method either, since "the position of this value" would require the same walk. You can implement it yourself by walking and counting, but the BCL deliberately doesn't offer the shortcut.

When you really do want positional access and can't switch collections, LINQ's ElementAt(int) works on any IEnumerable<T>, including LinkedList<T>. Under the hood it does the same walk you'd write by hand:

That's a convenience, not a speedup. ElementAt on a non-indexable source iterates until it reaches the requested position, so the cost is the same O(n).

foreach is the standard way to read every element. LinkedList<T> implements IEnumerable<T> (see the _IEnumerable & ICollection_ lesson), and its enumerator walks from First to Last following Next references:

That iterates the values in forward order. Each step of the loop reads one node, hands its Value to the loop variable, and moves to its Next. When Next is null, the enumerator finishes.

If you need the node itself, not just the value (for example to read the previous node mid-iteration), walk the chain manually with a local variable:

This pattern is the manual equivalent of foreach, but it gives you access to the node itself, so you can read Previous, hold the reference, or check node.List. The loop condition node is not null handles the end of the chain, and the node = node.Next step is what foreach does internally.

Backward iteration is the same pattern, walking Previous from Last:

Starting at Last and following Previous gives the values in reverse order. This is one of the things LinkedList<T> does for free that a single-linked list wouldn't, since each node knows both neighbors. With List<T> you'd either iterate by index in reverse or call Reverse() (which allocates).

A modifying-while-iterating warning applies the same way it does to any BCL collection. If you call Add* or Remove* during a foreach, the enumerator's version field stops matching the list's, and the next move throws InvalidOperationException:

The mutation is detected on the next call to MoveNext(), not at the mutation site. To remove during a walk, switch to a manual node loop. It's safe because you advance the cursor before the splice removes the current node:

The trick is to capture node.Next before removing node, because after removal node.Next is null (the node is detached). This walk-and-remove pattern is O(n) overall, doing constant-time work at each step, which is one of the cases where LinkedList<T> is genuinely a good fit.

Clear() removes every node:

After Clear(), Count is 0 and both First and Last are null. The list is back to its empty-constructor state. If you held a reference to a node before the clear, that node's List, Next, and Previous are all null afterward, the node is detached.

Internally, Clear walks the list and sets each node's List, Next, and Previous to null. The work is O(n), not O(1), because every node has to be detached. The nodes themselves become garbage as soon as no external references remain, and the GC reclaims them on the next collection.

The difference between Clear() and "make a new empty list" matters when other code holds a reference to the same LinkedList<T>. Clear() empties the list in place, and any other reference to the same instance sees zero elements. Assigning a new LinkedList<T> to your local variable only changes that local, the original list is unaffected.

This is the section that decides whether to use LinkedList<T> at all. In .NET, the answer is "usually no, use List<T>," and being precise about why is what makes the rare yes-cases obvious.

The summary table:

List<T> looks slower for middle inserts, but the constant factors swing things in its favor for most workloads. Its backing array sits in a contiguous block, so iterating it is sequential memory access that the CPU's prefetcher handles well. LinkedList<T> scatters nodes across the heap, and walking the chain is a series of pointer dereferences that can't be prefetched. For a list of a few thousand elements, walking a List<T> is often faster than walking a LinkedList<T> even though both are O(n), because the per-step cost is smaller.

Memory is also lopsided. A List<int> with 1,000 elements uses one array of 4,000 bytes plus the list object. A LinkedList<int> with 1,000 elements uses 1,000 separate node objects, each around 40 bytes on a 64-bit runtime, so roughly 40,000 bytes plus the list object. The linked list takes about 10x the memory for the same data.

So when does LinkedList<T> win? Two patterns:

The first is "I have many inserts or removes in the middle of the collection, and I have a reference to the node already." Calling cart.Remove(node) is O(1). The equivalent for List<T> is cart.RemoveAt(index), which is O(1) to find the position but O(n) to shift the remaining elements down. If your workload is "snip out this element, splice in that one" and you're holding the node, LinkedList<T> is the right shape.

The second is "I need to walk from a node to its neighbors quickly." A node's Previous and Next are constant-time. With List<T> you'd have to know the index, and finding the index from a value is another walk. This is what makes linked lists fit data structures like LRU caches, where you want to move an item to the front whenever it's touched.

Here's a sketch of an LRU cache built on top of LinkedList<T> and Dictionary<TKey, LinkedListNode<TValue>>:

The cache uses the dictionary to find the node for a key in O(1), then uses the linked list to move that node to the front or evict the tail node, both also O(1). Neither structure on its own would give all three of "lookup by key, move within order, evict the oldest" in constant time. The pair gives all three.

Another fitting use is an undo or redo stack where each entry might be inserted between two operations later, and where you keep node references so you can splice the new entry in without copying anything around it. The shape is "every mutation is local to a node I'm holding," which is exactly what linked lists optimize for.

If your workload doesn't match either of those patterns, prefer List<T>. The cache locality alone usually outweighs the asymptotic advantage of LinkedList<T> for typical sizes, and the memory cost is real.

The next lesson covers Dictionary<TKey, TValue>, which is the BCL's hash table. It gives you O(1) average-case lookup by key, which is exactly the missing piece in the LRU cache from this lesson, the dictionary plus the linked list together give the best of both shapes.