C# LinkedLists

C# Linked List

The Linked List is a fundamental data structure in computer programming. The idea is that each element is linked to the next element and the only way to access an element is to do a linear scan through the list until you find the element you are looking for or you reach the end of the list.

llist.png 10.52K 85 downloads

Each of the rectangles represents one element in a list. We see that for each element in the list there are two components: some data and a reference to the next element in the list. Without this reference we would have no way to find the next element in the list. We need some convention to represent the last reference in the list. We can technically use anything but it makes sense to use null to represent the reference. When we find a null reference we know we are at the end of the list.

This diagram suggests that the implementation of the list is a class with two fields a data field and a reference of type Node. This is known as a self-referential field. A sample node class would like this:

class Node {
    int Data;
    Node Next;
 }

We are going to look at the LinkedList in the C# System.Collections.Generic namespace and various methods the linked list can perform.
The two main benefits of a linked list is it is really fast to add an element at any arbitrary position in the list and it is easy to delete any element at any position in the list. We will look at functions on LinkedLists and make notes on their implementations and efficiencies.

In the above list if we want to add the node with value 4 after 5 we simply create a new node with value 4 and make it point to the node with value 3. Then we take the node with value 5 and update it’s next reference to point to the new node. Simple.

Creating Linked Lists

The above Node class only works with integers. The C# implementation, however, makes use of generics. Generics are a fairly simple concept that allows you to write one implementation that works with any type.
For instance,

 LinkedList<string> l1 = new LinkedList<string>();

Is a linked list that holds just strings data. This second example:

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

Is a linked list that just holds integer data.

Add To Front of List

This is one of the easiest operations we can perform. We simply use the AddFirst function like this:

 l2.AddFirst(5);
 l2.AddFirst(3);
 l2.AddFirst(4);

This function creates a new node and adds it to the front of the list.
It is interesting to note how this function would be implemented. Imagine your list is defined using the Node class above.

 
public static Node AddFirst(int elem, Node linkedList) {       
      var node = new Node {Data = elem, Next = linkedList};      
     return node;
 }

The {} notation is an object initializer to set all the fields of the object. This code simply makes a new node and makes it’s next reference equal to the reference to the first item in the old list.

AddBefore, AddAfter and AddLast

These functions are used to add an element before another element, after another element and at the end of the list. They are not as easy to implement as the AddFirst function. The key to these functions is that you first have to do a search to locate a node to aid in the insertion first.

In case of AddBefore, you have to do a search for a particular value always keeping a reference to the node before it. Once you do this it is a two-step process to add the new node. Update the next field of the node behind the node you are adding in front of to reference the new node. Then the new node’s next field has to be set to reference the node you adding in front of.

AddAfter is a very similar process to AddBefore. You can make these functions a lot easier to implement if you update the node class to maintain a reference to the element immediately after it and the element immediately before it. According to MSDN tutorials the AddAfter function has 0(1) running time. For those who do not know about algorithm analysis this means that the function has running time that does not depend on the size of the input (in this case the number of items in the list). What this means is the LinkedListNode class is implemented as I described with a reference to the previous and next element in the list. The AddLast function also has 0(1) running time.

AddLast is much easier to implement and it will slightly resemble AddFirst but the only difference is this function will require a full iteration of the linked list every time it is called to find the last element. To make this function much more efficient you can update each node to have a reference to the last node in the list.

Examples:

l2.AddBefore(new LinkedListNode<int>(5), 5);
  l2.AddBefore(new LinkedListNode<int>(5), 3);
  l2.AddLast(new LinkedListNode<int>(4));

The one thing that I do not like about this is that making the parameter of type LinkedListNode slightly reveals how the list is implemented. Ideally the function should be able to be called like this l2.AddBefore(5, 5);

Search Functions

Any function that does a search will always be linear time in the worst case as we have to examine every element in the list. There is no way around this. This is one of the trade-offs for the ability to quickly add and remove nodes.

The Contains function

l2.Contains(5);

This function simply looks in the list to see if it has the element 5 in it. This is fairly easy to implement:

public bool Contains(Node lst, int elem){      
        while(lst != null) {         
                 if(lst.Data == elem) return true;    
                 lst = lst.Next;      
        }
        return false;  
}

There are two find functions which return the first node that contains a value or null if it does not exist. These functions are find and findLast. Find returns the first node that contains the element. The FindLast function then returns the last node that contains the element. The FindLast function is obviously the most complicated function of the two to implement.

We can write find as follow:

  
      public Node find(Node lst, int elem) { 
         while (lst != null){       
                    if(lst.Data == elem) return new Node {Data = elem};   
                    lst = lst.Next;     
         }      
         return null; // Traversed the entire list. Not found.  
     }

Examples of using the built-in functions:

l2.Find(5); // returns first node with value 5 
 l2.FindLast(3); // returns last node with value 3

Deleting Nodes

These operations are also going to be 0(1) time because of how the list is implemented. To delete a node we need the previous node and the next node in the list. We simply update the node immediately before the node we are deleting to point to the node after the node we are deleting.

To remove a node we simply use this function:

L2.Remove(5)

This code removes the first node containing the value 5 if one exists. It returns a Boolean indicating if the value was removed or not. So if this function returns false then the node did not exist.

Two more functions exist and these are RemoveFirst and RemoveLast which remove the first element and the last element respectively. These functions are 0(1) time and are ridiculously simple to write.

An implementation of RemoveFirst:

 
public Node RemoveFirst(Node lst) {      
        Node next = lst.Next;     
        lst.Next = null;      
        lst = next;      
        return lst;  
}

The idea is we set the next reference of the first node to null so it no longer references the rest of the list. Before we do this, however, it is important to save the next node otherwise the rest of the list is lost in memory forever. Then once we update the pointer we simply return next which is the rest of the list.