10 April 2006

A straight forward implementation of a double-linked list that implements the interface,

    interface IDoubleLinkedList<T>: ILinkedList<T> {
        IEnumerable<T> Backwards { get; }
    }

can be implemented as,

    class DoubleLinkedList<T>: IDoubleLinkedList<T>, IEnumerable<T> {

        private class Node {
            public T Data;
            public Node Next;
            public Node Previous;
        }

        private Node _last;

        public DoubleLinkedList() { }

        public void Add(T value) {
            Node newNode = new Node();
            newNode.Data = value;
            if (_last == null) {
                newNode.Next = newNode;
                newNode.Previous = newNode;
                _last = newNode;
            }
            else {
                newNode.Next = _last.Next;
                _last.Next.Previous = newNode;
                _last.Next = newNode;
                newNode.Previous = _last;
                _last = newNode;
            }
        }

        public void Clear() {
            _last = null;
        }

        public IEnumerator<T> GetEnumerator() {
            if (_last != null) {
                Node current = _last;
                do {
                    current = current.Next;
                    yield return current.Data;
                } while (current != _last);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        public IEnumerable<T> Backwards {
            get {
                if (_last != null) {
                    Node current = _last;
                    do {
                        yield return current.Data;
                        current = current.Previous;
                    } while (current != _last);
                }
            }
        }
    }

With a casual comparison of this implementation to the implementation of LinkList<T> you will see that most of the methods are the same. Clear() and GetEnumator() are identical. Add() is nearly identical; in fact, it would be identical if we changed the Node implementation to

        private class Node {
            public T Data;
            private Node _next;
            public Node Previous;

            public Node Next {
                get {
                    return _next;
                }
                set {
                    _next = value;
                    value.Previous = this;
                }
            }
        }

With this change to the Node class, the only difference between LinkedList<T> and DoubleLinked<T> is the Node class and the Backwards property. It seems obvious we should use inheritance to share code. DoubleLinked<T> should derive from LinkedList<T>. To allow code sharing we need to make some changes to LinkedList<T>. First we need to change Node implementation to allow DoubleLink<T> to override the behavior of Next,

        protected class Node {
            public T Data;
            private Node _next;
            public virtual Node Next { get { return _next; } set { _next = value; } }
        }

Then we need to add,

        protected Node Last { get { return _last; } }

to allow DoubleLinked<T> to access to _last but not modify it. DoubleLink<T> need Last to implement Backwards. Additionally we need to introduce

        protected virtual Node CreateNode() { return new Node(); }

and change the first statement in the Add() method to,

            Node newNode = CreateNode();

to allow DoubleLinked<T> to override which class to create for the nodes in the list. This allows DoubleLink<T> to create DoubleNode instead of Node. With these changes we can now change the implementation of DoubleLink<T> implementation to,

    class DoubleLinkedList<T>: LinkedList<T>, IDoubleLinkedList<T> {

        protected class DoubleNode: Node {
            public DoubleNode Previous;

            public override Node Next {
                get {
                    return base.Next;
                }
                set {
                    base.Next = value;
                    ((DoubleNode)value).Previous = this;
                }
            }
        }

        public IEnumerable<T> Backwards {
            get {
                if (Last != null) {
                    DoubleNode current = (DoubleNode)Last;
                    do {
                        yield return current.Data;
                        current = current.Previous;
                    } while (current != Last);
                }
            }
        }

        protected override LinkedList<T>.Node CreateNode() { return new DoubleNode();  }
    }

There we have it. We used inheritance to share code. Unfortunately, we had to use casts to get this to work. The casts show we are now running into some limitations in the expressiveness of the C# type system. We know that all the items of the list will be of type DoubleNode but we need to convince the compiler (and the CLR) with a cast in the set part of the Next method and the Backwards property. It would be nice to write this without casts. Next time we look at a way to rid ourselves of one the cast in the Backwards property and the virtual CreateNode() method. We will also look at some possible ways to increase the expressiveness of C#'s type system to allow us to get rid of the final cast.



blog comments powered by Disqus