Linked list implementation along with unit test

Question

I've already made all the changes suggested here. Here is the link for round 2: Linked list implementation along with unit test [Round 2]

I want to see how other people think of my code, so here it goes. This is my first time writing a unit test. I'm wondering if there needs to be more tests for the LinkedList class and also if I'm writing them correctly.

I've made the Node class public so I can use it for a binary tree implementation later.

namespace DataStructuresAndAlgorithms.DataStructures
{
    public class Node<T>
    {
        public T Data { get; set; }
        public Node<T> Next { get; set; }
        public Node<T> Previous { get; set; }

        public Node() { }

        public Node(T t)
        {
            Data = t;
        }
    }
}

Implementation

using System;
using System.Collections.Generic;

namespace DataStructuresAndAlgorithms.DataStructures
{
    public class LinkedList<T>
    {
        public Node<T> Head { get; private set; }
        public Node<T> Tail { get; private set; }

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

        public void AddToFirst(Node<T> toAdd)
        {
            toAdd.Next = Head;
            Head = toAdd;
        }

        public void AddToLast(Node<T> toAdd)
        {
            Tail.Next = toAdd;
            Tail = toAdd;
        }

        public void RemoveFirst()
        {
            Head = Head.Next;
        }

        public void RemoveLast()
        {
            var pointer = Head;
            while (pointer.Next != Tail)
            {
                pointer = pointer.Next;
            }
            // pointer is now before Tail
            Tail = pointer;
            Tail.Next = null;
        }

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

Unit Test

using System;
using Xunit;

using DataStructuresAndAlgorithms.DataStructures;

namespace DataStructuresAndAlgorithms.DataStructures.Tests
{
    public class LinkedListTest
    {
        [Fact]
        public void AddToFirst_Node_Should_Become_Head()
        {
            // Arrange
            var myLinkedList = new LinkedList<int>(new Node<int>(45));

            // Act
            var nodeToAdd = new Node<int>(67);
            myLinkedList.AddToFirst(nodeToAdd);

            // Assert
            var theNode = GetNodeFromList<int>(myLinkedList, nodeToAdd);
            Assert.Equal(nodeToAdd, theNode);
            Assert.Equal(45, theNode.Next.Data);
        }

        [Fact]
        public void AddToLast_Node_Should_Become_Tail()
        {
            // Arrange
            var myLinkedList = new LinkedList<int>(new Node<int>(35));

            // Act
            var nodeToAdd = new Node<int>(14);
            myLinkedList.AddToLast(nodeToAdd);

            // Assert
            var theNode = GetNodeFromList<int>(myLinkedList, nodeToAdd);
            Assert.Equal(nodeToAdd, theNode);
        }

        [Fact]
        public void RemoveFirst_Next_Node_Should_Be_Head()
        {
            // Arrange
            var myLinkedList = new LinkedList<int>(new Node<int>(777));

            var node1 = new Node<int>(1);
            myLinkedList.AddToLast(node1);

            var node2 = new Node<int>(2);
            myLinkedList.AddToLast(node2);

            var node3 = new Node<int>(3);
            myLinkedList.AddToLast(node3);

            // Act
            myLinkedList.RemoveFirst();

            // Assert
            var theNode = GetNodeFromList<int>(myLinkedList, node1);
            Assert.Equal(node1, myLinkedList.Head);
        }

        [Fact]
        public void RemoveLast_Next_Node_Should_Be_Tail()
        {
            // Arrange
            var myLinkedList = new LinkedList<int>(new Node<int>(777));

            var node1 = new Node<int>(1);
            myLinkedList.AddToLast(node1);

            var node2 = new Node<int>(2);
            myLinkedList.AddToLast(node2);

            var node3 = new Node<int>(3);
            myLinkedList.AddToLast(node3);

            // Act
            myLinkedList.RemoveLast();

            // Assert
            var theNode = GetNodeFromList<int>(myLinkedList, node2);
            Assert.Equal(node2, myLinkedList.Tail);
        }

        public static Node<T> GetNodeFromList<T>(LinkedList<T> someLinkedList, Node<T> someNode) where T : struct
        {
            using (var itr = someLinkedList.GetEnumerator())
            {
                while (itr.Current != someNode)
                {
                    itr.MoveNext();
                }
                return itr.Current;
            }
        }
    }
}

Presentation

using System;
using System.Collections;

using DataStructuresAndAlgorithms.DataStructures;

namespace DataStructuresAndAlgorithms.Presentation.Console
{
    class Program
    {
        static void Main(string[] args)
        {
            RunNode();
            System.Console.WriteLine();
            RunLinkedList();
        }

        static void RunNode()
        {
            System.Console.WriteLine("Running the Node class");
            System.Console.WriteLine("----------------------");
            var myNode = new Node<int>(32);
            System.Console.WriteLine(myNode.Data);
        }

