Linked Lists

A collection class that has no similar version with a nongeneric collection is LinkedList<T>. LinkedList<T> is a doubly linked list, where one element references the next and the previous one, as shown in Figure 10-3.

Figure 10-3

The advantage of a linked list is that if items are inserted in the middle of a list, the linked list is very fast. When an item is inserted, only the Next reference of the previous item and the Previous reference of the next item must be changed to reference the inserted item. With the List<T> and ArrayList classes, when an element is inserted all following elements must be moved.

Of course, there’s also a disadvantage with linked lists. Items of linked lists can only be accessed one after the other. It takes a long time to find a item that’s somewhere in the middle or at the end of the list.

A linked list can not just store the items inside the list; together with every item, the linked list must have information about the next and previous items. That’s why the LinkedList<T> contains items of type LinkedListNode<T>. With the class LinkedListNode<T>, you can get to the next and previous items in the list. The following table describes the properties of LinkedListNode<T>.

Open table as spreadsheet

LinkedListNode<T> Properties	Description
List	The property List returns the LinkedList<T> that is associated with the node.
Next	The property Next returns the node that follows the current node. The return type is again of type LinkedListNode<T>.
Previous	The property Previous returns the node before the current node.
Value	The property Value returns the item that is associated with the node. Value is of type T.

The class LinkedList<T> implements the interfaces ICollection<T>, IEnumerable<T>, ICollection, IEnumerable, ISerializable, and IDeserializationCallback. Members of this class are explained in the following table.

Open table as spreadsheet

LinkedList<T> Members	Description
Count	The property Count returns the number of items in the list.
First	The property First returns the first node in the list. The type returned is LinkedListNode<T>. Using this returned node, you can iterate through the other nodes of the collection.
Last	The property Last returns the last node in the list. Again, the type is LinkedListNode<T>.
AddAfter() AddBefore() AddFirst() AddLast()	With the AddXXX methods you can add items to the linked list. Use the corresponding Add method to add the item to a specific position inside the list. AddAfter() requires a LinkedListNode<T> object where you can specify the node after which the new item should be added. AddBefore() positions the new item before the node defined with the first parameter. AddFirst() and AddLast() just add the new item to the beginning or the end of the list. All these methods are overloaded to accept either an object to add of type LinkedListNode<T> or of type T. If you pass a T object, a new LinkedListNode<T> object is created.
Remove() RemoveFirst() RemoveLast()	The Remove(), RemoveFirst(), and RemoveLast() methods remove nodes from the list. RemoveFirst() removes the first item, and RemoveLast() removes the last item. The Remove() method requires an object that is searched and removes the first occurrence of this item in the list.
Clear()	The Clear() method removes all nodes from the list.
Contains()	The method Contains() searches for an item and returns true if the item is found, and false otherwise.
Find()	The Find() method searches the list from the beginning to find the item passed. The Find() method then returns a LinkedListNode<T>.
FindLast()	The FindLast() method is similar to Find(), the search just starts from the end of the list.

The sample application uses a linked list, LinkedList<T>, together with a list, List<T>. The linked list contains documents as in the previous example, but the documents have an additional priority associated with them. The documents will be sorted inside the linked list depending on the priority. If multiple documents have the same priority, the elements are sorted according to the time the document was inserted.

Figure 10-4 describes the collections of the sample application. LinkedList<Document> is the linked list containing all the Document objects. The figure shows the title and the priority of the documents. The title indicates when the document was added to the list: The first document added has the title One, the second document Two, and so on. You can see that the documents One and Four have the same priority, 8, but because One was added before Four, it is earlier in the list.

Figure 10-4

When new documents are added to the linked list, they should be added after the last document that has the same priority. A LinkedList<Document> collection contains elements of type LinkedListNode<Document>. The class LinkedListNode<T> adds Next and Previous properties to walk from one node to the next. For referencing such elements, the List<T> is defined as List<LinkedListNode<Document>>. For fast access to the last document of every priority, the collection List<LinkedListNode> contains up to 10 elements, each referencing the last document of every priority. In the upcoming discussion, the reference to the last documents of every priority is called the priority node.

From the previous example, the Document class is extended to contain the priority. The priority is set with the constructor of the class:

public class Document
{

   private string title;
   public string Title
   {
      get
      {
         return title;
      }
   }

   private string content;
   public string Content
   {
      get
      {
         return content;
      }
   }

   private byte priority;
   public byte Priority
   {
      get
      {
         return priority;
      }
   }

   public Document(string title, string content, byte priority)
   {
      this.title = title;
      this.content = content;
      this.priority = priority;
   }
}

The heart of the solution is the PriorityDocumentManager class. This class is very easy to use. With the public interface of this class new Document elements can be added to the linked list, the first document can be retrieved, and for testing purposes it also has a method to display all elements of the collection as they are linked in the list.

The class PriorityDocumentManager contains two collections.The collection of type LinkedList<Document> contains all documents. The collection of type List<LinkedListNode<Document>> contains references of up to 10 elements that are entry points to add new documents with a specific priority. Both collection variables are initialized with the constructor of the class PriorityDocumentManager. The list collection is also initialized with null:

