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).

Advertisements

About Andras Nemes
I'm a .NET/Java developer living and working in Stockholm, Sweden.

One Response to Efficient linked lists in .NET

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

ultimatemindsettoday

A great WordPress.com site

Elliot Balynn's Blog

A directory of wonderful thoughts

Robin Sedlaczek's Blog

Developer on Microsoft Technologies

Softwarearchitektur in der Praxis

Wissenswertes zu Webentwicklung, Domain-Driven Design und Microservices

Technology Talks

on Microsoft technologies, Web, Android and others

Software Engineering

Web development

Disparate Opinions

Various tidbits

chsakell's Blog

WEB APPLICATION DEVELOPMENT BEST PRACTICES WITH MICROSOFT STACK & ANGULAR

Cyber Matters

Bite-size insight on Cyber Security for the not too technical.

Guru N Guns's

OneSolution To dOTnET.

Johnny Zraiby

Measuring programming progress by lines of code is like measuring aircraft building progress by weight.

%d bloggers like this: