Linked List

A linked list is a data structure made up of a chain of elements, where one element points to the next element, from start to finish. Each element is called a node, and each node contains data and an address to the next node in the list. The first node in the linked list is referenced with the property First, and the last node in the linked list is referenced with the property Last.

There are different types of linked lists. A linked list can be a singly linked list, where each node points to a single node that is next in the list. A doubly linked list has two pointers for each node, where one points to the next node in the list, and the other points to the previous node in the list.

The linked list that is available in the C# library is a doubly linked list that comes from Systems.Collections.Generic. This line of code initializes a new instance of LinkedList that is empty. The ‘T’ is a placeholder for the data type that you want to use in the linked list. The linked list is a generic class, which you will learn more about later in the course. Just know that any data type can be used inside the linked list, and you replace the ‘T’ with the data type you want to use.

LinkedList myLinkedList = new LinkedList();

An array can be used to populate a linked list by putting the array name in the linked list parentheses like this:

string[] w = new string[] { "be", "or", "not", "to", "be" };

LinkedList<string> phrase = new LinkedList<string>(w);

foreach (string word in phrase)

{
      Console.Write(word + " ");
}

The class available for use in the C# library handles all the addressing in the background. The foreach loop prints out:

be or not to be

Adding and removing items in the list is easy with the built in functions:

• Add an item at the beginning of the list

     phrase.AddFirst("To");

• Adds an item at the end of the list

     phrase.AddLast("that");

• Prints the value of the first node

     System.Console.WriteLine(phrase.First());

• Finds the first node that contains the value “or”

     LinkedListNode<string> target = phrase.Find("or");

• Adds a node after the node that was saved to the variable named “target”

     phrase.AddAfter(target, "NOT");

• Removes the first occurrence of a node

     phrase.Remove("not");

Going through all the steps, what will be printed if you run a foreach loop on the phrase linked list?

To be or NOT to be that