01 April 2006

In the last entry we looked at implementing a collection class using a linked list data structure. This time I will show some ways to use that implementation to implement the generic interfaces introduced last time. The complete class looks like,

    class LinkedList: IEnumerable {

        private class Node {
            public object Data;
            public Node Next;
        }

        private Node _last;

        public LinkedList() { }

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

        public void Clear() {
            _last = null;
        }

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

The interface we want to implement is,

    interface ILinkedList<T>: IEnumerable<T> {
        void Add(T value);
        void Clear();
    }

One obvious, but bad, way to implement this interface is to subclass LinkedList like,

    class LinkedList<T>: LinkedList, ILinkedList<T>, IEnumerable<T> {

        public void Add(T value) { base.Add(value); }

        IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            foreach (T item in this)
                yield return item;
        }
    }

The reason this is so bad is because given,

    LinkedList<string> list = new LinkedList<string>();

the following statements are both legal,

    list.Add("some string");
    list.Add(1);

The reason is because the first statement calls the LinkedList<T>.Add(T value) above, as expected, but the second will call LinkedList.Add(object value), because the generic Add is overloaded with the the non-generic version. Even if it was obscured by the new Add method you could still access Add(object value) by,

    LinkedList list2 = list;
    list2.Add(1);

We wanted the compiler to be able to flag when we add a non-string to the list as an error; this implementation doesn't do that. A slightly better approach is to use delegation instead of inheritance, as in,

    class LinkedListD<T>: ILinkedList<T>, IEnumerable<T> {
        private LinkedList _list = new LinkedList();

        public void Add(T value) { _list.Add(value); }

        public void Clear() { _list.Clear(); }

        IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            foreach (T item in _list)
                yield return item;
        }

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

But this is still not good enough because, not only can we no longer inherit the implementation of Clear() and GetEnumerator(), we also use more memory by having to create an instance of LinkedList to wrap. Additionally, if we wanted to add an Insert() method, that put values at the beginning of the list instead of the end, we would have to manually update LinkedListD. A much better approach is to scrap the first implementation and re-implement the class as a generic class, as in,

    class LinkedList<T>: ILinkedList<T>, IEnumerable<T> {
        private class Node {
            public T Data;
            public Node Next;
        }

        private Node _last;

        public LinkedList() { }

        public void Add(T value) {
            Node newNode = new Node();
            newNode.Data = value;
            if (_last == null) {
                newNode.Next = newNode;
                _last = newNode;
            }
            else {
                newNode.Next = _last.Next;
                _last.Next = newNode;
                _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();
        }
    }

With this approach, if we really need a list with data type object, we can always use LinkedList<object> which gives us a class essentially the same class as what we started with.  Sometimes it is just better to rewrite. Note that the BCL took a similar approach. List<T> and Dictionary<K,T> do not inherit from ArrayList and Hashtable.

Next time I will try a first crack at implementing IDoubleLinkedList<T>.



blog comments powered by Disqus