How does the implementation for Enumerator work in the Linked List class?
In the .NET resource reference, there’s a page on the LinkedList and LinkedListNode classes and in it, there’s a struct called Enumerator which implements the IEnumerator<T> and IEnumerator interfaces.
I decided to re-use pretty much all of the code for my own ForkableLinkedList<T> and ForkableLinkedListNode<T> classes, I get an error for the implementation of ForkableLinkedList<T>.GetEnumerator():
cannot convert from ‘CustomLinkedList.Models.ForkableLinkedList’ to ‘CustomLinkedList.Models.ForkableLinkedList’.
Here’s what my linked list looks like (I added a comment on the line where I get an error):
public class ForkableLinkedList<T> : ICollection<T>, System.Collections.ICollection, IReadOnlyCollection<T> { // This LinkedList is a doubly-Linked circular list. internal ForkableLinkedListNode<T> head; internal int count; internal int version; private Object _syncRoot; public ForkableLinkedList() { } public ForkableLinkedList(IEnumerable<T> collection) { if (collection == null) { throw new ArgumentNullException("collection"); } foreach (T item in collection) { AddLast(item); } } public int Count => count; public ForkableLinkedListNode<T> First => head; public ForkableLinkedListNode<T> Last => head == null ? null : head.prev; bool ICollection<T>.IsReadOnly => false; void ICollection<T>.Add(T value) => AddLast(value); public ForkableLinkedListNode<T> AddAfter(ForkableLinkedListNode<T> node, T value) { ValidateNode(node); ForkableLinkedListNode<T> result = new ForkableLinkedListNode<T>(node.list, value); InternalInsertNodeBefore(node.next, result); return result; } public void AddAfter(ForkableLinkedListNode<T> node, ForkableLinkedListNode<T> newNode) { ValidateNode(node); ValidateNewNode(newNode); InternalInsertNodeBefore(node.next, newNode); newNode.list = this; } public ForkableLinkedListNode<T> AddBefore(ForkableLinkedListNode<T> node, T value) { ValidateNode(node); ForkableLinkedListNode<T> result = new ForkableLinkedListNode<T>(node.list, value); InternalInsertNodeBefore(node, result); if (node == head) { head = result; } return result; } public void AddBefore(ForkableLinkedListNode<T> node, ForkableLinkedListNode<T> newNode) { ValidateNode(node); ValidateNewNode(newNode); InternalInsertNodeBefore(node, newNode); newNode.list = this; if (node == head) { head = newNode; } } public ForkableLinkedListNode<T> AddFirst(T value) { ForkableLinkedListNode<T> result = new ForkableLinkedListNode<T>(this, value); if (head == null) { InternalInsertNodeToEmptyList(result); } else { InternalInsertNodeBefore(head, result); head = result; } return result; } public void AddFirst(ForkableLinkedListNode<T> node) { ValidateNewNode(node); if (head == null) { InternalInsertNodeToEmptyList(node); } else { InternalInsertNodeBefore(head, node); head = node; } node.list = this; } public ForkableLinkedListNode<T> AddLast(T value) { ForkableLinkedListNode<T> result = new ForkableLinkedListNode<T>(this, value); if (head == null) { InternalInsertNodeToEmptyList(result); } else { InternalInsertNodeBefore(head, result); } return result; } public void AddLast(ForkableLinkedListNode<T> node) { ValidateNewNode(node); if (head == null) { InternalInsertNodeToEmptyList(node); } else { InternalInsertNodeBefore(head, node); } node.list = this; } public void Clear() { ForkableLinkedListNode<T> current = head; while (current != null) { ForkableLinkedListNode<T> temp = current; current = current.Next; // use Next the instead of "next", otherwise it will loop forever temp.Invalidate(); } head = null; count = 0; version++; } public bool Contains(T value) { return Find(value) != null; } public void CopyTo(T[] array, int index) { if (array == null) { throw new ArgumentNullException("array"); } if (index < 0 || index > array.Length) { throw new ArgumentOutOfRangeException("index"); } if (array.Length - index < Count) { throw new ArgumentException("index"); } ForkableLinkedListNode<T> node = head; if (node != null) { do { array[index++] = node.item; node = node.next; } while (node != head); } } public ForkableLinkedListNode<T> Find(T value) { ForkableLinkedListNode<T> node = head; EqualityComparer<T> c = EqualityComparer<T>.Default; if (node != null) { if (value != null) { do { if (c.Equals(node.item, value)) { return node; } node = node.next; } while (node != head); } else { do { if (node.item == null) { return node; } node = node.next; } while (node != head); } } return null; } public ForkableLinkedListNode<T> FindLast(T value) { if (head == null) return null; ForkableLinkedListNode<T> last = head.prev; ForkableLinkedListNode<T> node = last; EqualityComparer<T> c = EqualityComparer<T>.Default; if (node != null) { if (value != null) { do { if (c.Equals(node.item, value)) { return node; } node = node.prev; } while (node != last); } else { do { if (node.item == null) { return node; } node = node.prev; } while (node != last); } } return null; } public IEnumerator GetEnumerator() { return new Enumerator(this); // Here I get the aforementioned error. } IEnumerator<T> IEnumerable<T>.GetEnumerator() { return GetEnumerator(); } public bool Remove(T value) { ForkableLinkedListNode<T> node = Find(value); if (node != null) { InternalRemoveNode(node); return true; } return false; } public void Remove(ForkableLinkedListNode<T> node) { ValidateNode(node); InternalRemoveNode(node); } public void RemoveFirst() { if (head == null) { throw new InvalidOperationException(); } InternalRemoveNode(head); } public void RemoveLast() { if (head == null) { throw new InvalidOperationException(); } InternalRemoveNode(head.prev); } private void InternalInsertNodeBefore(ForkableLinkedListNode<T> node, ForkableLinkedListNode<T> newNode) { newNode.next = node; newNode.prev = node.prev; node.prev.next = newNode; node.prev = newNode; version++; count++; } private void InternalInsertNodeToEmptyList(ForkableLinkedListNode<T> newNode) { Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!"); newNode.next = newNode; newNode.prev = newNode; head = newNode; version++; count++; } internal void InternalRemoveNode(ForkableLinkedListNode<T> node) { Debug.Assert(node.list == this, "Deleting the node from another list!"); Debug.Assert(head != null, "This method shouldn't be called on empty list!"); if (node.next == node) { Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node"); head = null; } else { node.next.prev = node.prev; node.prev.next = node.next; if (head == node) { head = node.next; } } node.Invalidate(); count--; version++; } internal void ValidateNewNode(ForkableLinkedListNode<T> node) { if (node == null) { throw new ArgumentNullException("node"); } if (node.list != null) { throw new InvalidOperationException(); } } internal void ValidateNode(ForkableLinkedListNode<T> node) { if (node == null) { throw new ArgumentNullException("node"); } if (node.list != this) { throw new InvalidOperationException(); } } bool System.Collections.ICollection.IsSynchronized { get { return false; } } object System.Collections.ICollection.SyncRoot { get { if (_syncRoot == null) { System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); } return _syncRoot; } } void System.Collections.ICollection.CopyTo(Array array, int index) { if (array == null) { throw new ArgumentNullException("array"); } if (array.Rank != 1) { throw new ArgumentException("array"); } if (array.GetLowerBound(0) != 0) { throw new ArgumentException("array"); } if (index < 0) { throw new ArgumentOutOfRangeException("index"); } if (array.Length - index < Count) { throw new ArgumentException("index"); } T[] tArray = array as T[]; if (tArray != null) { CopyTo(tArray, index); } else { // // Catch the obvious case assignment will fail. // We can found all possible problems by doing the check though. // For example, if the element type of the Array is derived from T, // we can't figure out if we can successfully copy the element beforehand. // Type targetType = array.GetType().GetElementType(); Type sourceType = typeof(T); if (!(targetType.IsAssignableFrom(sourceType) || sourceType.IsAssignableFrom(targetType))) { throw new ArgumentException("array"); } object[] objects = array as object[]; if (objects == null) { throw new ArgumentException("array"); } ForkableLinkedListNode<T> node = head; try { if (node != null) { do { objects[index++] = node.item; node = node.next; } while (node != head); } } catch (ArrayTypeMismatchException) { throw new ArgumentException("array"); } } } } And here’s the code for Enumerator, which I copied verbatim and then removed the serialization stuff that I didn’t need. Here, it doesn’t seem to recognize T as a generic type because I don’t use Enumerator<T>. So why does it work in the .NET reference?
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator // Here, T is not recognized as a generic type { private ForkableLinkedList<T> list; private ForkableLinkedListNode<T> node; private int version; private T current; private int index; internal Enumerator(ForkableLinkedList<T> list) { this.list = list; version = list.version; node = list.head; current = default(T); index = 0; } public T Current { get { return current; } } object System.Collections.IEnumerator.Current { get { if (index == 0 || (index == list.Count + 1)) { throw new InvalidOperationException(); } return current; } } public bool MoveNext() { if (version != list.version) { throw new InvalidOperationException(); } if (node == null) { index = list.Count + 1; return false; } ++index; current = node.item; node = node.next; if (node == list.head) { node = null; } return true; } void System.Collections.IEnumerator.Reset() { if (version != list.version) { throw new InvalidOperationException(); } current = default(T); node = list.head; index = 0; } public void Dispose() { } } I’m using .NET Core 3.1.301 in Visual Studio Code 1.46.1 on a Windows 10 (x64) machine.