        static void RunLinkedList()
        {
            System.Console.WriteLine("Running the LinkedList class");
            System.Console.WriteLine("----------------------------");
            var myLinkedList = new LinkedList<int>(new Node<int>(99));
            myLinkedList.AddToFirst(new Node<int>(56));
            myLinkedList.AddToFirst(new Node<int>(23));
            myLinkedList.AddToFirst(new Node<int>(33));
            myLinkedList.AddToLast(new Node<int>(8888));
            myLinkedList.RemoveLast();
            myLinkedList.RemoveFirst();
            System.Console.WriteLine("HEAD = " + myLinkedList.Head.Data);
            System.Console.WriteLine("TAIL = " + myLinkedList.Tail.Data);

            using (var linkedListEnumerator = myLinkedList.GetEnumerator())
            {
                while (linkedListEnumerator.MoveNext())
                {
                    System.Console.WriteLine(linkedListEnumerator.Current.Data);
                }
            }
        }
    }
}

```

Answer 1

I've made the Node class public so I can use it for a binary tree implementation later

I don't think you can use this Node type as a node in a binary tree, because nodes in binary trees typically has references to other nodes like Parent, Left and Right. So IMO keep this Node class as a dedicated node type for this linked list:

  public class LinkedList<T>
  {
    class Node
    {
      public T Data { get; }
      public Node Next { get; set; }
      public Node Previous { get; set; }

      public Node(T data)
      {
        Data = data;
      }
    }

In this way you can skip the type parameter on the Node class. As shown above I've also made the Node class immutable for the Data property and hence no default constructor. It's easier to maintain, if you know that there is a one-to-one relationship between a data object and a Node.

---

public Node<T> Head { get; private set; }
public Node<T> Tail { get; private set; }

It's fine to have a public Head and Tail property, but they should be of type T and not Node. The client should be agnostic about the inner implementation of your list and only "communicate" objects of type T with it:

public T Head => _headNode.Data; // TODO check for null
public T Tail => _tailNode.Data; // TODO check for null

This will require that you have private nodes for head and tail as illustrated above.

---

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

Having a one and only constructor that takes a node (or item) is not a good idea, because you often want to instantiate an empty list and provide it as argument to a method or something like that. So your list should have a default constructor with no arguments:

public LinkedList()
{
}

You could also consider to have a constructor with a vector of items:

public LinkedList(IEnumerable<T> items)
{
  foreach (var item in items)
  {
    AddTail(item);
  }
}

---

public void AddToFirst(Node toAdd) {...}
    public void AddToLast(Node toAdd) {...}

You would typically call these methods AddHead and AddTail:

public void AddHead(T item) {...}
public void AddTail(T item) {...}

as you would call RemoveFirst() RemoveHead()...

---

public void AddToFirst(Node<T> toAdd)
{
  toAdd.Next = Head;
  Head = toAdd;
}

public void AddToLast(Node<T> toAdd)
{
  Tail.Next = toAdd; //OBS: This will fail if Tail is null!
  Tail = toAdd;
}

Your Node<T> class has a Previous property, why don't you use that (doubly linked list)?

---

public void RemoveFirst()
{
  Head = Head.Next;
}

This will fail, if Head is null.

---

public void RemoveLast()
{
  var pointer = Head;
  while (pointer.Next != Tail)
  {
    pointer = pointer.Next;
  }
  // pointer is now before Tail
  Tail = pointer;
  Tail.Next = null;
}

Why iterate through the entire list, when you have a reference to the last node in Tail?:

public void RemoveLast()
{
  if (Tail != null)
  {
    Tail = Tail.Previous;
    Tail.Next = null;
  }
}

You could consider to return the Data value from the removed nodes.

public T RemoveLast() {...}

---

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

It's fine to provide an enumerator. But it would be better to implement the IEnumerable<T> interface instead - where T is the T from your list - not Node<T>.

If you do that, instead of this

  using (var linkedListEnumerator = myLinkedList.GetEnumerator())
  {
    while (linkedListEnumerator.MoveNext())
    {
      Console.WriteLine(linkedListEnumerator.Current.Data);
    }
  }

you would be able to do

  foreach (var item in myLinkedList)
  {
    Console.WriteLine(item);
  }

And besides that, by implementing IEnumerable<T>, you'll be able to use LINQ extensions on the list. (see also VisualMelons comment).

---

Consider to implement this:

public bool Remove(T item)
{
  // TODO: implement this
  return <wasRemoved>;
}

---

You could try to implement the above and make a new post with an updated version with unit tests and we could then review that... :-)

Your use case should look as something like:

void RunLinkedList()
{
  Console.WriteLine("Running the LinkedList class");
  Console.WriteLine("----------------------------");
  var myLinkedList = new LinkedList<int>();
  myLinkedList.AddHead(99);
  myLinkedList.AddHead(56);
  myLinkedList.AddHead(23);
  myLinkedList.AddHead(33);
  myLinkedList.AddTail(8888);
  myLinkedList.RemoveTail();
  myLinkedList.RemoveHead();
  Console.WriteLine("HEAD = " + myLinkedList.Head);
  Console.WriteLine("TAIL = " + myLinkedList.Tail);

  foreach (var item in myLinkedList)
  {
    Console.WriteLine(item);
  }

}