Linked list in C#

Problem

The queue that stops the sending

The server sends emails from a queue. New ones go in at the back, urgent ones (a password reset) at the front, and the worker always takes the first. The code uses the ordinary list:

var emails = new List<string>();
emails.Add("invoice");
emails.Add("newsletter");
emails.Add("report");
emails.Insert(0, "password");
string next = emails[0];
emails.RemoveAt(0);
Console.WriteLine("Sending: " + next);
Console.WriteLine("Left: " + string.Join(", ", emails));

Sending: password
Left: invoice, newsletter, report

On Monday morning the newsletter to all customers fills the queue with 100,000 emails. The worker sends slower than usual, then almost stops, and the password reset emails are minutes late.

The reason: the list is a dynamic array. Taking the first one moves all the others one place forward, and an urgent one at the front moves all of them back. Sending 100,000 emails one after another is 99,999 + 99,998 + … + 1 = 4,999,950,000 moves, just to take the first one.

The idea

Nodes, head and tail

You already saw the node and inserting at the front in the lesson "Stack, queue and linked list": every element is a separate object with a value and an arrow Next to the following one. Here you write the whole class and work out what every operation costs.

The list keeps three things:

head: the first node. Every walk starts there.
tail: the last node. With it adding at the end does not go through the whole list.
the size, so it is not counted every time.

Both ends have to be right after every operation. The empty list has head and tail null. A list with one node has head and tail that point to the same node. Almost every bug in a linked list is a forgotten end: you remove the last one, and tail still points to it.

See it

Your own linked list

Here is the whole class. The nodes never move: every operation changes only arrows.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("the list is empty");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

Watch which arrows change on every operation:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

private Node head;
private Node tail;
private int size;

public string RemoveFirst()
{
    if (head == null)
    {
        throw new InvalidOperationException("the list is empty");
    }
    string value = head.Value;
    head = head.Next;
    if (head == null)
    {
        tail = null;
    }
    size--;
    return value;
}

public bool Remove(string value)
{
    Node prev = null;
    Node n = head;
    while (n != null && n.Value != value)
    {
        prev = n;
        n = n.Next;
    }
    if (n == null)
    {
        return false;
    }
    if (prev == null)
    {
        head = n.Next;
    }
    else
    {
        prev.Next = n.Next;
    }
    if (n == tail)
    {
        tail = prev;
    }
    size--;
    return true;
}

Step by step, in words

Three emails, each in its own node: the value and Next, the arrow to the following one. head points to the first, tail to the last.
AddFirst("password"): a new node, its Next points to the old first, and head moves to it. Two arrows, nothing moves: O(1).
AddLast("invite"): tail already knows the last, so nothing is walked. Its Next points to the new node, and tail moves: O(1).
RemoveFirst(): head moves to the next node. Nothing points to "password" any more, and its memory is freed by itself.
Remove("newsletter"): nodes have no index. n starts at head and walks until it finds it; prev stays one node behind. That is O(n).
prev.Next = n.Next: one arrow goes around "newsletter". "report" and "invite" do not move.
At the ends: two arrows, O(1). In the middle: one arrow, but you reach the place step by step, O(n).

var emails = new SimpleLinkedList();
emails.AddLast("invoice");
emails.AddLast("newsletter");
emails.AddLast("report");
emails.AddFirst("password");
emails.AddLast("invite");
Console.WriteLine(emails);
Console.WriteLine("Sending: " + emails.RemoveFirst());
emails.Remove("newsletter");
Console.WriteLine(emails);
Console.WriteLine("Position of report: " + emails.Find("report"));
Console.WriteLine("Emails: " + emails.Count);

password → invoice → newsletter → report → invite
Sending: password
invoice → report → invite
Position of report: 1
Emails: 3

RemoveFirst on an empty list throws InvalidOperationException, as LinkedList<T>.RemoveFirst does. ToString with override is what Console.WriteLine(emails) prints. Get is a method, not an indexer [i]: that way you see it reaches the element step by step. That is also why LinkedList<T> has no indexer.

Try it

Predict the output

Seven operations in a row. Watch which one is the last after the remove:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("the list is empty");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

var emails = new SimpleLinkedList();
emails.AddFirst("report");
emails.AddFirst("invoice");
emails.AddLast("invite");
emails.RemoveFirst();
emails.AddFirst("password");
emails.Remove("invite");
emails.AddLast("newsletter");
Console.WriteLine(emails);
Console.WriteLine("Emails: " + emails.Count);

