I tried to implement an unrolled linked list in C#. I only needed to add things and clear the whole list so I didn't implement IList<T> (I tried but it was getting too complex, so I postponed it).Why I did it?I needed a collection that should be able to handle millions of items and I was getting OutOfMemoryExceptions when I tried List<T> since it needs sequential memory to hold everything in one array.I tried LinkedList<T> but it was too slow. I don't need to enumerate backwards or expose the node class publicly. I also know the size of blocks that I want to keep my items in, so I wrote this:public sealed class UnrolledLinkedList<T> : IEnumerable<T>{    // Fields    private int _Count;    private Node _FirstNode;    private Node _LastNode;    private int _LastNodeCount;    private int _NodeCount;    private readonly int _NodeSize;    // Properties    public int Count { get { return _Count; } }    // Constructors    public UnrolledLinkedList(int nodeSize)    {        _NodeCount = 1;        _NodeSize = nodeSize;        _FirstNode = _LastNode = new Node(nodeSize);    }    public UnrolledLinkedList() : this(8) { }    // Fuctions    public void Add(T item)    {        if (_LastNodeCount == _NodeSize)        {            _LastNode = (_LastNode.Next = new Node(_NodeSize));            _LastNode.Items[0] = item;            _LastNodeCount = 1;            _NodeCount++;        }        else _LastNode.Items[_LastNodeCount++] = item;        _Count++;    }    public void Clear()    {        _FirstNode = _LastNode = new Node(_NodeSize);        // Edit: Just added these:        _Count = 0;        _LastNodeCount = 0;        _NodeCount = 1;    }    public IEnumerator<T> GetEnumerator()    {        var current = _FirstNode;        if (current == null)        yield break;        for (; ; )        {            if (current.Next == null)            {                for (int i = 0; i < _LastNodeCount; i++)                    yield return current.Items[i];                yield break;            }            else for (int i = 0; i < _NodeSize; i++)                    yield return current.Items[i];            current = current.Next;        }    }    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()    {        return GetEnumerator();    }    // Types    private class Node    {        public readonly T[] Items;        public Node Next;        public Node(int size) { Items = new T[size]; }    }}Is there a flaw you can detect?Is there any suggestion/optimization you have?Do you know a better implementation of an unrolled linked list in C#?Do you think this class should implement IList<T>?If so, can you give some pointers for implementing functions like Insert?Updated versionIt became like this after the answers:public sealed class UnrolledLinkedList<T> : IEnumerable<T>{    // Fields    private int _Count;    private Node _FirstNode;    private Node _LastNode;    private int _LastNodeCount;    private readonly int _NodeSize;    // Properties    public int Count { get { return _Count; } }    // Constructors    public UnrolledLinkedList(int nodeSize = 64)    {        _NodeSize = nodeSize;        _FirstNode = _LastNode = new Node(nodeSize);    }    // Functions    public void Add(T item)    {        if (_LastNodeCount == _NodeSize)        {            _LastNode.Next = new Node(_NodeSize, item);            _LastNode = _LastNode.Next;            _LastNodeCount = 1;        }        else _LastNode.Items[_LastNodeCount++] = item;        _Count++;    }    public void Clear()    {        _Count = 0;        _FirstNode = _LastNode = new Node(_NodeSize);        _LastNodeCount = 0;    }    public IEnumerator<T> GetEnumerator()    {        for (var current = _FirstNode; current != null; )        {            var last = current.Next == null ? _LastNodeCount : _NodeSize;            for (var i = 0; i != last; i++)                yield return current.Items[i];            current = current.Next;        }    }    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()    {        return GetEnumerator();    }    // Types    private sealed class Node    {        public readonly T[] Items;        public Node Next;        public Node(int size) { Items = new T[size]; }        public Node(int size, T firstItem) : this(size) { Items[0] = firstItem; }    }}
A simple unrolled linked list implementation
c#;.net;collections;linked list
I would change GetEnumerator as follows:public IEnumerator<T> GetEnumerator(){    for (var current = _FirstNode ; current != null ; )    {        var last = current.Next == null ? _NodeSize : _LastNodeCount;        for (var i = 0 ; i != last ; i++) {            yield return current.Items[i];        }        current = current.Next;    }}I would also remove _NodeCount, because you are maintaining it, but not using it anywhere to make decisions.Finally, since you always insert an item in a Node, I would make Node's constructor accept the value T to be placed in Items[0], rather than keeping that code in the Add method.