Enumerator over a sublist (linked list)

user_11808605 0
Viewed 111

I am trying to make an enumerator that iterates over a sublist within a linked list. To do this, I'm explicitly keeping track of the two nodes Head and Tail that bound the sublist. My goal is to be able to call a foreach loop over the linked list, to iterate over all the elements of the sublist.

What foreach wants to do:

The foreach loop first initializes an enumerator, in my case with the required list list and a variable linked list node node from which it will ask the Value during the loop.

Once the loop has been initialized, it repeats the following pattern:

  1. Call the MoveNext() method, which 'increments' the list
  2. Retrieve Current and return it to wherever it's called

Repeat until MoveNext() == false.

How I've currently written my enumerator

Since the first step is to move, rather than to return a value, I figured I could initialize my enumerator like this:

this.list = list;
this.node = list.Head.Previous // Initialize node to be the element before Head

Where Head is the first element of the sublist to be shown.

Then, I tried to implement the logic for MoveNext() and Current like this:

public T Current => node.Value;
object IEnumerator.Current => Current;
public bool MoveNext()
{
    node = node.Next;
    return node != list.Tail.Next;
}

Where Tail is the last element of the sublist to be shown.

But in some cases, because this implementation of a linked list is circular, list.Tail.Next can be list.Head, meaning that MoveNext() will return false without even getting the chance to return a single value.

Is there a way to refactor the enumerator to make sure it iterates over the entire sublist instead of just short-circuiting, both when list.Tail.Next does and doesn't point to list.Head?

.net-core linked-list c#
2 Answers

Did you try:

public bool MoveNext()
{
    bool returnValue = node != list.Tail; 
    node = node.Next;
    return returnValue;
}
user_139489660

From your description, there seems to be no cases where the first call to MoveNext would return false.

You could just add an extra piece of state called Moved:

private bool Moved { get; set; } = false;

public bool MoveNext()
{
    node = node.Next;
    var retVal = !Moved || node != list.Tail.Next;
    Moved = true;
    return retVal;
}

An extra state is definitely needed here, because if you only have one element, we have no way to tell whether we have iterated over it or not, as node = node.Next does not change the state of the enumerator.

user_51335850
Related