Answer

password → report
Emails: 3

password → report → invite → newsletter
Emails: 4

password → report → newsletter
Emails: 3

The idea

What costs what: array against linked list

Operation	Dynamic array	Linked list
read by index	O(1)	O(n)
add at the front	O(n)	O(1)
add at the back	O(1) amortized	O(1) with tail
remove the first	O(n)	O(1)
remove the last	O(1)	O(n), doubly linked: O(1)
in the middle	O(n): moving	O(n): walking to the place

The last row is the trap. The relinking in the middle is O(1) by itself, but you reach the place from head, step by step. The linked list wins in the middle only if you already hold the node, for example because you just found it with a hash table.

There is a cost in memory too. The array keeps the values (or the references) next to each other. Every node is a separate object: the value, the arrow and the header the runtime keeps for every object. With small values a node takes several times more memory than a place in the array.

See it

Measure it

Inserting at the front: the dynamic array from the previous lesson against the linked list. We count the writes of elements: for the array the new one and every move, for the list only the new node. The arrows that change are two for every insert and do not grow with n.

Insert at the front O(n²)
Linked list: at the front O(n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Insert at the front	63	501,516	50,021,376	≈ 5,002,137,600
Linked list: at the front	10	1,000	10,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("the list is empty");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

With 10,000 emails the array makes 50,021,376 writes, and the linked list 10,000.

Now the other way round: reading every element by index, get(0), get(1) and so on to the end. We count the places you reach: in the array get(i) is one jump, and in the list it passes i + 1 nodes.

Array: get(i) for every i O(n)
Linked list: get(i) for every i O(n²)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Array: get(i) for every i	10	1,000	10,000	100,000
Linked list: get(i) for every i	55	500,500	50,005,000	≈ 5,000,500,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("the list is empty");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

With 10,000 elements the array makes 10,000 jumps, and the linked list 50,005,000 steps. A loop by index over a linked list is O(n²). Walk it with the loop along the arrows (or with for-each), as ToString does: that is O(n).

More precisely, if you are curious

The same numbers in your language, with counters in the class:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;
    public long Writes { get; private set; }
    public long Steps { get; private set; }

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        Writes++;
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("the list is empty");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        Steps++;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
            Steps++;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

foreach (int n in new[] { 10, 1000, 100000 })
{
    var list = new SimpleLinkedList();
    for (int i = 0; i < n; i++)
    {
        list.AddFirst((1001 + i).ToString());
    }
    Console.WriteLine($"at the front, n = {n}: {list.Writes} writes");
}
foreach (int n in new[] { 10, 1000 })
{
    var list = new SimpleLinkedList();
    for (int i = 0; i < n; i++)
    {
        list.AddLast((1001 + i).ToString());
    }
    for (int i = 0; i < n; i++)
    {
        list.Get(i);
    }
    Console.WriteLine($"get(i) for every i, n = {n}: {list.Steps} steps");
}

at the front, n = 10: 10 writes
at the front, n = 1000: 1000 writes
at the front, n = 100000: 100000 writes
get(i) for every i, n = 10: 55 steps
get(i) for every i, n = 1000: 500500 steps

Bench counts operations, not time. On the clock the difference when walking is even bigger in favour of the array because of the cache: the array is one block, and the nodes are scattered and every next one may not be in the cache. That is not measured here, only explained in the lesson on the dynamic array.

Try it

Find the bug

A colleague has written AddLast. Three emails at the back, and the list comes out like this:

var emails = new SimpleLinkedList();
emails.AddLast("invoice");
emails.AddLast("newsletter");
emails.AddLast("report");
Console.WriteLine(emails);
Console.WriteLine("Emails: " + emails.Count);

invoice → report
Emails: 3

The size is 3, and the emails are two. Which line is the bug on?

Pick the line with the bug.

Try it

Fill in

Remove has found the node n and the one before it, prev. Where does prev have to point now?

public bool Remove(string value)
{
    Node prev = null;
    Node n = head;
    while (n != null && n.Value != value)
    {
        prev = n;
        n = n.Next;
    }
    if (n == null)
    {
        return false;
    }
    if (prev == null)
    {
        head = n.Next;
    }
    else
    {
        prev.Next = ;
    }
    if (n == tail)
    {
        tail = prev;
    }
    size--;
    return true;
}

The idea

The doubly linked list

A singly linked list cannot remove the last one fast: it needs the one before the last, and nothing points back to it. A doubly linked list keeps two arrows in every node, Next and Prev. Then both ends are O(1), and a node you already hold is removed with four arrows, without searching for the previous one.

The cost is one more arrow in every node and more to relink on every operation.

LinkedList<T> in C# is doubly linked. The nodes are visible: AddLast returns a LinkedListNode<T> with Next and Previous, and Remove(node) removes the node in O(1).

The idea

Where the linked list really wins

For an ordinary queue the built-in one is better. Queue<T> is an array that keeps both ends without moving. How it works is in the lesson Stack and queue. The linked list wins when you already hold the node and have to take it out or move it:

An LRU cache. The shop keeps the last opened products in memory and throws out the one opened longest ago. A hash table finds the node of the product in O(1), and a doubly linked list moves it to the back. The oldest is always at the front.
History with back and forward. The browser and the editor keep the steps in a doubly linked list: back and forward are one arrow.
The lists in the operating system kernel. Processes and buffers carry their own arrows and are taken out of the list in O(1).

Here is an LRU with the built-in tools, the last three opened products:

class Recent
{
    private readonly int limit;
    private readonly LinkedList<string> order = new();
    private readonly Dictionary<string, LinkedListNode<string>> nodes = new();

    public Recent(int limit)
    {
        this.limit = limit;
    }

    public void Open(string product)
    {
        if (nodes.TryGetValue(product, out var node))
        {
            order.Remove(node);
        }
        else if (order.Count == limit)
        {
            nodes.Remove(order.First.Value);
            order.RemoveFirst();
        }
        nodes[product] = order.AddLast(product);
    }

    public override string ToString()
    {
        return string.Join(", ", order);
    }
}

var recent = new Recent(3);
foreach (string product in new[] { "laptop", "mouse", "monitor", "laptop", "keyboard" })
{
    recent.Open(product);
    Console.WriteLine(recent);
}

laptop
laptop, mouse
laptop, mouse, monitor
mouse, monitor, laptop
monitor, laptop, keyboard

Here is the classic way by hand: Dictionary finds the node, and LinkedList<string> takes it out and attaches it at the back. Both are O(1).

Exercise

A doubly linked list

Solve it in your editor.

Removing from both ends. Make a DoublyLinkedList: the node has Prev too. Write AddFirst, AddLast, RemoveFirst and RemoveLast, all in O(1). Keep both ends right: when the list becomes empty, both head and tail are null.

Add the three emails at the back and the password one at the front. Print the list, remove the last and the first, print it again. Remove two more from the back, print the size, then add the invite at the back:

password → invoice → newsletter → report
Last: report
First: password
invoice → newsletter
Emails: 0
invite

More tasks

The middle with two pointers. Find the middle node in one pass: one pointer goes one step at a time, the other two. When the fast one reaches the end, the slow one is in the middle.
A cycle in the list. A bug has attached the last node to one of the previous ones. Detect it with the same two pointers: if there is a cycle, the fast one catches up with the slow one.
Remove all occurrences. RemoveAll(string value) removes every node with that value in one pass and returns how many it removed. Do not forget tail.
LRU by hand. Make the LRU cache from the card above with your own doubly linked list and a Dictionary from product to node.

Test

Check yourself

1. A linked list has 1000 nodes, and you keep only head. How many nodes do you pass to read the element at index 999?500 on average, whatever the index1000: from head along the arrows to it1: the address is computed

2. Why is tail needed if head already holds the whole list?To know the sizeWithout it adding at the end goes through all the nodes: O(n) instead of O(1)Without it the first one cannot be removed

3. In a singly linked list with head and tail, what does removing the last one cost?O(n): you need the one before the last, and you reach it from headO(1): tail knows itO(log n)

4. Bench shows that inserting at the front makes n operations in a linked list and about n²/2 in a dynamic array. Why is the array still often faster when walking?The array compiles betterThe array is one block in memory and the cache reads it in lines; the nodes are scatteredThe linked list makes more comparisons

5. An LRU cache keeps the last 1000 opened products and throws out the one opened longest ago. What makes every open O(1)?A hash table aloneAn array sorted by timeA hash table that finds the node, and a doubly linked list in which the node moves to the back

Linked list

Cookies