Lesson 3 - Linked Lists in C# .NET

In the previous lesson, Lists with arrays in C# .NET, we introduced lists and described how lists that use internal arrays work in detail. In today's tutorial, we're going to focus on the second type of lists, which are linked lists.

Linked lists

The second approach for creating lists with a variable number of elements is to create a linked list. This way of doing things doesn't incorporate arrays and uses a different principle instead. The individual elements of the linked list are placed randomly in memory (they are no longer in a sequence) and all consecutive elements refer to each other. You could see it as a chain where the first element is connected to the second one, the second one to the third one, and so on. Here's a visual representation of the elements from the last lesson in a linked list:

This type of list is referred to as a singly linked list. If there isn't a real reason to save memory, you would usually reference the consecutive elements in both directions, e.g. the second to the first, and so on. In which case, we'd be dealing with a doubly linked list. The list, in this case, would look something like this:

With linked lists, we lose the ability to access any given element quickly by its index due to the fact that the elements are no longer all in a row in memory. There is no way to effectively jump right to the 100th element and read its value. If we wanted to access a specific element, we'd have to go from the first element to the second, from the second to the third, and go on until we reach the element we need. The time complexity of reading and writing at a given index depends on the number of elements in the List. However, if we don't have the need to index elements, this type of collection becomes very useful.

A while back, we said that we wouldn't be using arrays at all. We're not limited by the length of the list anymore and we can add or remove the elements at runtime as long as we have enough memory. We are also able to remove elements in the middle of the list or to add new elements between the existing ones. When using arrays, adding a new element in the middle was only possible if we shifted all of the elements on the right in order to make space for the new element. This cost us a considerable amount of time which was dependent on the number of elements. As for linked lists, all we have to do is reference a new element between two existing elements (the other elements aren't affected).

Simply put, we have an efficient manner of inserting and removing elements where the toll paid is inefficient access to indexes. This sort of thing is common in regards to data structures and algorithms, one thing in exchange for another

As you can tell, linked lists and lists that use internal arrays are very different. If we plan on accessing elements using random indexes often, choosing the linked list would be a disaster. On the contrary, if we needed to add or delete elements in the middle of the collection, it'd be a piece of cake for the linked list, but the List with an array would be extremely slow.

LinkedList

Linked lists are represented by the generic LinkedList collections in the .NET framework. This class uses doubly linked lists, so we won't be using singly linked lists in .NET. We could program them, but it wouldn't be worth it since it's harder to work with them and saving memory isn't very significant for our intents and purposes.

LinekedList doesn't contain our elements directly as List did. Instead, it stores elements of the LinkedListNode type. These are nodes which point to each other (or refer to, if you will) and have the Value property. This is where our element (the value) is stored, wrapped in the node. The node adds the references to the surrounding elements. Let's take a quick look at the other methods that the LinkedList provides compared to the previous List:

• AddAfter() - Adds a new element after the given element.
• AddBefore() - Adds a new element before the given element.
• AddFirst() - Adds a new element at the beginning of the list.
• AddLast() - Adds a new element at the end of the list.
• First - A property which returns the first element.
• Last- The property which returns the last element.
• RemoveFirst() - Removes the first element.
• RemoveLast() - Removes the last element.

Example

Let's try a similar example to the one that we used for the first List:

{CSHARP_CONSOLE}
LinkedList<int> list = new LinkedList<int>();
LinkedListNode<int> head = list.AddFirst(5);
list.AddAfter(head, 10);
Console.WriteLine(list.First.Value);
Console.WriteLine(list.First.Next.Value);
{/CSHARP_CONSOLE}

The program output:

Console application
5
10

We create a new linked list of the int type, add the first element, and store it as the head. Then, we add another element after the head. Finally, we print the first element and the element after the first element (the second one).

Here's and example of very quick addition and removal of elements:

{CSHARP_CONSOLE}
// initialization and filling of the linked list
LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> middle = list.AddLast(3);
list.AddLast(4);
list.AddLast(5);

// adding and deleting in the middle of the list
list.AddAfter(middle, 32);
list.AddAfter(middle, 31);
list.Remove(middle);

// printing the list
foreach (int i in list)
    Console.Write("{0}, ", i);

Console.ReadKey();
{/CSHARP_CONSOLE}

Output:

Console application
1, 2, 31, 32, 4, 5,

Working with linked lists is more complicated than working with Lists due to nodes, so we use Lists in most cases. We mainly use linked lists when we want to add and delete elements in the middle of the list, which would be very slow with the List class.

There's one last thing we have to cover before we completely leave Lists. In old, outdated source codes, you may stumble upon the StringCollection class. This is what people used before they could simply use List<string> back when collections weren't generic in .NET. Nowadays, there's no reason to use this class and cause more confusion.

Today's lesson was a bit shorter, but I didn't want to start off with a new topic and leave you hanging. Next time, Multidimentional arrays in C# .NET, we'll take a look at multidimensional arrays.

Did you have a problem with anything? Download the sample application below and compare it with your project, you will find the error easily.