---

Mastering the C# Doubly Linked List: The Complete Guide

A C# Doubly Linked List is a dynamic data structure where each element (node) contains data and two pointers: one to the next node and one to the previous. This bidirectional linkage allows for efficient O(1) insertions and deletions at both ends, making it ideal for implementing structures like Deques.

---

The Challenge: Building a Flexible Train Route

Imagine you're architecting a new train scheduling system. Your team needs to represent train routes—sequences of stations—in a way that's both efficient and flexible. A train route isn't static; stations are often added to the beginning or end of a line as the network expands, or removed due to track maintenance.

Your first instinct might be to use a simple C# List<T> or an array. But then you hit a roadblock. Adding a new station to the end of the route is fast. However, adding a new starting station to the beginning of the route is a performance nightmare. You'd have to shift every single existing station one position over to make room. For a route with hundreds of stations, this is unacceptably slow.

This is precisely the problem where a more sophisticated data structure shines. Enter the Doubly Linked List. It promises to solve this exact pain point, offering a robust and high-performance way to manage dynamic sequences. In this guide, we'll build one from scratch in C#, exploring its mechanics, benefits, and the elegant solution it provides for our train route problem, a core challenge in the kodikra.com C# learning path.

---

What Exactly Is a Doubly Linked List?

A Doubly Linked List is a linear collection of data elements, called nodes. Unlike arrays, where elements are stored in contiguous memory locations, nodes in a linked list can be scattered anywhere in memory. The magic lies in how they are connected.

Each node in a doubly linked list contains three pieces of information:

• The Data: The actual value we want to store (like a station number or a customer record).
• The Next Pointer: A reference to the next node in the sequence.
• The Previous Pointer: A reference to the previous node in the sequence.

This two-way (bidirectional) linkage is its defining feature. The first node is called the head, and its Previous pointer is null. The last node is the tail, and its Next pointer is null. This structure allows you to traverse the list forwards or backwards with equal ease.

Visualizing the Structure

Here’s a simple ASCII diagram illustrating the connections between nodes in a doubly linked list representing a train route with stations 9, 21, and 14.

  Head
   │
   ▼
┌───────────┐     ┌───────────┐     ┌───────────┐
│ Prev: null│     │ Prev:  ●  │◄────┤ Prev:  ●  │
│ Data: 9   ├─────► Data: 21  ├─────► Data: 14  │
│ Next:  ●  │     │ Next:  ●  │     │ Next: null│
└───────────┘     └───────────┘     └───────────┘
                                         ▲
                                         │
                                        Tail

Doubly Linked List vs. Arrays (List<T>)

The key difference lies in memory layout and operational complexity. A C# List<T> is backed by an array, which stores elements in a single, contiguous block of memory. This is great for fast lookups by index (O(1)) because the computer can calculate the memory address of any element instantly.

However, this contiguous nature is also its weakness. Inserting an element at the beginning or in the middle requires shifting all subsequent elements, an O(n) operation. A Doubly Linked List, with its pointer-based system, simply rewires a few references to insert a new node, making insertions and deletions at the ends an O(1) operation.

---

Why Use a Doubly Linked List in C#?

While .NET provides a built-in System.Collections.Generic.LinkedList<T> class, understanding how to build one from scratch is a fundamental skill for any serious C# developer. It solidifies your understanding of memory, references, and algorithm design.

The primary reason to choose a doubly linked list is for its exceptional performance in specific scenarios.

The Performance Advantage: O(1) Insertions and Deletions

For our train route system, the most common operations are adding or removing stations from the start (extending the line) or the end (the last stop). With a doubly linked list, these operations are incredibly fast, regardless of how many stations are on the route.

• Adding to the end (Push): Create a new node, point the old tail's Next to it, and the new node's Prev to the old tail. Update the tail reference. Constant time.
• Adding to the beginning (Unshift): Create a new node, point its Next to the old head, and the old head's Prev to the new node. Update the head reference. Constant time.

This efficiency makes it the perfect choice for implementing a Deque (Double-Ended Queue), a data structure that allows adding and removing elements from both the front and back.

Pros and Cons Analysis

No data structure is perfect for every job. It's crucial to understand the trade-offs.

Feature	Doubly Linked List	Array / List<T>
Add/Remove at Ends	✅ Excellent (O(1))	❌ Poor at Start (O(n)), Good at End (Amortized O(1))
Element Access (by index)	❌ Poor (O(n))	✅ Excellent (O(1))
Memory Usage	Higher (data + 2 pointers per node)	Lower (just data)
Cache Locality	Poor (nodes can be scattered in memory)	Excellent (contiguous memory benefits CPU cache)

Future Trend Note: In modern computing, CPU caches are king. The poor cache locality of linked lists can sometimes make them slower in practice than an array-based List<T>, even for tasks they are theoretically better at. Always benchmark your specific use case. However, for algorithms that fundamentally rely on efficient insertions/deletions at the ends, like implementing a Deque, they remain the superior architectural choice.

---

How to Implement a Deque with a Doubly Linked List in C#

Let's build our train route scheduler. We'll implement a Deque<T> class using a special kind of doubly linked list: a circular one. In a circular implementation, the head node's Prev pointer points to the tail, and the tail node's Next pointer points back to the head. This clever setup simplifies some operations by eliminating null checks for the head and tail.

Our solution will consist of two parts: an inner Element class to represent the nodes (stations) and the public Deque<T> class to manage the route.

Step 1: The Node (Element) Class

First, we define the building block of our list. This private nested class holds the station data and the crucial `Next` and `Prev` pointers. We'll use modern C# features like nullable reference types (Element?) to clearly state that these pointers can be null.

// This class is nested inside our Deque
private class Element
{
    public T Value { get; }
    public Element? Next { get; set; }
    public Element? Prev { get; set; }

    public Element(T value, Element? prev = null, Element? next = null)
    {
        Value = value;
        Prev = prev;
        Next = next;
    }
}

This is a straightforward class. Each `Element` is initialized with a value, and its `Prev` and `Next` pointers can be set during construction or later.

Step 2: The Deque<T> Class and Core Logic

Now for the main class. We only need one private field, head, to keep track of the entire list. In our circular implementation, if head is not null, we can find the tail by accessing head.Prev.

public class Deque<T>
{
    private Element? head;

    // We will implement the methods here...
}

Method 1: Push(T value) - Adding a Station to the End of the Route

The Push method adds a new element to the tail of the list. Here's the implementation, followed by a detailed walkthrough.

public void Push(T value) // Add to the end (tail)
{
    if (head == null)
    {
        // List is empty, create the first element.
        head = new Element(value);
        // Make it circular: it points to itself.
        head.Next = head;
        head.Prev = head;
    }
    else
    {
        // The current tail is the element just before the head.
        var tail = head.Prev!; 
        
        // Create the new element.
        // Its Prev is the old tail, its Next is the head.
        var newElement = new Element(value, tail, head);
        
        // Update the old tail's Next pointer.
        tail.Next = newElement;
        
        // Update the head's Prev pointer to the new tail.
        head.Prev = newElement;
    }
}

Code Walkthrough:

1. Empty List Check: If head is null, the list is empty. We create a new Element and assign it to head. To make it a valid circular list of one, we make its Next and Prev pointers point to itself.
2. Find the Tail: If the list is not empty, we find the current tail. In our circular design, the tail is always head.Prev. The ! (null-forgiving operator) tells the compiler we are certain head.Prev is not null here.
3. Create New Element: We instantiate our new Element. Its Prev pointer is set to the old tail, and its Next pointer is set to the head, inserting it correctly into the circular chain.
4. Rewire Pointers: This is the most critical step. We update the old tail's Next pointer to point to our newElement. Then, we update the head's Prev pointer to also point to our newElement, officially making it the new tail.

Here is an ASCII flow diagram illustrating the pointer rewiring for the `Push` operation on a list that already has a `head` and a `tail`.

    ● Start with a new value
    │
    ▼
  ┌──────────────────┐
  │ Find current tail│
  │ (tail = head.Prev) │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Create new_node  │
  │ new_node.Prev = tail │
  │ new_node.Next = head │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Update old tail  │
  │ tail.Next = new_node │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Update head's link │
  │ head.Prev = new_node │
  └─────────┬────────┘
            │
            ▼
    ● End

Method 2: Unshift(T value) - Adding a Station to the Beginning of the Route

Unshift adds an element to the front of the list, making it the new head. The logic is very similar to Push, but we also need to update the head reference itself.

public void Unshift(T value) // Add to the front (head)
{
    // The logic to add is identical to Push.
    Push(value);
    
    // The newly added element is the new tail.
    // To make it the head, we just move the head pointer back one step.
    if (head != null)
    {
        head = head.Prev!;
    }
}

Code Walkthrough:

This implementation is clever. It reuses the Push logic, which adds the new element as the new tail (just before the current head). Then, it simply updates the head pointer to be this new element (head.Prev), effectively making the new element the official start of the list. This elegantly handles both empty and non-empty list cases.

Method 3: Shift() - Removing a Station from the Beginning

Shift removes the head element and returns its value. The next element in the sequence becomes the new head.

public T Shift() // Remove from the front (head)
{
    if (head == null)
    {
        throw new InvalidOperationException("Cannot shift from an empty deque.");
    }

    var oldHead = head;
    
    if (head.Next == head)
    {
        // This is the last element in the list.
        head = null;
    }
    else
    {
        var newHead = head.Next!;
        var tail = head.Prev!;
        
        // Rewire the list to bypass the old head.
        newHead.Prev = tail;
        tail.Next = newHead;
        
        // Update the head pointer.
        head = newHead;
    }
    
    return oldHead.Value;
}

Code Walkthrough:

1. Empty Check: First, we guard against trying to remove an element from an empty list by throwing an exception.
2. Store Value: We get a reference to the current head so we can return its value later.
3. Last Element Check: If head.Next points to itself, we know there's only one element. Removing it means setting head to null.
4. Rewire Pointers: For a list with multiple elements, we identify the new head (head.Next) and the tail (head.Prev). We then link them together, effectively cutting the old head out of the circular chain.
5. Update Head: We update the head reference to point to the newHead.
6. Return Value: Finally, we return the value from the node we removed.

