7
\$\begingroup\$

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 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; }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I think you shouldn't use for (;;), because it can be confusing to programmers that didn't encounter it before. The idiomatic way to write an infinite loop in C# is while (true). \$\endgroup\$ – svick Oct 18 '12 at 23:16
  • \$\begingroup\$ @svick: Thanks, I never really thought about it, you're right. But I liked the dasblinkenlight's version and I guess I'll use that one, anyway. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 6:41
  • 1
    \$\begingroup\$ Thanks +1 for the fun Wikipedia read. :) This was a new data structure for me. \$\endgroup\$ – David Harkness Oct 19 '12 at 7:41
  • \$\begingroup\$ @David: Glad if you liked, I've read it again by the way (after your suggestion under the answer) and realized that "See Also" section also has some cool references. I guess I can use a "hashed array tree" in my scenario. Will give it a try. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 10:34
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ GetEnumerator seems quite more readable like this, thanks. I guess I created _NodeCount when I tried to implement IList<T> so I could use it in index-related calculations. It's useless here as you have pointed out. And another constructor for Node is also a great idea. +1 and thank you again. \$\endgroup\$ – Şafak Gür Oct 18 '12 at 14:18
  • 1
    \$\begingroup\$ C# has yield? Wow, that almost makes up for the choice to use I to prefix interfaces and capital letters for both methods and fields so they look like class names. :p Is yield return the actual syntax? Can you have yield without return? \$\endgroup\$ – David Harkness Oct 19 '12 at 7:43
  • \$\begingroup\$ @DavidHarkness Of course it does! (link) It has been there for many years, since C# 2.0. \$\endgroup\$ – dasblinkenlight Oct 19 '12 at 10:37
4
\$\begingroup\$

I would also remove the default constructor and add a default value to the other one

public UnrolledLinkedList(int nodeSize = 8)

This just removes a few lines of extra code.

\$\endgroup\$
  • \$\begingroup\$ Using a default parameter makes the constructor neater, thank you and +1. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 6:39
4
\$\begingroup\$
  1. Isn't the default node size of 8 too small? If you're dealing with huge amounts of data, I think it would make more sense to make the default much larger. If you're worried that that would waste too much memory, you could make the last node small at first and resize it when it gets full (until it reaches some size, which would mean you would create a new node).

  2. I think performing two assignments on a single line, the way you do in Add() can be confusing. I would rewrite it as:

    _LastNode.Next = new Node(_NodeSize);
    _LastNode = _LastNode.Next;
    

    Or at least drop the parenheses, they don't add anything useful here.

  3. Both branches in your Add() method have code that does the same thing, you should factor that out:

    public void Add(T item)
    {
        if (_LastNodeCount == _NodeSize)
        {
            _LastNode.Next = new Node(_NodeSize);
            _LastNode = _LastNode.Next;
            _LastNodeCount = 0;
            _NodeCount++;
        }
        _LastNode.Items[_LastNodeCount++] = item;
        _Count++;
    }
    
