Introduction LinkedList is a general-purpose linked list. It supports enumerators and implements the ICollection interface.It is a true linked list with separate nodes of type LinkedListNode, so insertion and removal are O(1) operations. Lists that contain reference types perform better if a node and its value are created at the same time. Because the underlying nodes are exposed, it is possible to remove nodes and reinsert them, either in the same list or another list, as an O(1) operation with no allocations on the GC heap. The list also maintains an internal count so that getting the Count property is an O(1) operation; the count remains consistent if the list is used from a single thread. The LinkedList class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state. The design favors maintaining the integrity of the list, and in operations on a single thread a list remains consistent. The only multithreaded scenario supported by LinkedList is multithreaded read operations. In other multithreaded scenarios you must provide your own synchronization. Each node in the LinkedList is of the type LinkedListNode. Because the LinkedList is doubly linked, each node points forward to the Next node and backward to the Previous node. Nodes have links to the list so that invalid operations on the list do not put it in an inconsistent state.LinkedList accepts a null reference as a valid Value for reference types and allows duplicate values. LinkedList Generic Class represents a doubly linked list. The following code example demonstrates many features of the LinkedList class. The example creates an array of strings, then creates and populates a LinkedList of strings by passing the array of strings to the LinkedList constructor. The code example manipulates the resulting linked list using properties and methods of the LinkedList class, displaying the results between operations. Code: using System; using System.Text; using System.Collections.Generic; public class Example { public static void Main() { // Create the link list. string[] words = { "the", "apple", "falled", "over", "the", "dog" }; LinkedList<string> sentence = new LinkedList<string>(words); Display(sentence, "The linked list values:"); // Add the word 'today' to the beginning of the linked list. sentence.AddFirst("today"); Display(sentence, "Test 1: Add 'today' to beginning of the list:"); // Move the first node to be the last node. LinkedListNode<string> mark1 = sentence.First; sentence.RemoveFirst(); sentence.AddLast(mark1); Display(sentence, "Test 2: Move first node to be last node:"); // Change the last node be 'yesterday'. sentence.RemoveLast(); sentence.AddLast("yesterday"); Display(sentence, "Test 3: Change the last node to 'yesterday':"); // Move the last node to be the first node. mark1 = sentence.Last; sentence.RemoveLast(); sentence.AddFirst(mark1); Display(sentence, "Test 4: Move last node to be first node:"); // Indicate, by using parenthesis, the last occurrence of 'the'. sentence.RemoveFirst(); LinkedListNode<string> current = sentence.FindLast("the"); IndicateNode(current, "Test 5: Indicate last occurence of 'the':"); // Add 'lazy' and 'old' after 'the' (the LinkedListNode named current). sentence.AddAfter(current, "old"); sentence.AddAfter(current, "lazy"); IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':"); // Indicate 'apple' node. current = sentence.Find("apple"); IndicateNode(current, "Test 7: Indicate the 'apple' node:"); // Add 'big' and 'red' before 'apple': sentence.AddBefore(current, "big"); sentence.AddBefore(current, "red"); IndicateNode(current, "Test 8: Add 'big' and 'red' before 'apple':"); // Keep a reference to the current node, 'apple', // and to the previous node in the list. Indicate the 'dog' node. mark1 = current; LinkedListNode<string> mark2 = current.Previous; current = sentence.Find("dog"); IndicateNode(current, "Test 9: Indicate the 'dog' node:"); // The AddBefore method throws an InvalidOperationException // if you try to add a node that already belongs to a list. Console.WriteLine("Test 10: Throw exception by adding node (apple) already in the list:"); try { sentence.AddBefore(current, mark1); } catch (InvalidOperationException ex) { Console.WriteLine("Exception message: {0}", ex.Message); } Console.WriteLine(); // Remove the node referred to by mark1, and then add it // before the node referred to by current. // Indicate the node referred to by current. sentence.Remove(mark1); sentence.AddBefore(current, mark1); IndicateNode(current, "Test 11: Move a referenced node (apple) before the current node (dog):"); // Remove the node referred to by current. sentence.Remove(current); IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:"); // Add the node after the node referred to by mark2. sentence.AddAfter(mark2, current); IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (red):"); // The Remove method finds and removes the // first node that that has the specified value. sentence.Remove("old"); Display(sentence, "Test 14: Remove node that has the value 'old':"); // When the linked list is cast to ICollection(Of String), // the Add method adds a node to the end of the list. sentence.RemoveLast(); ICollection<string> icoll = sentence; icoll.Add("rhinoceros"); Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':"); Console.WriteLine("Test 16: Copy the list to an array:"); // Create an array with the same number of // elements as the inked list. string[] sArray = new string[sentence.Count]; sentence.CopyTo(sArray, 0); foreach (string s in sArray) { Console.WriteLine(s); } // Release all the nodes. sentence.Clear(); Console.WriteLine(); Console.WriteLine("Test 17: Clear linked list. Contains 'falled' = {0}", sentence.Contains("falled")); Console.ReadLine(); } private static void Display(LinkedList<string> words, string test) { Console.WriteLine(test); foreach (string word in words) { Console.Write(word + " "); } Console.WriteLine(); Console.WriteLine(); } private static void IndicateNode(LinkedListNode<string> node, string test) { Console.WriteLine(test); if (node.List == null) { Console.WriteLine("Node '{0}' is not in the list.\n", node.Value); return; } StringBuilder result = new StringBuilder("(" + node.Value + ")"); LinkedListNode<string> nodeP = node.Previous; while (nodeP != null) { result.Insert(0, nodeP.Value + " "); nodeP = nodeP.Previous; } node = node.Next; while (node != null) { result.Append(" " + node.Value); node = node.Next; } Console.WriteLine(result); Console.WriteLine(); } } This code example produces the following output: Code: the apple falled over the dog sentence->Contains("falled") = True today the apple falled over the dog the apple falled over the dog today the apple falled over the dog yesterday yesterday the apple falled over the dog the apple falled over (the) dog the apple falled over (the) lazy old dog the (apple) falled over the lazy old dog the big red (apple) falled over the lazy old dog the big red apple falled over the lazy old (dog) Exception message: The LinkedList node belongs a LinkedList. the big red falled over the lazy old apple (dog) Node "dog" is not in a list. the big red (dog) falled over the lazy old apple the big red dog falled over the lazy apple the big red dog falled over the lazy rhinoceros Copy the list to an array. the big red dog falled over the lazy rhinoceros
