C#
  Home arrow C# arrow More About Generics
ASP Free Forums 
.NET  
ASP  
ASP Code  
ASP.NET  
ASP.NET Code  
BrainDump  
C#  
Code Examples  
Database  
Database Code  
IIS  
Microsoft Access  
MS SQL Server  
Silverlight  
Visual Basic.NET  
Windows Scripting  
Windows Security  
XML  
Mobile Linux 
App Generation ROI 
IBM® developerWorks 
ASP Web Hosting  
ASP.NET Web Hosting 
Windows Web Hosting
 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us Get Paid 
Request Media Kit
Contact Us 
Site Map 
Privacy Policy 
Support 
 USERNAME
 
 PASSWORD
 
 
  >>> SIGN UP!  
  Lost Password? 
C#

More About Generics
By: O'Reilly Media
  • Search For More Articles!
  • Disclaimer
  • Author Terms
  • Rating: 5 stars5 stars5 stars5 stars5 stars / 1
    2008-12-18

    Table of Contents:
  • More About Generics
  • 4.6 Creating a Value Type That Can Be Initialized to Null
  • 4.7 Reversing the Contents of a Sorted List
  • 4.8 Making Read-Only Collections the Generic Way

  • Rate this Article: Poor Best 
      ADD THIS ARTICLE TO:
      Del.ici.ous Digg
      Blink Simpy
      Google Spurl
      Y! MyWeb Furl
    Email Me Similar Content When Posted
    Add Developer Shed Article Feed To Your Site
    Email Article To Friend
    Print Version Of Article
    PDF Version Of Article
     
     
    ADVERTISEMENT


    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.

    More C# Articles
    More By O'Reilly Media


       · This article is an excerpt from the book "C# 3.0 Cookbook, Third Edition," published...
     

    Buy this book now. 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.

    C# ARTICLES

    - Coding a CRC-Generating Algorithm in C
    - Cyclic Redundancy Check
    - Handling Methods and Functions
    - Destroying Objects in C#
    - Creating Objects in C-Sharp
    - Classes and Objects
    - Programming Languages: Managed versus Native
    - LINQ-to-MySQL with DbLinq in C#
    - Working with Dates and Times in C#
    - Generics, Dictionaries, and More
    - More About Generics
    - Working with C# Collections
    - Generics
    - C# and XML
    - Pointers and Arrays in C#





    © 2003-2009 by Developer Shed. All rights reserved. DS Cluster 4 Hosted by Hostway
    For more Enterprise Application Development news, visit eWeek