9
\$\begingroup\$

I guess this has been made a couple of times by now, but i wanted to take my chance on creating a simple generic linked list in c#. What do you think ?

This is the main class.

public class LinkedList<T>: IEnumerator<T>
{
    private Node<T> head;
    private Node<T> tail;


    public T Current
    {
        get { return myCurrentNode.GetValue(); }
    }

    object IEnumerator.Current => Current;

    private Node<T> myCurrentNode;

    public LinkedList()
    {
        head = null;
        tail = null;
    }


    public void Add(T value)
    {
        if (head == null && tail == null)
        {
            head = new Node<T>(value);
            tail = head;
            Reset();
            return;
        }

        tail.SetNextNode(new Node<T>(value));
        tail = tail.GetNextNode();
    }

    public void RemoveCurrentNode()
    {
        var node = new Node<T>();
        node.SetNextNode(head);

        while (node.GetNextNode() != myCurrentNode)
        {
            node = node.GetNextNode();
        }

        var nextNode = myCurrentNode.GetNextNode();
        node.SetNextNode(nextNode);

        if (head == myCurrentNode)
        {
            head = nextNode;
        }

        if (tail == myCurrentNode)
        {
            tail = node;
        }

        myCurrentNode = nextNode;
    }

    public bool MoveNext()
    {
        var nextNode = myCurrentNode.GetNextNode();
        if (nextNode != null)
        {
            myCurrentNode = nextNode;
            return true;
        }

        return false;
    }

    public void Reset()
    {
        myCurrentNode = new Node<T>();
        myCurrentNode.SetNextNode(head);
    }

    public void Dispose()
    {
        myCurrentNode = null;
        head = null;
        tail = null;
    }
}

Node class.

public class Node<T>
{
    private T _value;
    private Node<T> _nextNode;

    public Node()
    {

    }

    public T GetValue()
    {
        return _value;
    }

    public Node(T Value)
    {
        _value = Value;
    }

    public Node<T> GetNextNode()
    {
        return _nextNode;
    }

    public void SetNextNode(Node<T> nextNode)
    {
        _nextNode = nextNode;
    }
}

And three unit tests to check my implementation.

public class LinkedListTest
{
    private LinkedList.LinkedList<int> linkedList;
    private List<int> initialList;

    [Fact]
    public void LinkedListCanBeEnumerated()
    {
        //arange
        InitializeLinkedList(100);

        //act
        int[] array = new int[100];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
    }

    private void InitializeLinkedList(int howMany)
    {
        linkedList = new LinkedList.LinkedList<int>();
        initialList = Enumerable.Range(1, howMany).ToList();
        initialList.ForEach(i => linkedList.Add(i));
    }

    [Fact]
    public void RemovingCurrentNodeShouldAlterTheList()
    {
        //arange
        InitializeLinkedList(100);

        //act
        linkedList.MoveNext();
        linkedList.RemoveCurrentNode();
        linkedList.Reset();

        int[] array = new int[100];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => i.ShouldNotBe(1));

    }

    [Fact]
    public void RemovingTailNodeShouldResultInADifferentTailNode()
    {
        //arange
        InitializeLinkedList(3);

        //act
        linkedList.MoveNext();
        linkedList.MoveNext();
        linkedList.MoveNext();

        linkedList.RemoveCurrentNode();
        linkedList.Reset();

        int[] array = new int[3];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => i.ShouldNotBe(3));
    }
}
\$\endgroup\$
  • \$\begingroup\$ I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, both head and tail are null), you create two nodes, one in the Add method, and one in Reset which is called from Add. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure. \$\endgroup\$ – Abigail Jan 18 at 13:42
  • \$\begingroup\$ I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/… \$\endgroup\$ – user297876 Jan 18 at 14:23
16
\$\begingroup\$

Collection != enumerator

The main problem I see here is that LinkedList<T> implements IEnumerator<T> instead of IEnumerable<T>. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext() and Current, instead of being able to use foreach. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.

IEnumerable<T> represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield).

IEnumerator<T> represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach statement (which calls GetEnumerator on the given enumerable to obtain an enumerator).


The above means that myCurrentNode does not belong in this class - it should be part of an enumerator. The same goes for Current, MoveNext, Reset and Dispose.

Regarding RemoveCurrentNode, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode also has to perform a linear search to find the preceding node.

Take a look at System.Collections.Generic.LinkedList<T> to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.

Other notes

  • IEnumerator.Reset is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception in Reset.
  • Note that IEnumerable<T>.GetEnumerator is quite easy to implement with yield.
  • There's no need to initialize head and tail to null - that's their default value already.
  • There's also no need for disposal here - there are no unmanaged resources here that require disposal.
  • Why does Node use Java-style get and set methods instead of properties? I'd expect to see public T Value { get; } and public Node<T> NextNode { get; set; }.
  • Personally I would handle the head == myCurrentNode edge-case in RemoveCurrentNode without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation).
  • A LinkedList(IEnumerable<T> collection) constructor would be useful.
\$\endgroup\$
  • \$\begingroup\$ Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead. \$\endgroup\$ – user297876 Jan 20 at 16:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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