Introduction
I was writing some code in C# the other day and I realized I needed a linked list to
make something I was doing easier. I wanted a list that would collapse around a removed object,
and that was not be backed by an array. I naturally went to the .NET Framework and the System.Collections
namespace to look at the .NET linked list that I just assumed would be there. To my surprise there was not one.
I could not believe it. I then searched MSDN looking for one to see if it was placed in another namespace.
It was not; it just did not exist in the .NET Framework. Finally, I searched the internet and
still could not find one implemented in C#.
That inspired me to write my own linked list. Not just a standard linked list, but
a doubly-linked list. A list where each element has a reference to the next element and the previous element.
A standard linked list would just have a reference to the next element. With doubly-linked list,
the list can easily be traversed forward and backwards and delete an element in constant time.
Break It Down
My doubly-linked list, which we will call just LinkedList from now on, starts by implementing the
following interfaces.
IList (which is a ICollection and IEnumerable)ICloneable
Then under this public facade we have a lot of very important private members that do the bulk of the work.
class Nodeclass LinkedListEnumerator
FindNodeAt(int)Remove(Node)
Node headerNodeint modifications
Some Details
The Node class is a very simple class, yet it is a very key part
of the LinkedList. It wraps an object and keeps a reference to the next node and the
previous node. The Node class is hidden from the user of the LinkedList,
so that it works like any other collection in the .NET Framework.
The headerNode member variable of type Node has an important role as
the starting point in the list. This Node contains a null reference and
can never be accessed by the user or removed. It is not considered in the count of total objects in
the list. This Node is important in a doubly-linked list, as it is technically the
beginning and ending of the list.
The FindNodeAt(int index) method contains the search algorithm for accessing the
list by index. At the moment it divides the list in half and searches from the beginning
or the end depending on which is closest to the requested index. This method is
used by all the other methods directly or indirectly that require access to
an object by index. This helps to make the searches much faster.
There is potential for improvement for large lists by further dividing before searching, however, at a
cost for small lists. Right now this seems like the best compromise for most
usages. The current algorithm
used to find a Node is below.
Node node = headerNode;
if (index < (count / 2))
{
for (int i = 0; i <= index; i++)
node = node.NextNode;
}
else
{
for (int i = count; i > index; i--)
node = node.PreviousNode;
}
The Remove(Node value) is important because it adjusts the
remaining Nodes by compressing the list. This is done simply by
taking the Node that needs to be removed and changing its
previous Node's next Node reference to its
next Node, and changing its next Node's
previous Node reference to its previous Node then leaving itself for
the garbage collector. This may be easier to understand by viewing the algorithm used in this method below.
if (value != headerNode)
{
value.PreviousNode.NextNode = value.NextNode;
value.NextNode.PreviousNode = value.PreviousNode;
count--;
modifications++;
}
The modifications member variable of type int is incremented
every time there is a modification to the structure of the list.
The variable is then used by the LinkedListEnumerator to guard
against concurrent modifications to the list while enumerating.
The LinkedList class is not thread safe by design. If thread
safety is required, the class can be extended to provide it.
The LinkedListEnumerator class is fail-fast. This means it uses
the modifications variable it is passed when it is created to
know if any modifications have been made while enumerating. The
check is made in its MoveNext() method before it increments to
the next value. If a modification has been detected then it will throw
a SystemException that can then be caught and handled accordingly. Below is
the source for LinkedListEnumerator class.
private class LinkedListEnumerator : IEnumerator
{
private LinkedList linkedList;
private int validModificationCount;
private Node currentNode;
public LinkedListEnumerator(LinkedList linkedList)
{
this.linkedList = linkedList;
validModificationCount = linkedList.modifications;
currentNode = linkedList.headerNode;
}
public object Current
{
get
{
return currentNode.CurrentNode;
}
}
public void Reset()
{
currentNode = linkedList.headerNode;
}
public bool MoveNext()
{
bool moveSuccessful = false;
if (validModificationCount != linkedList.modifications)
throw new SystemException(
"A concurrent modification occured to the LinkedList " +
"while accessing it through it's enumerator.");
currentNode = currentNode.NextNode;
if (currentNode != linkedList.headerNode)
moveSuccessful = true;
return moveSuccessful;
}
}
The LinkedList(ICollection) constructor and the AddAll(ICollection)
and InsertAll(int, ICollection) are there for convenience to the user of the list.
This constructor calls AddAll(ICollection) which in turn
calls InsertAll(int, ICollection). Below is the the code for this method.
public virtual void InsertAll(int index, ICollection collection)
{
if (collection != null)
{
if (0 < collection.Count)
{
modifications++;
Node startingNode = (index == count ?
headerNode : FindNodeAt(index));
Node previousNode = startingNode.PreviousNode;
foreach (object obj in collection)
{
Node node = new Node(obj,
startingNode, previousNode);
previousNode.NextNode = node;
previousNode = node;
}
startingNode.PreviousNode = previousNode;
count += collection.Count;
}
else
throw new ArgumentOutOfRangeException("index",
index, "less than zero");
}
else
throw new ArgumentNullException("collection");
}
The LinkedList provides two methods for cloning. The first
is the ICloneable interface Clone() method.
It provides a shallow copy of the LinkedList.
The second is Clone(bool attemptDeepCopy). It attempts to make a deep copy of
the list if passed true, if false it will make
a shallow copy. If an object in the list is not an ICloneable then
it will throw a SystemException. The returned attempted deep copied
list is not guaranteed to be a true deep copy. It defers the cloning to the
objects own Clone() method. Here is the source for these two methods.
public virtual object Clone()
{
LinkedList listClone = new LinkedList();
for (Node node = headerNode.NextNode; node != headerNode;
node = node.NextNode)
listClone.Add(node.CurrentNode);
return listClone;
}
public virtual LinkedList Clone(bool attemptDeepCopy)
{
LinkedList listClone;
if (attemptDeepCopy)
{
listClone = new LinkedList();
object currentObject;
for (Node node = headerNode.NextNode; node != headerNode;
node = node.NextNode)
{
currentObject = node.CurrentNode;
if (currentObject == null)
listClone.Add(null);
else if (currentObject is ICloneable)
listClone.Add(((ICloneable)currentObject).Clone());
else
throw new SystemException("The object of type [" +
currentObject.GetType() +
"] in the list is not an ICloneable, cannot attempt " +
"a deep copy.");
}
}
else
listClone = (LinkedList)this.Clone();
return listClone;
}
Conclusion
I believe this is a great class to learn how to implement your own custom collection. It is
also very useful as it is, and ready to be included in your next project. The rest of the
class is fairly straight-forward for a list collection. The class is fairly well
commented using XML comment tags. Experienced and intermediate developers should have no trouble following the class.
This LinkedList is part of a set of .NET utilities I am developing, and
have released as an open source project under
the GNU General Public License (GPL). My
complete project can be found at Source Forge.