Method 4: Pop() - Removing a Station from the End

Pop removes the tail element. In our circular implementation, this means removing the element *before* the head.

public T Pop() // Remove from the end (tail)
{
    if (head == null)
    {
        throw new InvalidOperationException("Cannot pop from an empty deque.");
    }
    
    // In our circular list, the element to pop is the one before the head.
    // So, we can move the head pointer forward, then Shift.
    // This is a clever trick but can be less intuitive. Let's write a clearer version.
    
    var tail = head.Prev!;
    
    if (tail == head) // Only one element
    {
        head = null;
    }
    else
    {
        var newTail = tail.Prev!;
        newTail.Next = head;
        head.Prev = newTail;
    }
    
    return tail.Value;
}

Code Walkthrough:

1. Empty Check: As always, we handle the empty case.
2. Find the Tail: We get a reference to the tail, which is head.Prev.
3. Last Element Check: If the tail is the same as the head, there's only one element. We clear the list by setting head to null.
4. Rewire Pointers: We find the element that will become the new tail (tail.Prev). We then update its Next pointer to skip the old tail and point directly to the head. We also update the head's Prev pointer to point to this newTail.
5. Return Value: We return the value of the removed tail node.

This custom implementation from the kodikra module provides a powerful, efficient foundation for our train scheduling system, demonstrating a deep understanding of data structures. For more C# challenges, you can explore our full C# learning roadmap.

---

Where and When to Use Doubly Linked Lists

Beyond our train route example, doubly linked lists are the backbone of many common software features and data structures.

• Undo/Redo Functionality: Text editors and image manipulation software often use a doubly linked list to store a history of actions. Moving forward and backward through the list is equivalent to hitting "redo" and "undo".
• Browser History: The back and forward buttons in your web browser are a perfect real-world analogy. Each page you visit is a node, and you can traverse forwards and backwards through your session history.
• LRU (Least Recently Used) Caches: Caching systems need to evict old data to make room for new data. A doubly linked list is often used alongside a hash map to keep track of which items were used most recently, allowing for O(1) eviction of the least recently used item.
• Implementing Other Data Structures: They are the natural choice for building stacks, queues, and especially deques, as we've demonstrated.

The general rule is: if your application's primary workload involves frequent additions or removals from the beginning or end of a sequence, and you rarely need to access elements by a specific index, a doubly linked list is a strong candidate. If you need fast, random access, a List<T> is almost always better. For a deeper dive into C# collections and data structures, check out our complete C# language guide.

---

Frequently Asked Questions (FAQ)

What is the main difference between a singly and doubly linked list?

A singly linked list only has a `Next` pointer, allowing for forward traversal only. A doubly linked list has both `Next` and `Prev` pointers, allowing for traversal in both directions. This makes operations like removing the last element much more efficient (O(1) vs. O(n)).

Is the built-in LinkedList<T> in .NET a doubly linked list?

Yes. The System.Collections.Generic.LinkedList<T> class in the .NET Base Class Library is a general-purpose, high-performance implementation of a doubly linked list. It's an excellent choice for production code when you don't need to implement one from scratch.

Why not just use List<T> for everything?

List<T> is fantastic for general-purpose use due to its O(1) indexed access. However, its performance degrades to O(n) for insertions or deletions at the beginning of the list. For applications that behave like a queue or deque, a linked list provides superior and more consistent O(1) performance for those specific operations.

What is the time complexity of a doubly linked list?

• Access (by index): O(n)
• Search (by value): O(n)
• Insertion (at head/tail): O(1)
• Deletion (at head/tail): O(1)
• Insertion/Deletion (in middle, given the node): O(1)

How is memory managed with linked lists in C#?

C# is a managed language with a Garbage Collector (GC). When you remove a node from a list, you are simply removing all references to it. The GC will automatically detect that the node object is no longer reachable and will reclaim its memory during its next collection cycle. You do not need to manually deallocate memory.

Can a doubly linked list store null values?

Yes. If you declare your list as Deque<string?> or another nullable reference type, you can store null as a valid value within a node.

What is the advantage of a circular doubly linked list?

A circular implementation can simplify code by eliminating edge cases. You never have a `null` pointer for the head's `Prev` or the tail's `Next`, which can reduce the number of `if (head == null)` or `if (tail == null)` checks in your methods, sometimes leading to slightly cleaner code.

---

Conclusion: The Right Tool for the Right Job

The Doubly Linked List stands as a testament to classic computer science principles that remain incredibly relevant today. While not a one-size-fits-all solution, its O(1) performance for adding and removing elements at both ends makes it an indispensable tool for specific, performance-critical scenarios like our train route scheduling system.

By building one from scratch, you've not only solved a complex problem but also gained a much deeper appreciation for what happens under the hood of C#'s powerful collection types. You now understand the trade-offs between contiguous and node-based data structures, empowering you to make smarter architectural decisions in your future projects.

Disclaimer: All code examples in this article are written and tested against .NET 8 and C# 12. Syntax and features may differ in older versions of the framework.

---

Published by Kodikra — Your trusted Csharp learning resource.