Книга: C# 2008 Programmer

Using the LinkedList Generic Class

Using the LinkedList<T> Generic Class

One of the new classes in the System.Collection.Generic namespace is the LinkedList<T> generic class. A linked list is a data structure containing a series of interconnected nodes. Linked lists have wide usage in computer science and are often used to store related data.

There are several types of linked lists:

? Singly linked list

? Doubly linked list

? Circularly linked list

Figure 9-5 shows a singly linked list. Every node has a field that "points" to the next node. To move from one node to another (known as list traversal), you start from the first node and follow the links leading to the next node.

Figure 9-5 

Figure 9-6 shows a doubly linked list. Doubly linked list nodes contains an additional field to point to the previous node. You can traverse a doubly linked list in either direction. The LinkedList<T> class implements a doubly linked list.

Figure 9-6

Figure 9-7 shows a circularly linked list. A circularly linked list has its first and last node linked together. A circularly linked list can either be a singly linked list (as shown in Figure 9-5) or a doubly linked list.

Figure 9-7 

The next example shows how to use the LinkedList<T> class available in the .NET Framework to store a list of random numbers. As each random number is generated, it is inserted into the linked list in numeric sorted order (from small to big). The end result is a list of sorted random numbers. Specifically, the example uses the LinkedList<T> class members shown in the following table.

Each node in the LinkedList<T> class is an object of type LinkedListNode<T>. The following table shows the properties in the LinkedListNode<T> that are used in this example.

Now for the example, first create an instance of the LinkedList<T> class using the int type:

LinkedList<int> Numbers = new LinkedList<int>();

Define the InsertNumber() function, which accepts an int parameter:

private void InsertNumber(int number) {
 //---start from first node---
 LinkedListNode<int> currNode = Numbers.First;
 LinkedListNode<int> newNode = new LinkedListNode<int>(number);
 if (currNode == null) {
  Numbers.AddFirst(newNode);
  return;
 }
 while (currNode != null) {
  if (currNode.Value < number) {
   if (currNode.Previous != null)
    //---Case 1 - add the node to the previous node---
    Numbers.AddAfter(currNode.Previous, newNode);
   else
    //--- Case 2 - the current node is the first node---
    Numbers.AddBefore(currNode, newNode);
   break;
  } else if (currNode.Next == null) {
   //--- Case 3 - if last node has been reached---
   Numbers.AddAfter(currNode, newNode);
   break;
  }
  //---traverse to the next node---
  currNode = currNode.Next;
 }
}

The InsertNumber() function initially creates a new node to contain the random number generated. It then traverses the linked list to find the correct position to insert the number. Take a look at the different possible cases when inserting a number into the linked list.

Figure 9-8 shows the case when the node to be inserted (11) is between two nodes (9 and 15, the current node). In this case, it must be added after node 9.

Figure 9-8

Figure 9-9 shows the case when the node to be inserted (11) is smaller than the first node (current node) in the linked list. In this case, it must be added before the current node.

Figure 9-9

Figure 9-10 shows the case when the node to be inserted is larger than the last node (current node) in the linked list. In this case, it must be added after the current node.

Figure 9-10

To insert a list of random numbers into the linked list, you can use the following statements:

Random rnd = new Random();
for (int i = 0; i < 20; i++)
 InsertNumber(rnd.Next(100)); //---random number from 0 to 100---

To print out all the numbers contained within the linked list, traverse the link starting from the first node:

//---traverse forward---
LinkedListNode<int> node = Numbers.First;
while (node != null) {
 Console.WriteLine(node.Value);
 node = node.Next;
}

The result is a list of 20 random numbers in sorted order. Alternatively, you can traverse the list backward from the last node:

//---traverse backward---
LinkedListNode<int> node = Numbers.Last;
while (node != null) {
 Console.WriteLine(node.Value);
 node = node.Previous;
}

The result would be a list of random numbers in reverse-sort order.

Оглавление книги