Linked Lists C# Help

Acollection class that has no similar version with a non-generic collection is LinkedList<T>. LinkedList<T> is a doubly linked list, where one element references the next and the previous one, as shown.

Capture

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 be accessed only one after the other. It takes a long time to Find an item that’s somewhere in the middle or at the end of the list.

A linked list cannot just store the item 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>.

Capture

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.

Capture

Capture

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.

That describes the collections of the sample application. LinkedList<Document> is the linked list containing all the Documentobjects. 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 has the title 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.

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 <Documen.t>T.he 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 10elements, each referencing the last document of every priority. In the upcoming discussion, the reference to the last document 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;

}

}

Capture

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

}

}

{

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

}

}

The heart of the solution is the Priority Document Manager 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 Priority Document Manager 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 for adding new documents with a specific priority. Both collection variables are initialized with the constructor of the class Priority Document Manager. The list collection is also initialized with null:

Capture

Part of the public interface of the class is the method AddDocument ( ) . AddDocument () does nothing more than call the private method AddDocumentToPriori tyNode (). The reason for having the implementation inside a different method is that AddDocumentToPriori tyNode () 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 AddDocumentToPriori tyNode () is a check to see if the priority fitsin 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, AddDocumentToPriori tyNode () 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 caIling the method AddLas t ( ) . 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 whether 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.

Capture

Capture

Now only simple methods are left for discussion.DisplayAllNodes () just does a for each loop to display the priorityand the titleof every document to the console».

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

public void DisplayAllNodes()
f- –
foreach (Document doc in documentList)
(
Console.WriteLine(
‘priority: (O). title (l)’.
doc.Priority. doc.Title);
• t
II returns the document with the highest priority
II (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 Oocument(·two·, ‘Sample’,
3) );
pdm.AddDocument(new Document (‘three’,
•Sample’ , 4)1;
pdm.AddDocument(new Document(‘four’, ‘Sample’,
8) ) ;
pdm.AddDocument(new Document (‘five’, ‘Sample’,
1)) ; .
pdm.AddDocum~nt (new Document (‘six’, ‘Sample’,
9) ) ;
.•dm.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: I, title five
priority: I, title seven
priority: I, title eight

Posted on October 29, 2015 in Collections

Share the Story

Back to Top