LinkedList Implementation Bug

Question

I tried to implement my linked list below, It just that when I used my linked list, it seems that it's inserting a null entry in the middle. Anyone could take a look? The problem could be in the add end method.

LinkedList<T>

     public class LinkedList<T> : IEnumerable<T>
    {
        public Node<T> Head { get; set; }
        public int Count { get; set; }

        public LinkedList()
        {
            Head = new Node<T>();

        }

        public void AddStart(T data)
        {
            if (Head == null)
            {
                Head = new Node<T> {Value = data};

            }
            else
            {
                var newNode = new Node<T> {Value = data, Next = Head};
                Head = newNode;
            }

            Count++;
        }

        public void AddEnd(T data)
        {
            var newNode = new Node<T> { Value = data, Next = null};
            var current = Head;
            if (Head == null)
            {
                Head = newNode;
            }
            else
            {
                while (current.Next != null)
                {                    
                    current = current.Next;
                }
                current.Next = newNode;                
            }
        }


        public IEnumerator<T> GetEnumerator()
        {
            Node<T> current = Head;
            while (current != null)
            {
                yield return current.Value;
                current = current.Next;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

Usage:

 LinkedList<string>  strings = new LinkedList<string>();            
    strings.AddStart("a");
    strings.AddStart("b");
    strings.AddStart("c");
    strings.AddEnd("a");
    strings.AddEnd("e");
    strings.AddEnd("d");

Result: (Notice the null in the middle)

c
b
a

a
e
d

Usage:

 LinkedList<string>  strings = new LinkedList<string>();
strings.AddStart("a");
strings.AddStart("b");
strings.AddStart("c");
strings.AddEnd("a");
strings.AddEnd("e");
strings.AddEnd("d");
strings.AddStart("a");
strings.AddEnd("b");
strings.AddStart("a");
strings.AddStart("b");
strings.AddStart("c");
strings.AddEnd("a");
strings.AddEnd("e");
strings.AddEnd("d");

Result: (Notice the null in the middle)

c
b
a
a
c
b
a

a
e
d
b
a
e
d

Answer 1

You are creating an empty Node, when you initialize your LinkedList:

public LinkedList()
{
    Head = new Node<T>();
}

At this point you essentially have a node without a value. This is displayed as an empty value.

Everytime you call AddStart, you insert items before hand. When calling AddEnd you insert items at the end. Since you call both methods equally, it appears that the initial node is in the middle.

You can resolve this by changing your constructor to this:

public LinkedList()
{
    Head = null;
}

Or by removing the constructor alltogether. In both methods you are checking for a Head node with a value, so you do not need to initialize it without a value.

if (Head == null)
{
    Head = new Node<T> {Value = data};
}

In your current state, you are checking if Head is null. Head is of Type Node, which, if it is a class, cannot be null, if you initialize it in your constrcutor (Head = new Node<T>(); //not null any longer). So you need to make up your mind on how you want to solve it.

Personally I'd just write a unit test to assert my logic and implementation is correct. If you assume that Head is null after initialisation, test for it:

[Fact]
public void AssertHeadIsNull()
{
    var list = new LinkedList<int>();
    Assert.Null(list.Head);
}

In your case, the test would have failed, and you could have backtracked the issue to your constructor.