Simple Linked List

Question

I've implemented a simple linked list in C# using generic T for values. I did not inherit from any of .Net's fun and helpful classes like IEnumerable<T>, or IList<T> :D. This is just after an hours worth of work. I've tested everything and I believe it all works well enough, but before I go on to add more methods, or make the actual data-structure more complex I'm looking for some feedback on what I have. Critiques on everything are welcome, perhaps there is some glaring issue that I have not addressed.

As far as my nodes having a previous and next value, that is because I did intend to have quicker searching iterating backwards through, and some other stuff that is not yet implemented. While right now do use both properties of the node, I know I could avoid it. But I have kept it in and use it because I do plan to implement more stuff later.

This is supposed to emulate the List class. I've called mine Jist to not confuse anyone. I also have considered taking away the JNode constructor, because all the properties are public anyway, but I've decided against that, because I don't want any accidentally null values... while default values are fine, I don't want any in there by accident.

class JNode<T>
{
    public T Value { get; set; }
    public JNode<T> Next { get; set; }
    public JNode<T> Previous { get; set; }

    public JNode(T value) { Value = value; }
}

public class Jist<T>
{
    #region Private Members
    private JNode<T> _first;
    private JNode<T> _last;

    #endregion

    #region Public Properties
    public UInt64 Count { get; private set; }

    public T this[UInt64 index]
    {
        get { return NodeAtIndex(index).Value; }
        set { NodeAtIndex(index).Value = value; }
    }

    #endregion

    #region Constructor
    public Jist()
    {
        Count = 0;
        _first = new JNode<T>(default(T));
        _last = new JNode<T>(default(T));
        LinkNodes(_first, _last);
    }

    #endregion

    #region Public Methods
    public void Add(T value)
    {
        InsertBeforeNode(_last, value);
    }

    public void Clear()
    {
        LinkNodes(_first, _last);
        Count = 0;
    }

    public bool Contains(T value)
    {
        return FirstNodeWithValue(value) != null;
    }

    public void Insert(T value, UInt64 index)
    {
        if (index > Count)
            throw new IndexOutOfRangeException("Index(" + index + ") cannot be greater than Count(" + Count + ")");
        InsertBeforeNode(NodeAtIndex(index), value);
    }

    public UInt64? IndexOf(T value)
    {
        return IndexOfFirstNodeWithValue(value);
    }

    public bool Remove(T value)
    {
        var node = FirstNodeWithValue(value);
        if (node != null)
            LinkNodes(node.Previous, node.Next);
        return node != null;
    }

    #endregion

    #region Private Methods
    private void InsertBeforeNode(JNode<T> node, T value)
    {
        if (Count == UInt64.MaxValue)
            throw new ArgumentException("List can not grow larger than " + UInt64.MaxValue + " nodes large.");

        var nn = new JNode<T>(value);
        LinkNodes(node.Previous, nn);
        LinkNodes(nn, node);
        Count++;
    }

    private void LinkNodes(JNode<T> first, JNode<T> second)
    {
        first.Next = second;
        second.Previous = first;
    }

    private JNode<T> NodeAtIndex(UInt64 index)
    {
        if (index > Count - 1)
            throw new IndexOutOfRangeException("Index(" + index + ") cannot be greater than Count(" + Count + " - 1)");

        JNode<T> node = _first.Next;
        for (UInt64 i = 0; i < index; i++)
            node = node.Next;
        return node;
    }

    private JNode<T> FirstNodeWithValue(T value)
    {
        JNode<T> node = _first.Next;
        for (UInt64 i = 0; i < Count; i++)
            if (EqualityComparer<T>.Default.Equals(node.Value, value))
                return node;
            else
                node = node.Next;
        return null;
    }

    private UInt64? IndexOfFirstNodeWithValue(T value)
    {
        UInt64 i = 0;
        for (JNode<T> node = _first.Next; !EqualityComparer<T>.Default.Equals(node.Value, value); node = node.Next)
            if (i >= Count) return null;
            else i++;
        return i;
    }

    #endregion
}

Answer 1

Overall, this isn't bad. I do see a few things that bug me though.

1. Regions - I find they clutter up the code and don't add much value. I would not use them.

2. Code blocks, regardless how many lines they are should be surrounded by {}. This makes it much easier for your eyes to line code up. There are a few cases where I think this can be ignored (see point 3)

   if (node != null)
   {
       LinkNodes(node.Previous, node.Next);
   }
   
   for (UInt64 i = 0; i < index; i++)
   {
       node = node.Next;
   }
   

3. The else statement in the following code is redundant because of the return. This is one of those cases I'm on the fence about having {} around code blocks.

   for (UInt64 i = 0; i < Count; i++)
   {
       if (EqualityComparer<T>.Default.Equals(node.Value, value)) return node;
   
       node = node.Next;
   }
   

4. Add UL to numbers to avoid having to use the type declaration. This will allow you to use var instead.

   for (var i = 0UL; i < Count; i++)
   {
       if (EqualityComparer<T>.Default.Equals(node.Value, value)) return node;
   
       node = node.Next;
   }
   

5. The variable nn is not named very well. Try something like newNode to make the intent more visible.

Answer 2

Well done for making it a doubly-linked list (i.e. Next and Prev members of JNode): that improves performance of insert and remove in the middle of the list.

However that performance improvement is wasted by the fact that you always need to search through the list in the first place (so you know, from searching, what the previous node is), to find the node you want to insert or delete.

---

I suspect it would be neater to use a nested class:

public class Jist<T>
{
    class JNode
    {
        public T Value { get; set; }
        public JNode Next { get; set; }
        public JNode Previous { get; set; }

        public JNode(T value) { Value = value; }
    }

    #region Private Members
    private JNode _first;
    private JNode _last;

    ... etc ...

JNode doesn't presently appear in the public API.

It would be dangerous to add JNode to the public API (e.g. to implement a method which returns the JNode in which a value is contained) because JNode has public Prev and Next properties which the user code should be allowed to set.

---

I'm not sure about using UInt64 as your counter type: standard System.Collection types make do with int.

---

The performance of the indexer ...

public T this[UInt64 index]

... is potentially very slow: because you need to iterate to find the requested node. IOW the API looks like an array but its performance doesn't. Equivalent System.Generic classes such as Queue<> don't implement this API, perhaps (or IMO, probably) because they cannot implement it well/performantly.

---

NodeAtIndex doesn't ensure that index is smaller than Count.

Answer 3

In your public Insert method, the argument check

if (index > Count)
    throw new IndexOutOfRangeException("Index(" + index + ") cannot be greater than Count(" + Count + ")");

is off by one. It should be Count - 1. Your current code will forgive this oversight, because the NodeAtIndex method it calls to retrieve the node also has an argument check, with the correct max value. But if you're going to put in an argument check, it should be correct.

If my assumption is wrong, and you intended to allow inserting at Count (i.e. after the last item), then you have a different problem, because NodeAtIndex will throw an exception when you try that.