More About Generics

(Page 1 of 4 )

In this second part of a three-part series on using generics in C#, you'll learn how to use a linked list, and more. This article is excerpted from chapter four of the C# 3.0 Cookbook, Third Edition, written by Jay Hilyard and Stephen Teilhet (O'Reilly, 2008; ISBN: 059651610X). Copyright © 2008 O'Reilly Media, Inc. All rights reserved. Used with permission from the publisher. Available from booksellers or direct from O'Reilly Media.

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 theTodoItemclass, which is a simple container of two string propertiesNameandComment. 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 theLinkedList<T>class, the previous node is always accessed through thePrevious property, and the next node is always accessed through theNextproperty. The first node’sPreviousproperty in the linked list always returns anull value. Likewise, the last node’sNextproperty in the linked list always returns anullvalue.

Each node (represented by the boxes in Figure 4-1) in the linked list is actually a genericLinkedListNode<T>object. So aLinkedList<T>object is actually a collection ofLinkedListNode<T>objects. Each of theseLinkedListNode<T>objects contains properties to access the next and previousLinkedListNode<T>objects, as well as the object contained within it. The object contained in theLinkedListNode<T>object is accessed through theValueproperty. In addition to these properties, aLinkedListNode<T>object also contains a property calledList, which allows access to the containingLinkedList<T>object.

Items to be aware of withList<T>andLinkedList<T>:

1. Adding and removing nodes within aList<T>is, in general, faster than the same operation using aLinkedList<T>class.
   
2. AList<T>stores its data essentially in one big array on the managed heap, whereas theLinkedList<T>can potentially store its nodes all over the managed heap. This forces the garbage collector to work that much harder to manageLinkedList<T>node objects on the managed heap.
   
3. Note that theList<T>.Insert* methods can be slower than adding a node anywhere within aLinkedList<T>using one of itsAdd* methods. However, this is dependent on where the object is inserted into theList<T>. AnInsertmethod must shift all the elements within theList<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 theList<T>, the overhead of shifting the existing elements is negligible compared to the garbage collector overhead of managing theLinkedList<T>nodes objects. Another area where theList<T>can outperform theLinkedList<T>is when you’re doing an indexed access. With theList<T>, you can use the indexer to do an indexed lookup of the element at the specified position. However, with aLinkedList<T>class, you do not have that luxury. With aLinkedList<T>class, you must navigate theLinkedListNode<T>objects using thePreviousandNextproperties on eachLinkedListNode<T>, running through the list until you find the one at the specified position.
   
4. AList<T>class also has performance benefits over aLinkedList<T>class when searching for an element or node. TheList<T>.BinarySearchmethod is faster at finding elements within aList<T>object than its comparable methods within theLinkedList<T>class, namely theContains,Find, andFindLast methods.

Table 4-2 shows the comparison betweenList<T>andLinkedList<T>.

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

Action	Who Wins
Adding/Removing Nodes	List
Inserting nodes	LinkedList*
Indexed access	List
Node searching	List

See Also

The “LinkedListClass” topic in the MSDN documentation.

Next: 4.6 Creating a Value Type That Can Be Initialized to Null >>
 

More C# Articles
More By O'Reilly Media

Comments On: More About Generics

· This article is an excerpt from the book "C# 3.0 Cookbook, Third Edition," published...   >>> Post your comment now!

Buy this book...

This article is excerpted from chapter four of the C# 3.0 Cookbook, Third Edition, written by Jay Hilyard and Stephen Teilhet (O'Reilly, 2008; ISBN: 059651610X). Check it out today at your favorite bookstore. Buy this book now.