Introduction
Many programs require some form of dynamic memory management. This need arises whenever it is necessary to create data structures whose size cannot be determined statically when the program is being built. Search trees, symbol tables, and linked lists are examples of dynamic data structures. A linked list is a linear collection (i.e. a sequence) of self-referential class objects called nodes, connected by reference links. A program accesses a linked list via a reference to the first node of the list. Each subsequent node is accessed via the link-reference number stored in the previous node. Data is stored in a linked list dynamically--that is, each node is created as necessary. It follows then that a node can contain data of any type, including references to other objects of other classes. The advantage of using a linked list over an array is that an array can be declared to contain more elements than the number of items expected, potentially wasting memory. Linked lists provide better memory utilization because they can grow and shrink at execution time, saving memory. The elements of an array are stored contiguously in memory to allow immediate access to any array element. That is, the address of any element in an array can be calculated directly from its index. Linked lists do not enable quick access to their elements: you have to traverse the list from the front. I am writing this article to exemplify a linked list library that can be used by a test program (a very basic program). The program consists of four classes. We will build it and then install it into our global assembly cache:
using System;
namespace LinkedListLibrary
{
class ListNode
{
public object Data { get; private set; }
public ListNode Next { get; set; }
public ListNode(object dataValue )
: this (dataValue, null)
{
}
public ListNode(object dataValue, ListNode nextNode )
{
Data = dataValue;
Next = nextNode;
}
}
public class List
{
private ListNode firstNode;
private ListNode lastNode;
private string name;
public List( string listName)
{
name = listName;
firstNode = lastNode = null;
}
public List()
: this("list")
{
}
public void InsertAtFront(object insertItem)
{
if ( IsEmpty() )
firstNode = lastNode = new ListNode(insertItem);
else
lastNode = lastNode.Next = new ListNode(insertItem);
}
public void InsertAtBack(object insertItem)
{
if (IsEmpty())
firstNode = lastNode = new ListNode(insertItem);
else
firstNode = new ListNode( insertItem, firstNode);
}
public object RemoveFromFront()
{
if (IsEmpty())
throw new EmptyListException( name );
object removeItem = firstNode.Data;
if (firstNode == lastNode)
firstNode = lastNode = null;
else
firstNode = firstNode.Next;
return removeItem;
}
public object RemoveFromBack()
{
if (IsEmpty() )
throw new EmptyListException( name );
object removeItem = lastNode.Data;
if (firstNode == lastNode)
firstNode = lastNode = null;
else
{
ListNode current = firstNode;
while (current.Next != lastNode)
current = current.Next;
lastNode = current;
current.Next = null;
}
return removeItem;
}
public bool IsEmpty()
{
return firstNode == null;
}
public void Display()
{
if ( IsEmpty() )
{
Console.WriteLine( "Empty " + name);
}
else
{
Console.Write("The " + name + " is: ");
ListNode current = firstNode;
while ( current != null )
{
Console.Write(current.Data + " " );
current = current.Next;
}
Console.WriteLine("\n");
}
}
}
public class EmptyListException : Exception
{
public EmptyListException()
: base("The list is empty")
{
}
public EmptyListException(string name)
: base("the " + name + " is empty")
{
}
public EmptyListException(string exception, Exception inner)
: base( exception, inner)
{
}
}
}
Notice that the methods that are defined in the four classes involve insertion or deletion at the front or back of the linked list. This means that this data structure requires some form of dynamic memory management; it does not store in memory like an array even though it is a sequence. The nodes are logically contiguous and form a graph. This growth and shrinking saves memory. So if we compile it:
csc.exe /target:library /out: LinkedListLibrary.dll LinkedListLibrary.cs
Now let’s give it a key:
sn –k LinkedLibrary.key
sn -p LinkedList.key LinkedList.PublicKey
Public key written to LinkedList.PublicKey
sn –tp LinkedList.PublicKey
Public key is
00240000048000009400000006020000002400005253413100040000010001001140e2bd73e36c
ab97d26e829e0c6effdf19cf4bb207d8390ffaff1d6ed27589cf051c73af89f3f2835ec22af689
1014297135206738f65188ab6c344b7e8bf0ff0cacc23835f7e9c36edea4965326c67d91e2dcce
e69aa334c9f4f7973f0fb5ec87b41f75a8f093ce9f538498ea75c070f049c05a43a328f58fb977
0d1bd6ec
Public key token is d45a48ae6bd81f08
csc /keyfile:LinkedList.key /target:library LinkedListLibrary.cs
gacutil -i LinkedListLibrary.dll
Assembly successfully added to the cache
Class List contains private instance variables firstNode (a reference to the first ListNode in a List) and lastNode (a reference to the last ListNode in a List). The method IsEmpty() is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is null). If the list is empty, IsEmpty() returns true. The Display() method displays the list's contents. This next program will reference the library and use the functions on all of the primitive data types.
using System;
using LinkedListLibrary;
class ListTest
{
public static void Main(string[] args)
{
List list = new List();
bool aBoolean = true;
char aCharacter = '$';
int anInteger = 34567;
string aString = "hello";
list.InsertAtFront(aBoolean);
list.Display();
list.InsertAtFront(aCharacter);
list.Display();
list.InsertAtBack(anInteger);
list.Display();
list.InsertAtBack(aString);
list.Display();
object removedObject;
try
{
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed");
list.Display();
}
catch (EmptyListException emptyListException)
{
Console.Error.WriteLine( "\n" + emptyListException);
}
}
}
Now here is the output:
The list is: True
The list is: True $
The list is: 34567 True $
The list is: hello 34567 True $
hello removed
The list is: 34567 True $
34567 removed
The list is: True $
$ removed
The list is: True
True removed
Empty list
The typical compilation with an external reference:
csc.exe /r:LinkedListLibrary.dll ListTest.cs
The four classes build the LinkedListLibrary and can also be used for other linear data structures, like stacks and queues. A tree, on the other hand, is a non-linear, two dimensional data structure that has special properties. But from the beginning stand point, that reusable component is only meant to demonstrate the underlying principles of the linked list. One cannot avoid the BCL class definition of the linked list.
.NET 2.0 introduced generics. Generics are similar in principle to templates and the STD in ISO C++. Assume you have a collection of objects, all of which are numeric amounts for paychecks. They form an itemized list. The data type would obviously be of type decimal. But if one or more were different types, (such as a string, an Int32, a char, and so on) we included, then the functions used in an algorithm or processing procedure would not be able to process those of a different data type. There would be a compiler error when it came to, say, a string type, for instance. In the simplest sense, generics involves parameterizing types so as to pass a data type to a class (as you pass a parameter to a function). The .NET Framework provides a double linked list class. The LinkedList<t> class -- found in the System.dll assembly -- stores a collection of nodes of type LinkedListNode<t>, each of which is responsible for maintaining a pointer to the next element in line. That is, the list itself maintains only a pointer to front and back elements (i.e., head and tail) -- represented as Front and Back properties on the list type. Each node has next and previous pointers to the nodes surrounding it in the list.
LinkedListNode<t> instantiations normally have three properties: Next, Previous, and Value:
Next will be null at the end of the list, similar to the end of a file. Consider this code:
using System;
using System.Collections.Generic;
public sealed class Program
{
public static void Main()
{
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(10); list.AddLast(15); list.AddLast(3); list.AddLast(99); list.AddBefore(list.Last, 25);
LinkedListNode<int> node = list.First;
while (node != null)
{
Console.WriteLine(node.Value);
node = node.Next;
}
}
}
The output would be as expected:
10
15
3
25
99
Notice that we iterate through the Linked list node that the code does not branch until the node has a value of null. We then display the results of the initial constructor after that iteration, prior to the establishment of the Linked list elements and the operations performed on them. But earlier I mentioned memory resources. In .NET, a linked list does not allocate sequential, or contiguous, storage for its elements as an array does. This is why collections begin because there are limitations to arrays. Rather, a linked list uses pointers to chain individual elements together. As a result, linked lists are quicker for inserting and deleting elements, but are slower for traversal – slower for stepping over the contents of a collection. To access each element requires an additional pointer dereference. So linked list elements point to other areas of memory because of that indirection: they can point to areas of memory far from the source point. This could cause overhead for garbage collection and any random access to an element. File I/O goes the same for sequential access and random access to data. Accessing an arbitrary node within the list requires that you either start with the front or the back. Perhaps the cost associated with having a dynamic structure should be weighed against the overhead of traversing the list.
