I am interested in the performance tradeoffs of linked lists, standard lists and unrolled linked lists. This will depend on various factors including what operation is being performed (e.g. delete, insert, and from where), and the size of the nodes. I've written some performance tests (not listed here).
I am interested in whether the node class could be implemented as an array rather than a list, so I'll be trying this in the future. This class works quite well as a stack, but I am also interested in its use as a queue; in order to try this I might alter the Node class to store pointers for the start and end of the list/array.
Does anyone have any feedback on my unrolled linked list class? I did it just for fun.
/// <summary>
/// An unrolled linked list implements the standard list operations.
/// Its implementation is inbetween that of a standard List and a LinkedList.
/// </summary>
public class UnrolledLinkedList<T> : IList<T>
{
private Node first, last;
private int count;
/// <summary>
/// Create a new (empty) unrolled linked list
/// </summary>
public UnrolledLinkedList()
{
count = 0;
}
/// <summary>
/// Create an unrolled linked list which is populated with data from an enumerable
/// </summary>
public UnrolledLinkedList(IEnumerable<T> enumerable)
: this()
{
if (enumerable.Any())
{
first = new Node();
Node node = first;
foreach(T t in enumerable)
{
node = AddAfterIfFull(node, t);
count++;
}
last = node;
}
}
public int IndexOf(T item)
{
int offset = 0;
foreach (Node node in Nodes)
{
int nodeResult = node.IndexOf(item);
if (nodeResult >= 0)
{
return offset + nodeResult;
}
offset += node.Count;
}
return -1;
}
public void Insert(int index, T item)
{
if (first == null) //if the list is empty, then thats only ok if index=0
{
if (index == 0)
{
Initialise(item);
}
else
{
throw new IndexOutOfRangeException("The list is empty, so you can only insert at index 0");
}
}
else
{
if (index == count) //adding right at the end of the list
{
AddAfterIfFull(last, item);
}
else
{
FindResult findResult = Find(index);
if (findResult.node.IsFull)
{
T t = findResult.node.RemoveLast();
AddAfter(findResult.node, t);
}
findResult.node.Insert(index - findResult.offset, item);
}
}
count++;
}
public T this[int index]
{
get
{
FindResult findResult = Find(index);
return findResult.node[index - findResult.offset];
}
set
{
FindResult findResult = Find(index);
findResult.node[index - findResult.offset] = value;
return;
}
}
public void Add(T item)
{
if (first == null)
{
Initialise(item);
}
else
{
AddAfterIfFull(last, item);
}
count++;
}
public void Clear()
{
first = null;
count = 0;
}
public bool Contains(T item)
{
return Nodes.Any(x => x.Contains(item));
}
public void CopyTo(T[] array, int arrayIndex)
{
int i = arrayIndex;
foreach (T t in this)
{
array[i] = t;
i++;
}
}
public int Count
{
get
{
return count;
}
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
foreach (Node node in Nodes)
{
int i = node.IndexOf(item);
if (i >= 0)
{
if (node.Count == 1)
{
DeleteNode(node);
}
else
{
node.RemoveAt(i);
}
count--;
return true;
}
}
return false;
}
public void RemoveAt(int index)
{
FindResult findResult = Find(index);
findResult.node.RemoveAt(index - findResult.offset);
if (!findResult.node.Any())
{
DeleteNode(findResult.node);
}
count--;
return;
}
public IEnumerator<T> GetEnumerator()
{
foreach (Node node in Nodes)
{
foreach (T t in node)
{
yield return t;
}
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
/// <summary>
/// Initialise this list so it contains only one item.
/// DOES NOT increase the count
/// </summary>
private void Initialise(T firstItem)
{
first = new Node();
first.Add(firstItem);
last = first;
}
/// <summary>
/// Gets an enumerator over all the nodes
/// </summary>
private IEnumerable<Node> Nodes
{
get
{
Node node = first;
while (node != null)
{
yield return node;
node = node.next;
}
}
}
/// <summary>
/// If the node supplied is full then a new one is created afterwards;
/// the item is added
/// </summary>
/// <returns>If the node is full then the new node; otherwise just the node supplied</returns>
private Node AddAfterIfFull(Node node, T item)
{
if (node.IsFull)
{
return AddAfter(node, item);
}
else
{
node.Add(item);
return node;
}
}
/// <summary>
/// Adds a new node after the node supplied, and populates it with the item supplied.
/// DOES NOT increase the count
/// </summary>
private Node AddAfter(Node node, T item)
{
Node newNode = new Node();
newNode.Add(item);
newNode.next = node.next;
newNode.previous = node;
if (node.next == null)
{
last = newNode;
}
else
{
node.next.previous = newNode;
}
node.next = newNode;
return newNode;
}
/// <summary>
/// Removes a node from the list
/// </summary>
private void DeleteNode(Node node)
{
if (node.next == null)
{
last = node.previous;
}
if (node.previous != null)
{
node.previous.next = node.next;
}
if (node.next != null)
{
node.next.previous = node.previous;
}
}
/// <summary>
/// Finds the item with this index,
/// and the index of the first item within that node
/// </summary>
private FindResult Find(int index)
{
int offset = 0;
foreach (Node node in Nodes)
{
int nextOffset = offset + node.Count;
if (index >= offset && index < nextOffset) //found node
{
return new FindResult(node, offset);
}
offset = nextOffset;
}
throw new IndexOutOfRangeException("No item at that index!");
}
/// <summary>
/// Stores the two values returned by Find
/// </summary>
private class FindResult
{
public readonly Node node;
public readonly int offset;
public FindResult(Node node, int offset)
{
this.node = node;
this.offset = offset;
}
}
////////////////////// NODE CLASS //////////////////////
private class Node : List<T>
{
internal const int MaxSize = 100;
public Node next, previous;
public bool IsFull
{
get
{
return Count >= MaxSize;
}
}
public T RemoveLast()
{
int i = Count - 1;
T t = this[i];
RemoveAt(i);
return t;
}
}
}
Performance
Here are some performance statistics. It's not scientific but it gives you a rough idea. Times are in milliseconds.
- Adding 100000 integers (list): 1
Adding (unrolled linked list): 12
Finding the index of an integer at the end of 1000 integers (list): 10886
Finding (unrolled linked list): 18055
Inserting 100000 integers into the middle (list): 22694
Insertion(unrolled linked list): 2238
Deletion of 1000 items from the start (list): 2331
- Deletion (unrolled linked list): 1
It looks like an unrolled linked list could be a good choice for a long list where there is a lot of insertion or deletion at places other than the end. It will have a lower memory footprint than a linked list (I've not tested that out though).
List<T>
that will hold the first (or the last) item of each Node used byUnrolledLinkedList<T>
? That way when you want to find the index of an element you just need to perform a binary search in that list (which is always sorted) to know in which Node that element is. If you have a lot of nodes, it will pay. when you think about it, it is somehow similar to aB+Tree
but with only one level below root. \$\endgroup\$