public class PriorityDocumentManager
{
   private readonly LinkedList<Document> documentList;
// priorities 0..9
private readonly List<LinkedListNode<Document>> priorityNodes;

public PriorityDocumentManager()
{
   documentList = new LinkedList<Document>();
   
   priorityNodes = new List<LinkedListNode<Document>>(10);
   for (int i = 0; i < 10; i++)
   {
      priorityNodes.Add(new LinkedListNode<Document>(null));
   }
}

Part of the public interface of the class is the method AddDocument(). AddDocument() does nothing more than call the private method AddDocumentToPriorityNode(). The reason for having the implementation inside a different method is that AddDocumentToPriorityNode() may be called recursively, as you will see soon.

public void AddDocument(Document d)
{
   if (d == null) throw new ArgumentNullException("d");
   AddDocumentToPriorityNode(d, d.Priority);
}

The first action that is done in the implementation of AddDocumentToPriorityNode() is a check to see if the priority fits in the allowed priority range. Here, the allowed range is between 0 and 9. If a wrong value is passed, an exception of type ArgumentException is thrown.

Next, you check if there’s already a priority node with the same priority as the priority that was passed. If there’s no such priority node in the list collection, AddDocumentToPriorityNode() is invoked recursively with the priority value decremented to check for a priority node with the next lower priority.

If there’s no priority node with the same priority or any priority with a lower value, the document can be safely added to the end of the linked list by calling the method AddLast(). Also, the linked list node is referenced by the priority node that’s responsible for the priority of the document.

If there’s an existing priority node, you can get the position inside the linked list where the document should be inserted. Here, you must differentiate if a priority node already exists with the correct priority, or if there’s just a priority node that references a document with a lower priority. In the first case, you can just insert the new document after the position that’s referenced by the priority node. Because the priority node always must reference the last document with a specific priority, the reference of the priority node must be set. It gets more complex if just a priority node referencing a document with a lower priority exists. Here, the document must be inserted before all documents with the same priority as the priority node. To get the first document of the same priority, a while loop iterates through all linked list nodes, using the Previous property, until a linked list node is reached that has a different priority. This way, you know the position where the document must be inserted, and the priority node can be set.

private void AddDocumentToPriorityNode(Document doc, int priority)
{
   if (priority > 9 || priority < 0)
      throw new ArgumentException("Priority must be between 0 and 9");

   if (priorityNodes[priority].Value == null)
   {
      priority--;
      if (priority >= 0)
      {
         // check for the next lower priority
         AddDocumentToPriorityNode(doc, priority);
      }
      else // now no priority node exists with the same priority or lower
           // add the new document to the end
      {
         documentList.AddLast(doc);
         priorityNodes[doc.Priority] = documentList.Last;
      }
      return;
   }
   else // a priority node exists
   {
      LinkedListNode<Document> priorityNode = priorityNodes[priority];
      if (priority == doc.Priority)     // priority node with the same
                                        // priority exists
      {
         documentList.AddAfter(priorityNode, doc);
         
         // set the priority node to the last document with the same priority
         priorityNodes[doc.Priority] = priorityNode.Next;
      }
      else // only priority node with a lower priority exists
      {
         // get the first node of the lower priority
         LinkedListNode<Document> firstPriorityNode = priorityNode;
         while (firstPriorityNode.Previous != null &&
                firstPriorityNode.Previous.Value.Priority ==
                      priorityNode.Value.Priority)
         {
            firstPriorityNode = priorityNode.Previous;
         }

         documentList.AddBefore(firstPriorityNode, doc);

         // set the priority node to the new value
         priorityNodes[doc.Priority] = firstPriorityNode.Previous;
      }
   }
}

Now only simple methods are left for discussion. DisplayAllNodes() just does a foreach loop to display the priority and the title of every document to the console.

The method GetDocument() returns the first document (the document with the highest priority) from the linked list and removes it from the list:

   public void DisplayAllNodes()
   {
      foreach (Document doc in documentList)
      {
         Console.WriteLine("priority: {0}, title {1}", doc.Priority, doc.Title);
      }
   }

   // returns the document with the highest priority (that's first
   // in the linked list)
   public Document GetDocument()
   {
      Document doc = documentList.First.Value;
      documentList.RemoveFirst();
      return doc;
   }
}

In the Main() method the PriorityDocumentManager is used to demonstrate its functionality. Eight new documents with different priorities are added to the linked list, and then the complete list is displayed:

static void Main()
{
   PriorityDocumentManager pdm = new PriorityDocumentManager();
   pdm.AddDocument(new Document("one", "Sample", 8));
   pdm.AddDocument(new Document("two", "Sample", 3));
   pdm.AddDocument(new Document("three", "Sample", 4));
   pdm.AddDocument(new Document("four", "Sample", 8));
   pdm.AddDocument(new Document("five", "Sample", 1));
   pdm.AddDocument(new Document("six", "Sample", 9));
   pdm.AddDocument(new Document("seven", "Sample", 1));
   pdm.AddDocument(new Document("eight", "Sample", 1));

   pdm.DisplayAllNodes();
}

With the processed result you can see that the documents are sorted first by the priority and second by when the document was added:

priority: 9, title six
priority: 8, title one
priority: 8, title four
priority: 4, title three
priority: 3, title two
priority: 1, title five
priority: 1, title seven
priority: 1, title eight