I was inspired by the Phillip Trelford "Beyond Lists" presentation published on InfoQ. So, I decided to make it simple, yet still capable to act as IList<T>.
I tried to stay close to the Core .Net System.Collections.Generic code style, this is the reason why I decided to explicitly implement Enumerator for the class.
The constrains of this implementation is that it is not thread safe, and Enumerator cannot detect whether collection had been changed during the iteration.
User facing interface:
public partial class UnrolledLinkedList<T> : IList<T>
{
private const int CAPACITY = 16;
private readonly int _NodeCapacity;
private UnrolledLinkedListNode<T> _FirstNode;
private UnrolledLinkedListNode<T> _LastNode;
#region Constructors
public UnrolledLinkedList() : this(CAPASITY) { }
public UnrolledLinkedList(int nodeCapasity)
{
if (nodeCapasity < 1)
{
throw new ArgumentOutOfRangeException("NodeCapasity cannot be less than 1");
}
_NodeCapasity = nodeCapasity;
_LastNode = _FirstNode = new UnrolledLinkedListNode<T>(this._NodeCapasity);
Count = 0;
}
public UnrolledLinkedList(
int nodeCapasity,
IEnumerable<T> collection) : this(nodeCapasity)
{
AddRange(collection);
}
#endregion Constructors
#region ICollection<T> Properties
public int Count { get; private set; }
public bool IsReadOnly
{
get
{
return false;
}
}
#endregion
#region IList<T> Properties
public T this[int index]
{
get
{
CheckIndex(index);
var node = FindNodeAndIndex(ref index);
return node.Data[index];
}
set
{
CheckIndex(index);
var node = FindNodeAndIndex(ref index);
node.Data[index] = value;
}
}
private void CheckIndex(int index)
{
if (index < 0 || index > (Count - 1))
throw new IndexOutOfRangeException();
}
#endregion
#region IEnumerable<T> Methods
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns></returns>
public IEnumerator<T> GetEnumerator()
{
return new Enumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion IEnumerable<T> Methods
#region Public Non-Interface Methods
public void AddRange(IEnumerable<T> range)
{
foreach (var item in range)
{
Add(item);
}
}
public void AddFirst(T item)
{
_FirstNode.Insert(0, item);
Count++;
}
public void AddLast(T item)
{
_LastNode.Add(item);
if (_LastNode.Next != null)
{
_LastNode = _LastNode.Next;
}
Count++;
}
#endregion Public Non-Interface Methods
#region ICollection<T> Methods
/// <summary>
/// Adds an item to the end of the collection
/// <param name="item"></param>
public void Add(T item)
{
AddLast(item);
}
/// <summary>
/// Removes the first occurrence of the item in the list
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Remove(T item)
{
return RemoveFirst(item);
}
private bool RemoveFirst(T item)
{
var found = false;
var currentNode = _FirstNode;
do
{
var index_found = currentNode.IndexOf(item);
if (index_found > -1)
{
found = true;
currentNode.RemoveAt(index_found);
Count--;
if (currentNode.IsEmpty() && currentNode.Previous != null)
{
var prevNode = currentNode.Previous;
prevNode.ByPassNext();
}
break;
}
currentNode = currentNode.Next;
}
while ((currentNode != null));
return found;
}
/// <summary>
/// Removes all items from the collection
/// </summary>
public void Clear()
{
_LastNode = _FirstNode = new UnrolledLinkedListNode<T>(_NodeCapasity);
Count = 0;
}
/// <summary>
/// Determines whether the collection contains a specific value.
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Contains(T item)
{
bool found = false;
var currentNode = _FirstNode;
do
{
found = currentNode.Contains(item);
currentNode = currentNode.Next;
}
while (!found && currentNode != null);
return found;
}
/// <summary>
/// Copies the elements of the collection to an Array, starting at a particular Array index.
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
if (array == null)
{
throw new ArgumentNullException("Parameter 'array' cannot be null");
}
if (arrayIndex < 0)
{
throw new ArgumentOutOfRangeException("Parameter 'arrayIndex' cannot be negative");
}
if (array.Length - arrayIndex < Count)
{
throw new ArgumentException(
"Data will not fit into destination 'array' " +
"starting from specified index. " +
"{\"array.Length\" : {{{0}}}, \"arrayIndex\" : {{{1}}}}");
}
var currentNode = _FirstNode;
do
{
int count = currentNode.CopyTo(array, arrayIndex);
arrayIndex += count;
currentNode = currentNode.Next;
}
while (currentNode != null);
}
#endregion ICollection<T> Methods
#region IList<T> Methods
public int IndexOf(T item)
{
var currentNode = _FirstNode;
int index = 0;
bool found = false;
do
{
var i = currentNode.IndexOf(item);
if (i < 0)
{
index += currentNode.Count;
}
else
{
found = true;
index += i;
}
currentNode = currentNode.Next;
}
while (currentNode != null && !found);
return (found) ? (index) : (-1);
}
public void Insert(int index, T item)
{
if (index < 0 || index > Count)
{
throw new ArgumentOutOfRangeException(
string.Format("Index cannot be less than 0, " +
"or greater than Count: {0}", Count));
}
if (index == Count)
{
AddLast(item);
return;
}
if (index == 0)
{
AddFirst(item);
return;
}
var node = FindNodeAndIndex(ref index);
node.Insert(index, item);
Count++;
}
public void RemoveAt(int index)
{
if (index < 0 || index > (Count - 1))
{
throw new ArgumentOutOfRangeException(
string.Format("Index cannot be less than 0, " +
"or greater than Count: {0}", Count));
}
var node = FindNodeAndIndex(ref index);
node.RemoveAt(index);
Count--;
}
#endregion IList<T> Methods
#region Private Methods
private UnrolledLinkedListNode<T> FindNodeAndIndex(ref int index)
{
var currentNode = _FirstNode;
do
{
if (index < currentNode.Count)
{
break;
}
index -= currentNode.Count;
currentNode = currentNode.Next;
}
while (currentNode != null);
return currentNode;
}
#endregion Private Methods
}
Enumerator:
public partial class UnrolledLinkedList<T>
{
internal struct Enumerator : IEnumerator<T>, IEnumerator
{
private UnrolledLinkedList<T> _List;
private int _CurrentIndex;
private UnrolledLinkedListNode<T> _CurrentNode;
public Enumerator(UnrolledLinkedList<T> list)
{
_List = list;
_CurrentIndex = -1;
_CurrentNode = _List._FirstNode;
}
public T Current
{
get
{
if (_CurrentIndex == -1)
{
throw new InvalidOperationException();
}
return _CurrentNode.Data[_CurrentIndex];
}
}
object IEnumerator.Current
{
get
{
return (object)Current;
}
}
public bool MoveNext()
{
if (_CurrentNode == null || _CurrentNode.Count < 1)
{
return false;
}
_CurrentIndex += 1;
if (_CurrentIndex < _CurrentNode.Count)
{
return true;
}
_CurrentNode = _CurrentNode.Next;
if (_CurrentNode == null)
{
_CurrentIndex = -1;
return false;
}
_CurrentIndex = 0;
return true;
}
public void Reset()
{
_CurrentIndex = -1;
_CurrentNode = _List._FirstNode;
}
public void Dispose() { }
}
}
Internal list node:
class UnrolledLinkedListNode<T>
{
internal UnrolledLinkedListNode<T> Previous { get; private set; }
internal UnrolledLinkedListNode<T> Next { get; private set; }
internal int Count { get; private set; }
internal readonly T[] Data;
private int HalfCapacity { get { return (Data.Length + 1) / 2; } }
#region Constructors
internal UnrolledLinkedListNode(int capacity)
{
Data = new T[capacity];
Count = 0;
}
#endregion Constructors
#region Methods
internal bool IsEmpty()
{
return Count == 0;
}
internal void Add(T item)
{
if (Count < Data.Length)
{
Data[Count] = item;
Count++;
}
else
{
CreateNext();
Next.Add(item);
}
}
internal void RemoveAt(int index)
{
ShiftItemsLeft(index + 1, index);
PullItemsFromNext();
}
internal int CopyTo(T[] array, int arrayIndex)
{
Array.Copy(Data, 0, array, arrayIndex, Count);
return Count;
}
internal int IndexOf(T item)
{
return Array.IndexOf(Data, item, 0, Count);
}
internal bool Contains(T item)
{
return (IndexOf(item) > -1);
}
internal void Insert(int index, T item)
{
if (Count < Data.Length)
{
ShiftItemsRight(index, index + 1);
Data[index] = item;
}
else
{
CreateNext();
int midIndex = Data.Length / 2;
UnrolledLinkedListNode<T> nodeInsertTo = null;
if (index > midIndex)
{
nodeInsertTo = Next;
midIndex += 1;
index -= midIndex;
}
else
{
nodeInsertTo = this;
}
PushItemsToNext(midIndex);
nodeInsertTo.Insert(index, item);
}
}
internal void ByPassNext()
{
if (Next == null)
return;
var newNext = Next.Next;
if (newNext != null)
newNext.Previous = this;
Next = newNext;
}
#endregion Public Methods
#region Private Methods
private void CreateNext()
{
var newNode = new UnrolledLinkedListNode<T>(Data.Length);
newNode.Next = Next;
newNode.Previous = this;
Next = newNode;
}
private void ShiftItemsRight(int sourceIndex, int destinationIndex)
{
if (destinationIndex < sourceIndex)
throw new InvalidOperationException("This shifts items right");
int length = Count - sourceIndex;
Array.Copy(Data, sourceIndex, Data, destinationIndex, length);
Count += destinationIndex - sourceIndex;
}
private void ShiftItemsLeft(int sourceIndex, int destinationIndex)
{
if (destinationIndex > sourceIndex)
throw new InvalidOperationException("This shifts items left");
int idxDifference = sourceIndex - destinationIndex;
int length = Count - sourceIndex;
// TODO: think about the special case of length == 0,
// when the last element in the node is removed
Array.Copy(Data, sourceIndex, Data, destinationIndex, length);
Array.Clear(Data, destinationIndex + length, idxDifference);
Count -= idxDifference;
}
private void PullItemsFromNext()
{
if (Next == null)
return;
if (Count > HalfCapacity)
return;
PullItemsFromNextUntilHalfFull();
var nextCount = Next.Count;
int remainingCapacity = Data.Length - Count;
if (nextCount <= remainingCapacity)
{
Array.Copy(Next.Data, 0, Data, Count, nextCount);
ByPassNext();
}
}
private void PullItemsFromNextUntilHalfFull()
{
int itemsShortToHalfFull = HalfCapacity - Count;
int numberOfItemsToTransfer = Math.Min(itemsShortToHalfFull, Next.Count);
Array.Copy(Next.Data, 0, Data, Count, numberOfItemsToTransfer);
Count += numberOfItemsToTransfer;
Next.ShiftItemsLeft(numberOfItemsToTransfer, 0);
}
private void PushItemsToNext(int startIndex)
{
var length = Count - startIndex;
Array.Copy(Data, startIndex, Next.Data, 0, length);
Next.Count += length;
Array.Clear(Data, startIndex, length);
Count -= length;
}
#endregion Private Methods
}
Full solution with unit tests is located here.
CAPASITYandCAPACITY? \$\endgroup\$DEFAULT_CAPACITYand make that public \$\endgroup\$