Welcome to the third part of the series on implementing a double linked list. It is now time to finalize the basic functions of the list, as well as some extra helper functions. The latter have the purpose of easing the use of the list for its users.
In this episode we'll cover the following:
- Delegate some of the concerns of the list to its nodes;
- Implement the IEnumerable interface, and the associate iterator;
- Add a bit of "closure" to our list.
- Removing items from the list
Preamble
The main difference between our implementation of the doubly linked list and the one provided by the .Net framework, is in the accessibility of data. While the .Net framework version exposes the data through the nodes containing it, we, on the other hand, expose it directly. This might be a shortcoming in terms of flexibility for navigating locally in the list. But the benefits come in form of structural integrity of the list, while permitting low level alteration of the structure of the list, and a better user experience in terms of accessing the data. What I mean by keeping control over the structural integrity of the list is that the consumer of the list can't make modifications that could break the chain of references or desynchronize the count of nodes, but the list can make modifications at that level internally. Of course these low level operations are also available to the inheritors of the list.
Revisiting the Node Class
Until now we've managed to ignore the Node class, but she "feels" that and tells us: "Listen, I'm pretty good at holding hands (references) with my left and right neighbors, so let me add new neighbor nodes as well as remove myself from the list". So we delegate to the Node class the concern of "keeping up references" during the operation of the list.
Adding a neighbor to the left of a node, means that we have to change:
- the reference of the original left node to its right node, to the new node;
- the reference to the original left node, to the new node;
- the reference of the new node's left node, to the original left node;
the reference of the new node's right node to the current node.
public Node<T> EnchainBefore(T item)
{
Node<T> node = new Node<T>();
node.Data = item;
node.Previous = Previous;
node.Next = this;
Previous.Next = node;
Previous = node;
return node;
}
Removing the current node means we have to make its two neighbors reference each other:
public void RemoveFromChain()
{
Previous.Next = Next;
Next.Previous = Previous;
}
Implementing the IEnumberable Interface
The interesting part is not implementing the IEnumerable interface, but the IEnumerator. The twist is that the enumerator must "enumerate" through the list in two directions: forward as well as backward. Essentially the iterator will follow the chain of references starting with the left sentinel and ending with the right sentinel for forward enumerating. The iterator will go the other way around for backward iteration. This logic is embodied into the MoveNext method:
public bool MoveNext()
{
if (forwardDirection)
{
current = current.Next;
return current != rightSentinel;
}
current = current.Previous;
return current != leftSentinel;
}
The rest of the code is just plumbing and we shall not go over it.
A Little Bit of Closure
We need a way of applying some function to the list of nodes. The process must be controled by the function, meaning that the function can dictate when to stop the process.
Introducing the predicate. The predicate is a delegate with one generic parameter, which returns a boolean value. We could have built our own delegate, and in one way it would have been better, because we are abusing the purpose of the predicate as intended by its creators. But why reinvent the wheel when it's already there.
So let's define the Apply method, which applies a predicate received as parameter to each node, as long as the predicate evaluates to (returns) true and there are still items in the list:
Public virtual void Apply(Predicate<T> predicate)
{
Node<T> node = leftSentinel.Next;
while (node != rightSentinel && predicate(node.Data))
node = node.Next;
}
Removing items from the list can be easily implemented by using the Apply method. What I intend to do is iterate through the list as long as the current node does not contain the value we are trying to remove, and when we find it we'll ask the containing node to remove itself from the list and stop the iteration:
Apply(delegate(Node<T> node)
{
if (item.Equals(node.Data))
{
node.RemoveFromChain();
count--;
return false;
}
return true;
});
Another method that coud use the help of the predicate is the Add method. This way we could make the items beig added to the list obey certain rules:
public virtual void Add(T item, Predicate<T> check)
{
Node<T> node = leftSentinel.Next;
while (node != rightSentinel && !check(node.Data))
node = node.Next;
AddBefore(node, item);
}
Now we have to tools to implement an ordered list:
public class SortedList : DoubleLinkedList<int>
{
public override void Add(int item)
{
Add(item, delegate (int data)
{
return data < item;
});
}
}
That's all for this episode. Remember you can find the source code here.
