26 March 2006

Last time I investigated several ways to implement an expression evaluator using a procedural style and several object oriented styles. I used this to demonstrate a data structure that doesn't lend itself well to being representing in an object oriented style. Another problematic structure is a linked list. It is not so much the linked list itself but writing it is such a way that is both type safe and also supports code sharing with, say, a doubly-linked list. What I want to implement is a class that implements the following interface.

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

And then a subclass of that class that implements,

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

which inherits the implementation of Add() and Clear() and efficiently implements Backwards. For now, I will ignore the generic parameter and just implement a simple linked list. First, lets create a Node that will form the nodes of the linked list.

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

A linked list consists of a list of these nodes.

    class LinkedList: IEnumerable {
        Node _last;
    }

When an item is added to the list we will create a new node to hold it and create circular list where the _last instance variable will always point to the last node. This way we can quickly find both the last node and the first node of the list because, since the list is circular, the last node's Next field points to the first node. The reason I chose this particular way of implementing a linked list will be obvious if you have watched this video.

        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;
            }
        }

Clearing the list is simple, just forget all the nodes.

        public void Clear() {
            _last = null;
        }

I implemented IEnumerable interface by using the new yield feature of C# 2.0. I start at the last node of the list, walk forward (to the first node) and yield an element, each successive loop will yield another element until we have yielded the last element (which is pointed to by _last).

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

Now I have a reasonable implementation of a linked list. Next time we will take several different approaches to implement the interfaces defined above.



blog comments powered by Disqus