Using linked lists in C# – Part I - 1

There is re-markedly little honor in building your own linked list class in C#. The standard libraries provide a solid implementation in the LinkedList generic class. The point of languages such as C# and Java is of course that code re-use should be the top priority, so why re-invent one of the most elementary wheels of computer science? In this post I will look at why you could use a linked list, and how they work.

If you don’t know in advance how many elements you are going to store a linked list is often a good solution. But what is a linked list anyway? I

In a linked list every element is linked to the next element in the list. If you would like to add a new element, you just allocate the memory for the new element and add it to the chain. So at the price of a little overhead (the need to keep links) you are prepared for situations that might grow from just 1 or 2 items to huge numbers of elements.

A common alternative is to allocate an array and allow it to grow when it reaches maximum capacity. This incurs a processing penalty as new memory needs to be allocated and the old array is copied to the new array.

For the linked list the penalty comes in access speed. In an array you can immediately access every element through my_array[1], my_array[1000] etc. In a linked list you have to start at the top and step through the whole list until the element is found. One optimization you can make here is to keep a counter of elements. If you know that the element you are looking for is closer to the end you could start at the end of the list, and count backwards.

Another benefit of linked lists is that it is possible to remove elements, something that is very hard to do in arrays. An array with many empty elements becomes wasteful and would require repacking or shrinking.

The following code implements a simple linked list using C# generics.

First we need to define the link elements in C# we use a class for this, not a struct. The reason being that classes in C# are passed by reference. If you make a copy of a reference, just the reference is copied, not the original item (which is just like using pointers in C and C++) If we were to use a struct each action would involve copying the whole item as structs are passed by value.

    class LinkedListElement<T>
    {
        public T Data;
        public LinkedListElement<T> Prev;
        public LinkedListElement<T> Next;

        public LinkedListElement(T Data)
        {
            this.Data = Data;
        }
    }

As you can see from the above definition we will be using a double-linked list: we keep a reference to both the previous and next item in the list. The benefit of this is that is it possible to travel through the list both in directions. In a single linked list, we would only have a reference to the next item, but not to the previous one. It also makes it easier to remove elements from the list.

    class LinkedList<T>
    {
        public LinkedListElement<T> Head;
        public LinkedListElement<T> Tail;

        public LinkedList()
        {
            Head = null;
            Tail = null;
        }
    }

In the double linked list we keep a reference to both the Head and Tail of the list. In an empty list, both the Head and Tail are NULL. If the list contains only one element, both Head and Tail point to the same element. For the Head element, the previous element is always NULL. For the Tail element the next element is always NULL.

        public void Add(T element)
        {
            LinkedListElement<T> Listelement = new LinkedListElement<T>(element);
            if (Head == null)
            {
                Head = Listelement;
            }
            else
            {
                Listelement.Prev = Tail;
                Tail.Next = Listelement;
            }
            Tail = Listelement;
        }

In adding to the list we need to check if the list is empty, if it is, the new element becomes the head.Otherwise we will add the new element to the end of the tail.

        public void Remove(LinkedListElement<T> element)
        {
            if (element == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");

            if (element == Head)
                Head = element.Next;
            if (element == Tail)
                Tail = element.Prev;

            if (element.Prev != null)
            {
                LinkedListElement<T> prev = element.Prev;
                prev.Next = element.Next;
            }
            if (element.Next != null)
            {
                LinkedListElement<T> next = element.Next;
                next.Prev = element.Prev;
            }
        }

Removing an element from the list involves fusing the previous element and next element together. And of course we need to check if it the element removed is the head or tail element.

The last basic action of using a list is to find if an element is stored in the list.

        public LinkedListElement<T> Find(T needle)
        {
            return Find(needle, Head);
        }

        public LinkedListElement<T> Find(T needle, LinkedListElement<T> start)
        {
            LinkedListElement<T> iterator = start;
            while (iterator != null)
            {
                if (iterator.Data.Equals(needle)) return iterator;
                iterator = iterator.Next;
            }
            return null;
        }

A simple iterator loops through the list comparing the linked list element to the one you are looking for, starting from the head of the list.

The full code of the linked list implementation is listed below. There is still much that it can be improved upon. C# provides a standard iterator mechanism, which is easy to implement and would make it possible to use our linked list in a forearch loop. That would also remove the need to expose so much of the classes internals to the outside world. A better implementation would hide the internal use of LinkedListElement completely.

In my next post I will show an implementation of Java inspired LinkedList class in C# which improves on the above problems.

using System;

namespace LinkedList_Simple
{

    class LinkedListElement<T>
    {
        public T Data;
        public LinkedListElement<T> Prev;
        public LinkedListElement<T> Next;

        public LinkedListElement(T Data)
        {
            this.Data = Data;
        }
    }

    class LinkedList<T>
    {

        public LinkedListElement<T> Head;
        public LinkedListElement<T> Tail;

        public LinkedList()
        {
            Head = null;
            Tail = null;
        }

        public void Add(T element)
        {
            LinkedListElement<T> Listelement = new LinkedListElement<T>(element);
            if (Head == null)
            {
                Head = Listelement;
            }
            else
            {
                Listelement.Prev = Tail;
                Tail.Next = Listelement;
            }
            Tail = Listelement;
        }

        public LinkedListElement<T> Next(LinkedListElement<T> element)
        {
            if (element == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");
            return element.Next;
        }

        public LinkedListElement<T> Prev(LinkedListElement<T> element)
        {
            if (element == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");
            return element.Prev;
        }

        public void Remove(LinkedListElement<T> element)
        {
            if (element == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");

            if (element == Head)
                Head = element.Next;
            if (element == Tail)
                Tail = element.Prev;

            if (element.Prev != null)
            {
                LinkedListElement<T> prev = element.Prev;
                prev.Next = element.Next;
            }
            if (element.Next != null)
            {
                LinkedListElement<T> next = element.Next;
                next.Prev = element.Prev;
            }
        }

        public LinkedListElement<T> Find(T needle)
        {
            return Find(needle, Head);
        }

        public LinkedListElement<T> Find(T needle, LinkedListElement<T> start)
        {
            LinkedListElement<T> iterator = start;
            while (iterator != null)
            {
                if (iterator.Data.Equals(needle)) return iterator;
                iterator = iterator.Next;
            }
            return null;
        }

    }

    class MainClass
    {
        public static void Main(string[] args)
        {
            LinkedList<string> myList = new LinkedList<string>();
            myList.Add("Hello World");
            myList.Add("Good day to you");
            myList.Add("Once upon a time in the west");

            LinkedListElement<string> search_it = myList.Find("Good day to you");

            if (search_it != null)
            {
                Console.WriteLine("Found: {0}", search_it.Data);
                myList.Remove(search_it);
            }
            else
                Console.WriteLine("Not found!");

            // Print the contents of the entire list
            LinkedListElement<string> print_it = myList.Head;

            int Lp = 0;
            while (print_it != null)
            {
                Console.WriteLine("{0} {1}", Lp++, print_it.Data);
                print_it = myList.Next(print_it);
            }

        }
    }

}