Wei-Meng Lee - C# 2008 Programmer's Reference

Prior to .NET 2.0, all the data structures contained in the System.Collectionnamespace are object-based. With .NET 2.0, Microsoft has released generic equivalents of some of these classes. The following table shows the mapping of these classes in the two namespaces.

The Stack, Queue, and Dictionarygeneric classes are discussed in more detail in Chapter 13, "Collections."

One of the new classes in the System.Collection.Genericnamespace is the LinkedListgeneric 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 LinkedListclass 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 LinkedListclass 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 LinkedListclass members shown in the following table.

Each node in the LinkedListclass is an object of type LinkedListNode. The following table shows the properties in the LinkedListNodethat are used in this example.

Now for the example, first create an instance of the LinkedListclass using the inttype:

LinkedList Numbers = new LinkedList();

Define the InsertNumber()function, which accepts an intparameter:

private void InsertNumber(int number) {

//---start from first node---

LinkedListNode currNode = Numbers.First;

LinkedListNode newNode = new LinkedListNode(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.