Efficient linked lists in .NET

Sometimes you need a collection that’s modified a lot: you insert, update and remove items. A List of T is then inefficient as it needs to constantly rearrange all other items. The LinkedList class might be a better candidate.

A linked list is a doubly-linked list. Each item has a Next and Previous pointer to look at which element comes right before and after a particular object in the list. A linked list is very efficient at inserting and deleting items in particular.

Initialisation:

LinkedList<int> intList = new LinkedList<int>();

There are multiple ways to add a new item: AddAfter, AddBefore, AddFirst, AddLast.

Adding a new item on the top of the list:

intList.AddFirst(2);

Putting 3 ahead of 2:

intList.AddFirst(3);

It’s not possible to directly pull out an item with an indexer, such as [2].

You can, however, iterate through the collection:

foreach (var i in intList)
{
}

You can get a reference of the first item with the First property:

LinkedListNode<int> firstItem = intList.First;

You can then insert an item after that:

intList.AddAfter(first, 5);

This will add 5 in between 3 and 2.

Inserting before the first item is equally easy:

intList.AddBefore(first, 5);

You can get to the last item… can you guess how? Through the Last property.

The First and Last properties do not return an int, or the type that you provided in place of T. It returns a LinkedListNode of type T, which is int in this case. This object has a Previous and Next properties:

LinkedListNode<int> firstItem = intList.First;
firstItem.Previous;
firstItem.Next;

It also has a Value property which returns the actual value of the LinkedListNode object.

Another way of iterating through the list is the following:

LinkedListNode<int> item = intList.First;
while (item != null)
{
    int val = item.Value;
    item = item.Next;
}

Removing items can be done with methods such as RemoveLast(), RemoveFirst(), Remove(item).