3
\$\begingroup\$

Here is the link to the next round of code review: Linked list implementation along with unit test [Round 3]

Here's the link to the previous code review: Linked list implementation along with unit test

Implementation

/*************************************************************************************************************
 *
 *  Special Thanks to Henrik Hansen for the awesome code review!
 *  Url: https://codereview.stackexchange.com/questions/216453/linked-list-implementation-along-with-unit-test
 *
 *************************************************************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;

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

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

        private Node _head, _tail;
        public T Head => _head == null ? throw new ArgumentNullException("Head is null") : _head.Data;
        public T Tail => _tail == null ? throw new ArgumentNullException("Tail is null") : _tail.Data;

        public LinkedList() { }

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

        public void AddHead(T item)
        {
            if (item == null)
                throw new ArgumentNullException("AddHead: An item you are trying to add is not initialized!");

            if (_head == null && _tail == null)
            {
                _head = new Node(item);
                _tail = _head;
            }
            else
            {
                _head.Previous = new Node(item);
                var temp = _head;
                _head = _head.Previous;
                _head.Next = temp;
            }
        }

        public void AddTail(T item)
        {
            if (item == null)
                throw new ArgumentNullException("AddTail: An item you are trying to add is not initialized!");

            if (_tail == null && _head == null)
            {
                _tail = new Node(item);
                _head = _tail;
            }
            else
            {
                _tail.Next = new Node(item);
                var temp = _tail;
                _tail = _tail.Next;
                _tail.Previous = temp;
            }
        }

        public void RemoveHead()
        {
            if (_head == null) return;
            else
            {
                _head = _head.Next;
                if (_head == null) return;
                _head.Previous = null;
            }
        }

        public void RemoveTail()
        {
            if (_tail == null) return;
            else
            {
                _tail = _tail.Previous;
                if (_tail == null) return;
                _tail.Next = null;
            } 
        }

        public bool Remove(T item)
        {
            var pointer = _head;
            while (pointer.Data.Equals(item) == false)
            {
                if (pointer.Next == null)
                    return false;
                pointer = pointer.Next;
            }

            if (pointer.Previous == null)
            {
                // It is the Head
                pointer.Next.Previous = null;
                return true;
            }
            if (pointer.Next == null)
            {
                // It is the Tail
                pointer.Previous.Next = null;
                return true;
            }
            pointer.Previous.Next = null;
            pointer.Next.Previous = null;
            return true;
        }

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

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

Unit Test

using System;
using Xunit;

using DataStructuresAndAlgorithms.DataStructures;

namespace DataStructuresAndAlgorithms.DataStructures.Tests
{
    public class LinkedListTest
    {
        [Fact]
        public void AddHead_Node_Should_Become_Head()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };
            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.AddHead(45);

            // Assert
            Assert.Equal(45, myLinkedList.Head);
        }

        [Fact]
        public void AddTail_Node_Should_Become_Tail()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };
            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.AddTail(7777);

            // Assert
            Assert.Equal(7777, myLinkedList.Tail);
        }

        [Fact]
        public void RemoveHead_Next_Node_Should_Be_Head()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };
            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.RemoveHead();

            // Assert
            Assert.Equal(2, myLinkedList.Head);
        }

        [Fact]
        public void RemoveTail_Next_Node_Should_Be_Tail()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };
            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.RemoveTail();

            // Assert
            Assert.Equal(4, myLinkedList.Tail);
        }
    }
}

Presentation

using System;
using System.Collections;

using DataStructuresAndAlgorithms.DataStructures;

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

        static void RunLinkedList()
        {
            System.Console.WriteLine("Running the LinkedList class");
            System.Console.WriteLine("----------------------------");
            var myLinkedList = new LinkedList<int>();
            myLinkedList.AddHead(54);
            myLinkedList.AddHead(44);
            myLinkedList.AddHead(96);
            myLinkedList.AddTail(300);
            myLinkedList.AddTail(900);
            myLinkedList.AddTail(77);
            myLinkedList.Remove(900);

            System.Console.WriteLine("HEAD = " + myLinkedList.Head);
            System.Console.WriteLine("TAIL = " + myLinkedList.Tail);

            foreach (var item in myLinkedList)
            {
                System.Console.WriteLine(item);
            }
        }
    }
}
```
\$\endgroup\$
  • \$\begingroup\$ I have found an error where it prints the wrong tail. I will be fixing this. This means I must be missing some tests. \$\endgroup\$ – feature_creep Mar 29 at 21:43
  • \$\begingroup\$ I find it difficult to add valuable tests like public void Head_Should_Only_Have_Previous_Equal_NULL() and public void Tail_Should_Only_Have_Next_Equal_NULL() when my _head and _tail member variables are set to private. \$\endgroup\$ – feature_creep Mar 29 at 22:33
3
\$\begingroup\$
  • Remove... family methods fail with an exception if from the list is of size 1. pointer.Previous == null does not mean that pointer.Next is not.

  • It is quite important to convey a success/failure of the removal to the caller. Remove should return at least a boolean.

  • I am not sure why do you disallow a Node having null data. In any case, if you want to enforce it, do it in a Node constructor, rather than in insertion methods.

  • AddHead should be streamlined. After all, the new Node is created in both branches, and becomes head no matter what. Lift the common functionality out:

    public void AddHead(T item)
    {
        var node = new Node(item);
        node.Next = _head;
    
        if (_head == null && _tail == null)
        {
            _tail = node;
        }
        else
        {
            _head.Previous = node;
        }
        _head = node;
    }
    

    Ditto for AddTail.

  • A while (pointer.Data.Equals(item) == false) loop deserves to become a Find method.

\$\endgroup\$
2
\$\begingroup\$

Much better.

I have the following to add to vnp's answer:

public T Head => _head == null ? throw new ArgumentNullException("Head is null") : _head.Data;
public T Tail => _tail == null ? throw new ArgumentNullException("Tail is null") : _tail.Data;

Instead of ArgumentNullException it's better to use NullReferenceException because there is no argument.


Instead of iterating this way:

  while (pointer.Data.Equals(item) == false)
  {
    if (pointer.Next == null)
      return false;
    pointer = pointer.Next;
  }

I find it more intuitive to do:

  Node node = _head;
  while (node != null)
  {
    if (item.Equals(node.Data))
    {
      break;
    }

    node = node.Next;
  }

  if (node == null) return false;

Instead of this:

  if (pointer.Previous == null)
  {
    // It is the Head
    pointer.Next.Previous = null;
    return true;
  }

consider reuse RemoveHead():

  if (node == _head)
  {
    RemoveHead();
    return true;
  }

That will be more DRY. And you can do the same for the tail.


You could consider to implement:

public bool IsEmpty { get; }
public int Count { get; }

You tests seems OK to me. You're missing one for Remove(T value).

About "Head_Should_Only_Have_Previous_Equal_NULL": unit tests are about testing the public interface of an object, so checking for _head.Previous == null should be tested indirectly through testing the public interface. In fact you'd have to test for it every time you make a change to the list. An indirect test could be trying to remove the head or tail from an empty list. If that doesn't fail, it may indicate that something is wrong with the handling of Node.Previous. In your case, you'll then have to throw or return false from RemoveHead() to find out...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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