C# Generics Recipes—Implementing a Linked List

Microsoft .NET Framework, ASP.NET, Visual C# (CSharp, C Sharp, C-Sharp) Developer Training, Visual Studio

CSharp-Online.NET:Articles

C# Articles

C# Generics Recipes When and Where to Use Understand Generic Types Getting the Type Replacing the ArrayList Replace Stack, Queue Implement a Linked List Value Type to be Inited Reverse Sorted List Read-Only Collections Replace the Hashtable Using foreach Constrain Type Arguments Initialize Generic Variables

© 2006 O'Reilly Media, Inc.

Contents 1 4.6 Implementing a Linked List 1.1 Problem 1.2 Solution 1.3 Discussion 1.4 See Also

4.6 Implementing a Linked List

Problem

You need a linked data structure that allows you to easily add and remove elements.

Solution

Use the generic LinkedList<T> class. The following method creates a LinkedList<T> class, adds nodes to this linked list object, and then uses several methods to obtain information from nodes within the linked list:

public static void UseLinkedList( )
{
   // Create a new LinkedList object.
   LinkedList<TodoItem> todoList = new LinkedList<TodoItem>( );
 
   // Create TodoItem objects to add to the linked list.
   TodoItem i1 = new TodoItem("paint door", "Should be done third");
   TodoItem i2 = new TodoItem("buy door", "Should be done first");
   TodoItem i3 = new TodoItem("assemble door", "Should be done second");
   TodoItem i4 = new TodoItem("hang door", "Should be done last");
 
   // Add the items.
   todoList.AddFirst(i1);
   todoList.AddFirst(i2);
   todoList.AddBefore(todoList.Find(i1), i3);
   todoList.AddAfter(todoList.Find(i1), i4);
   // Display all items.
   foreach (TodoItem tdi in todoList)
   {
      Console.WriteLine(tdi.Name + " : " + tdi.Comment);
   }
 
   // Display information from the second node in the linked list.
   Console.WriteLine("todoList.First.Next.Value.Name == " 
      + todoList.First.Next.Value.Name);
 
   // Display information from the next to last node in the linked list.
   Console.WriteLine("todoList.Last.Previous.Value.Name == " 
      + todoList.Last.Previous.Value.Name);
}

The output for this method is shown here:

buy door : Should be done first
assemble door : Should be done second
paint door : Should be done third
hang door : Should be done last
todoList.First.Value.Name == buy door
todoList.First.Next.Value.Name == assemble door
todoList.Last.Previous.Value.Name == paint door

This is the TodoItem class, which is a simple container for two strings _name and _comment.

public class TodoItem
{
   public TodoItem (string name, string comment)
   {
      _name = name;
      _comment = comment;
   }
 
   private string _name = "";
   private string _comment = "";
 
   public string Name
   {
      get {return (_name);}
      set {_name = value;}
   }
 
   public string Comment
   {
      get {return (_comment);}
      set {_comment = value;}
   }
}

Discussion

The LinkedList<T> class in the .NET framework is considered a doubly linked list. This is because each node in the linked list contains a pointer to both the previous node and the next node in the linked list. Figure 4-1 shows what a doubly linked list looks like diagrammed on paper. Each node in this diagram represents a single LinkedListNode<T> object.

Figure 4-1. Graphical representation of a doubly linked list with three nodes

Notice that each node (i.e., the square boxes) contains a pointer to the next node (i.e., the arrows pointing to the right) and a pointer to the previous node (i.e., the arrows pointing to the left) in the linked list. In contrast, a singly linked list contains only pointers to the next node in the list. There is no pointer to the previous node.

In the LinkedList<T> class, the previous node is always accessed through the Previous property and the next node is always accessed through the Next property. The first node’s Previous property in the linked list always returns a null value. Likewise, the last node’s Next property in the linked list always returns a null value.

Each node (represented by the boxes in Figure 4-1) in the linked list is actually a generic LinkedListNode<T> object. So a LinkedList<T> object is actually a collection of LinkedListNode<T> objects. Each of these LinkedListNode<T> objects contains properties to access the next and previous LinkedListNode<T> objects, as well as the object contained within it. The object contained in the LinkedListNode<T> object is accessed through the Value property. In addition to these properties, a LinkedListNode<T> object also contains a property called List, which allows access to the containing LinkedList<T> object.

As far as performance is concerned, the List<T> class has benefits over using a LinkedList<T> class. Adding and removing nodes within a List<T> is, in general, faster than the same operation using a LinkedList<T> class. Comparing the List<T>.Add method to the Add* methods of the LinkedList<T> class, the performance hit isn’t due to the actual add operation, but due to the pressure that the LinkedList<T> puts on the garbage collector. A List<T> stores its data essentially in one big array on the managed heap, whereas the LinkedList<T> can potentially store its nodes all over the managed heap. This forces the garbage collector to work that much harder to manage LinkedList<T> node objects on the managed heap. Note that the List<T>.Insert* methods can be slower than adding a node anywhere within a LinkedList<T> using one of its Add* methods. However, this is dependent on where the object is inserted into the List<T>. An Insert method must shift all the elements within the List<T> object, at the point where the new element is inserted, up by one position. If the new element is inserted at or near the end of the List<T>, the overhead of shifting the existing elements is negligible compared to the garbage collector overhead of managing the LinkedList<T> nodes objects.

Another area where the List<T> can outperform the LinkedList<T> is when you’re doing an indexed access. With the List<T>, you can use the indexer to do an indexed lookup of the element at the specified position. However, with a LinkedList<T> class, you do not have that luxury. With a LinkedList<T> class, you must navigate the LinkedListNode<T> objects using the Previous and Next properties on each LinkedListNode<T>, running through the list until you find the one at the specified position.

A List<T> class also has performance benefits over a LinkedList<T> class when searching for an element or node. The List<T>.BinarySearch method is faster at finding elements within a List<T> object than its comparable methods within the LinkedList<T> class, namely the Contains, Find, and FindLast methods. This is due to the fact that the LinkedList<T> methods perform a linear search whereas the List<T>. BinarySearch method performs a binary search. In simple terms, a binary search takes advantage of the fact that the elements within the List<T> are sorted. This entails calling the Sort method before the BinarySearch (note that if any new elements are added, the Sort method must again be called before the BinarySearch method). Using this, the binary search will examine the middle element in the list and ask the question: is the object you’re looking for greater than the object at the current point in the list? If so, you know the target object is at an index somewhere in the list above the current index. If not, the object is at an index somewhere in the list below the current index. The binary search algorithm keeps asking this question until the object is found. In contrast, a linear search starts at the first element in a list and determines if that object is the one you are looking for. If not, the search continues to the next element in the list. This operation keeps repeating until the object is found in the list.

See Also

See the "LinkedList<T> Class" topic in the MSDN documentation.