Using linked lists in .NET with C#

Linked lists are very efficient if you want to insert and remove items in a collection frequently. Linked lists do not store their elements in contiguous regions in memory, like e.g. the List of T object. Instead elements in linked lists can be stored anywhere.

The elements are linked by their “next” and “previous” references. The first element will have a “next” pointer to the element that comes after that. The second element in turn will have a reference to the previous and next elements. The first element will of course only have a reference to the “next” element and “previous” will be null, whereas the last element will point to the previous element and “next” will be null. All elements in between will have two references. Such a linked list is also called a doubly linked list.

One big difference between linked lists and “normal” lists is that linked lists have no index accessors. You just cannot extract the element #3 for example without looping through the linked list and stopping at the third element.

Linked lists are represented by the generic LinkedList of T class in .NET. The elements are stored within objects of type LinkedListNode of T. Each node will keep track of its “next” and “previous” references. LinkedList provides 4 Add methods: AddFirst, AddLast, AddAfter and AddBefore.

AddFirst and AddLast will, as expected, add the element to the first and last position of the linked list. They also return a LinkedListNode object which come in handy when using the AddAfter and AddBefore methods. Those two require a LinkedListNode parameter that indicates the reference point of “before” and “after”.

Here’s an example of AddFirst and AddLast:

LinkedList<Guest> guestList = new LinkedList<Guest>();
LinkedListNode<Guest> john25 = guestList.AddFirst(new Guest() { Age = 25, Name = "John" });
LinkedListNode<Guest> barbara24 = guestList.AddFirst(new Guest() { Age = 24, Name = "Barbara" });
LinkedListNode<Guest> phil24 = guestList.AddFirst(new Guest() { Age = 24, Name = "Phil" });
LinkedListNode<Guest> fred23 = guestList.AddLast(new Guest() { Age = 23, Name = "Fred" });
LinkedListNode<Guest> hannah26 = guestList.AddFirst(new Guest() { Age = 26, Name = "Hannah" });
LinkedListNode<Guest> cindy27 = guestList.AddLast(new Guest() { Age = 27, Name = "Cindy" });

foreach (Guest guest in guestList)
{
	Debug.WriteLine("{0}, {1}", guest.Name, guest.Age);
}

…where Guest look as follows:

public class Guest
{
	public string Name { get; set; }
	public int Age { get; set; }
}

The code prints…

Hannah, 26
Phil, 24
Barbara, 24
John, 25
Fred, 23
Cindy, 27

Let’s see how we can insert other elements before and after:

LinkedList<Guest> guestList = new LinkedList<Guest>();
LinkedListNode<Guest> john25 = guestList.AddFirst(new Guest() { Age = 25, Name = "John" });
LinkedListNode<Guest> barbara24 = guestList.AddFirst(new Guest() { Age = 24, Name = "Barbara" });
LinkedListNode<Guest> phil24 = guestList.AddFirst(new Guest() { Age = 24, Name = "Phil" });
LinkedListNode<Guest> fred23 = guestList.AddLast(new Guest() { Age = 23, Name = "Fred" });
LinkedListNode<Guest> hannah26 = guestList.AddFirst(new Guest() { Age = 26, Name = "Hannah" });
LinkedListNode<Guest> cindy27 = guestList.AddLast(new Guest() { Age = 27, Name = "Cindy" });

LinkedListNode<Guest> ron21 = guestList.AddAfter(hannah26, new Guest() { Age = 21, Name = "Ron" });
LinkedListNode<Guest> mary26 = guestList.AddBefore(barbara24, new Guest() { Age = 26, Name = "Mary" });

foreach (Guest guest in guestList)
{
	Debug.WriteLine("{0}, {1}", guest.Name, guest.Age);
}

Here’s the printout:

Hannah, 26
Ron, 21
Phil, 24
Mary, 26
Barbara, 24
John, 25
Fred, 23
Cindy, 27

If you don’t have these references then you can use the Find method. Keep in mind that the linked list will need to search through the elements until it fins the first matching one. If you have several identical items in the list then Find will return the first one only.

By the way the result for Find will be based on equality. As Guest is a reference type it will need to implement the IEquatable interface so that the Find will know how to equate two Guest objects. Here’s an example:

public class Guest : IEquatable<Guest>
{
	public string Name { get; set; }
	public int Age { get; set; }

	public bool Equals(Guest other)
	{
		return Name.Equals(other.Name);
	}
}

The Find method will then correctly locate john25 by simply providing a Guest object with name = John:

LinkedListNode<Guest> find = guestList.Find(new Guest() { Name = "John" });

View all various C# language feature related posts here.

Advertisements

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

2 Responses to Using linked lists in .NET with C#

  1. Hugues says:

    Hi Andras,

    In what real-life scenario would you use a linked list instead of a regular one?

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ 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

HarsH ReaLiTy

A Good Blog is Hard to Find

Softwarearchitektur in der Praxis

Wissenswertes zu Webentwicklung, Domain-Driven Design und Microservices

the software architecture

thoughts, ideas, diagrams,enterprise code, design pattern , solution designs

Technology Talks

on Microsoft technologies, Web, Android and others

Software Engineering

Web development

Disparate Opinions

Various tidbits

chsakell's Blog

Anything around ASP.NET MVC,WEB API, WCF, Entity Framework & AngularJS

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: