Unrolled linked list

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.

```
///
/// An unrolled linked list implements the standard list operations.
/// Its implementation is inbetween that of a standard List and a LinkedList.
///
public class UnrolledLinkedList : IList
{
private Node first, last;
private int count;

///
/// Create a new (empty) unrolled linked list
///
public UnrolledLinkedList()
{
count = 0;
}

///
/// Create an unrolled linked list which is populated with data from an enumerable
///
public UnrolledLinkedList(IEnumerable 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 t

A few things off the bat:

• You should consider prefixing private field names with underscores, so it is possible to distinguish them from local variables.

Edit: There is no "official" naming conventions regarding private members. Not that i know of anyway. Underscore however is a somewhat accepted industrial standart nowadays. Mainly, because a) it is used by Microsoft, b) it is used by ReSharper (by default), c) better intelli-sense support, d) when it comes to choosing between this.name = name; and _name = name; most people choose the latter. I think this is pretty accurate

-

IEnumerator enumerator = enumerable.GetEnumerator();
while (enumerator.MoveNext())

emm, why dont you use foreach?

-
tuple.Item1[index - tuple.Item2] = value; - really hard to read.

-

public void Clear()
{
    first = null;
    count = 0;
}

waht happens to last reference?

-
internal members in private class do not make much sense (consider making those public).

-
Your Node class should probably extend List and not encapsulate it. This way you can drop all those proxy methods and therefore reduce the amount of code. Edit2: i think using arrays in Node class is an overkill. You'll end up re-writing List implementation. Resizing is the only noticable performance drawback of List but that is not going to happen in your case (since you specify the size in constructor). The rest is unlikely to become any kind of bottleneck, so you probably want to keep it simple.

-
internal const int MaxSize = 100; this should probably be a parameter rather than a constant (at least as a user i would like to be able to set up the size of a node)

StackExchange Code Review Q#41436, answer score: 5