\$\endgroup\$
  • \$\begingroup\$ You're right about node size of 8, I'll increase that (what would you use btw? is ~64 fine?). Resizing is a good idea but I don't think that will be necessary. You're right about that line, too. I have a habbit that makes me think "shorter is always more readable" which is not right in cases like this. You also right about the Add method (you didn't set the _LastNodeCount, though), I'm going to change it like this. Thank you so much and +1 for your help. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 6:57
  • \$\begingroup\$ You're right, I didn't realize that I have to reset _LastNodeCount, fixed now. \$\endgroup\$ – svick Oct 19 '12 at 14:50
  • \$\begingroup\$ +1 but I disagree with the double-assignment. Leaving it on one line (when it fits) makes it clear that the two variables receive the same value. \$\endgroup\$ – David Harkness Oct 20 '12 at 4:27
3
\$\begingroup\$

Even though you are keeping every node full (except the last) and thus only need to track the number of elements in the last node, the code would be cleaner if you moved the count into Node. As well, it would allow you to implement the full functionality of IList more easily.

The implementations of Insert and Delete given this design will be slow because they'll have to shift all of the elements past the inserted/deleted element. Because there are multiple nodes you'll need two memory-copy calls per node. I don't know the equivalent in C# but assume it's similar to Java's System.arraycopy for moving elements from one array to another or within a single array.

\$\endgroup\$
  • \$\begingroup\$ It would be cleaner, yes. But I only keep track of the elements in the last node so I didn't want to add 4 more bytes to every node. I agree on implementing IList<T> means shifting the whole thing. So I guess I shouldn't implement IList<T> at all or explicitly implement the methods that manipulate the collection. +1 for review. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 6:55
  • \$\begingroup\$ Yes, if you need insert/delete you are better off paying the four bytes per node. Since you're concerned about node overhead, you should already be using a fairly large number of elements per node which means those four bytes pale in comparison. \$\endgroup\$ – David Harkness Oct 19 '12 at 7:40
  • \$\begingroup\$ You may be right. I guess it can help me to alter only one array instead of every array in every node if I implement a remove function. It can also be used in insert if an item is removed from that node before. Do I get your point? :) \$\endgroup\$ – Şafak Gür Oct 19 '12 at 7:45
  • \$\begingroup\$ Read the Wikipedia Page again for clarity. By allowing each node to range from half to completely full, you gain improvements in the time to insert and update. This is the classic speed vs. memory tradeoff. \$\endgroup\$ – David Harkness Oct 19 '12 at 9:15
2
\$\begingroup\$

I think there's a bug in your GetEnumerator. To wit, I believe the conditional to check the last index in the current node is backward:

var last = current.Next == null ? _NodeSize : _LastNodeCount;

should be

var last = current.Next == null ? _LastNodeCount : _NodeSize;

instead.

I have a few other changes I would personally make (for instance, seal the private Node class and not use public fields, but rather make them properties), but the updated version is quite good.

using System.Collections.Generic;

public sealed class UnrolledLinkedList<T> : IEnumerable<T>
{
    // Fields
    private readonly int nodeSize;

    private Node firstNode;

    private Node lastNode;

    private int lastNodeCount;

    // Constructors
    public UnrolledLinkedList(int nodeSize = 64)
    {
        this.nodeSize = nodeSize;
        this.Clear();
    }

    // Properties
    public int Count
    {
        get;

        private set;
    }

    // Methods
    public void Add(T item)
    {
        if (this.lastNodeCount == this.nodeSize)
        {
            this.lastNode.Next = new Node(this.nodeSize, item);
            this.lastNode = this.lastNode.Next;
            this.lastNodeCount = 1;
        }
        else
        {
            this.lastNode.Items[this.lastNodeCount++] = item;
        }

        this.Count++;
    }

    public void Clear()
    {
        this.Count = 0;
        this.firstNode = this.lastNode = new Node(this.nodeSize);
        this.lastNodeCount = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (var current = this.firstNode; current != null;)
        {
            var last = current.Next == null ? this.lastNodeCount : this.nodeSize;

            for (var i = 0; i != last; i++)
            {
                yield return current.Items[i];
            }

            current = current.Next;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    // Types
    private sealed class Node
    {
        private readonly T[] items;

        public Node(int size)
        {
            this.items = new T[size];
        }

        public Node(int size, T firstItem) : this(size)
        {
            this.items[0] = firstItem;
        }

        public T[] Items
        {
            get
            {
                return this.items;
            }
        }

        public Node Next
        {
            get;

            set;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You're right about the bug :) I fixed that. I also sealed the Node but I didn't change its fields to properties (since it's just a private class, accessing the fields directly seemed ok to me). Making Count an auto-implemented property on the other hand, looks pretty good. Thank you, and +1 for your suggestions. \$\endgroup\$ – Şafak Gür Oct 19 '12 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.