Simple LinkedList

Question

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));
    }
}

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/… — Vlad Sandu
– Vlad Sandu, Commented Jan 18, 2019 at 14:23

Pieter Witvoet · Accepted Answer · 2019-01-18 15:52:05Z

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.

Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead. — Vlad Sandu
– Vlad Sandu, Commented Jan 20, 2019 at 16:38

Stack Exchange Network

Simple LinkedList

1 Answer 1

Collection != enumerator

Other notes

You must log in to answer this question.

Hot Network Questions

Simple LinkedList

1 Answer 1

Collection != enumerator

Other notes

You must log in to answer this question.

Related

Hot Network Questions