C# .NET Iterator Example : Complex Iteration

Link lists are complex data structures. Iterators are particularly useful when iterating complex data structures, such as a link list. Each item in the list is considered a node. Nodes maintain a reference to the previous and next node. From any node, you can walk the link list either forward or backward. For several reasons, the iteration is more complex. First, data structure must be iterated forward and backward during the same iteration. Second, fence posts are not as definable. Fence posts in arrays, stacks, queues, and other sequenced containers are easily found, which helps avoid fence post error exceptions. Finally, the iteration can start from any node in the link list, not necessarily just the beginning or end of the list.

Below is a partial listing of the Node class. The key code is in the GetEnumerator method. In the first while loop, the link list is iterating in reverse—from the current node to the beginning of list. This is accomplished by walking the prevNode member of the node class. The current node is enumerated next. Finally, the second while loop iterates the link list going forward from the current node to the end of the list. The nextNode members are walked.

public class Node<T> {     public Node(Node<T> node, T data)     {         m_Info = data;         if (node == null)         {             if (firstNode != null)             {                 Node<T> temp = firstNode;                 this.nextNode = temp;                 temp.prevNode = this;                 firstNode = this;                 return;             }             prevNode = null;             nextNode = null;             firstNode = this;             return;         }           this.prevNode = node;         this.nextNode = node.nextNode;         node.nextNode = this;         if (node.nextNode == null)         {             lastNode = null;         }     }       public void AddNode(T data)     {         this.nextNode = new Node<T>(this, data);     }       public IEnumerator<T> GetEnumerator()     {         Node<T> temp = prevNode;         while (temp != null)         {             yield return temp.m_Info;             temp = temp.prevNode;         }         yield return m_Info;         temp = nextNode;         while (temp != null)         {             yield return temp.m_Info;             temp = temp.nextNode;         }     }       private T m_Info;     private static Node<T> lastNode = null;     private static Node<T> firstNode = null;     private Node<T> prevNode = null;     private Node<T> nextNode = null; }