C# 3.0 Cookbook, 3rd Edition

4.5. Using 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()
	{
	    Console.WriteLine("\r\n\r\n");

	    // Create TodoItem objects to add to the linked list
	    TodoItem i1 =
	        new TodoItem() { Name = "paint door", Comment = "Should be done third" }; 
	    TodoItem i2 =        
	        new TodoItem() { Name = "buy door", Comment = "Should be done first" }; 
	    TodoItem i3 =        
	        new TodoItem() { Name = "assemble door", Comment = "Should be done second" };
	    TodoItem i4 =        
	        new TodoItem() { Name = "hang door", Comment = "Should be done last" };

	    // Create a new LinkedList object
	    LinkedList<TodoItem> todoList = new LinkedList<TodoItem>();

	    // 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 first node in the linked list
	    Console.WriteLine("todoList.First.Value.Name == " + 
	        todoList.First.Value.Name);

	    // 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 of two string properties Name and Comment. The properties use the new Automatically Implemented Properties feature in C# 3.0 that allows you to declare properties, and the definition of the backing fields is generated automatically:

	/// <summary>
	/// Todo list item
	/// </summary>
	public class TodoItem
	{
	    /// <summary>
	    /// Name of the item
	    /// </summary>
	    public string Name { get; set; }

	    /// <summary>
	    /// Comment for the item
	    /// </summary>
	    public string Comment { get; set; }
	}

Discussion

The LinkedList<T> class in the .NET Framework is 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 reference 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.

Items to be aware of with List<T> and LinkedList<T>:

• Adding and removing nodes within a List<T> is, in general, faster than the same operation using a LinkedList<T> class.

• 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.

Table 4-2 shows the comparison between List<T> and LinkedList<T>.

Table 4-2. Performance comparison between List<T> and LinkedList<T>

Action	Who Wins
Adding/Removing Nodes	List<T>
Inserting nodes	LinkedList<T>
Indexed access	List<T>
Node searching	List<T>

See Also

The LinkedList<T> Class topic in the MSDN documentation.