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 OutOfMemoryException
s 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 version
It 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; }
}
}
for (;;)
, because it can be confusing to programmers that didn't encounter it before. The idiomatic way to write an infinite loop in C# iswhile (true)
. – svick Oct 18 '12 at 23:16