2
\$\begingroup\$

Here are the changes I've made thanks to suggestions made by @vnp, and @Henrik Hansen. Here is the link to the previous code review: Linked list implementation along with unit test - Round 2

I've made some new additions that were not mentioned and added more unit tests. I really feel like I'm improving!

Implementation

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

namespace DataStructuresAndAlgorithms.DataStructures
{
    public class LinkedList<T> : IEnumerable<T>
    {
        class Node
        {
            public T Data { get; set; }
            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 NullReferenceException() : _head.Data;
        public T Tail => _tail == null ? throw new NullReferenceException() : _tail.Data;
        public bool IsEmpty { get { return Count > 0 ? false : true; } }
        public int Count { get; private set; } = 0;

        public LinkedList() { }

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

        public void AddHead(T item)
        {
            var node = new Node(item);

            if (_head == null && _tail == null)
            {
                _head = node;
                _tail = node;
                Count += 1;
            }
            else
            {
                node.Next = _head;
                _head.Previous = node;
                Count += 1;
            }
            _head = node;
        }

        public void AddTail(T item)
        {
            var node = new Node(item);

            if (_tail == null && _head == null)
            {
                _head = node;
                _tail = node;
                Count += 1;
            }
            else
            {
                node.Previous = _tail;
                _tail.Next = node;
                Count += 1;
            }
            _tail = node;
        }

        public T RemoveHead()
        {
            if (_head == null) return default;
            else
            {
                var temp = _head.Next;
                _head = _head.Next;
                if (_head != null) _head.Previous = null;
                Count -= 1;
                if (temp == null) return default;
                return temp.Data;
            }
        }

        public T RemoveTail()
        {
            if (_tail == null) return default;
            else
            {
                var temp = _tail.Previous;
                _tail = _tail.Previous;
                if (_tail != null) _tail.Next = null;
                Count -= 1;
                if (temp == null) return default;
                return temp.Data;
            } 
        }

        public bool Find(T item)
        {
            if (_head == null || _tail == null) return false;
            var node = _head;
            while (node.Data.Equals(item) == false)
            {
                if (node.Next == null)
                    return false;
                node = node.Next;
            }
            return true;
        }

        public bool Remove(int index)
        {
            if (_head == null || _tail == null) return false;
            var node = _head;
            for (int i = 0; i < Count; i++)
            {
                if (i == index) break;
                node = node.Next;
            }
            // Remove the node
            if (node == null) return false;
            bool isRemoved = NodeAwareRemove(node);
            return isRemoved;
        }

        private bool NodeAwareRemove(Node node)
        {
            if (node.Next != null && node.Previous != null)
            {
                // In between nodes
                node.Previous.Next = node.Next;
                node.Next.Previous = node.Previous;
                Count -= 1;
                return true;
            }

            if (node.Next != null && node.Previous == null)
            {
                // Head node
                RemoveHead();
                return true;
            }

            if (node.Previous != null && node.Next == null)
            {
                // Tail node
                RemoveTail();
                return true;
            }

            if (node.Next == null && node.Previous == null)
            {
                // Only node
                _head = null;
                _tail = null;
                Count -= 1;
                return true;
            }
            return false;
        }

        public int RemoveAll(T item)
        {
            if (_head == null || _tail == null) return -1;
            var node = _head;
            int numberRemoved = 0;
            while (node != null)
            {
                if (node.Data.Equals(item))
                {
                    if (NodeAwareRemove(node)) numberRemoved += 1;
                }
                node = node.Next;
            }
            return numberRemoved;
        }

        public T GetIndex(int index)
        {
            if (index < 0) throw new IndexOutOfRangeException();
            if (index > Count) throw new IndexOutOfRangeException();
            if (index == 0) return _head.Data;

            var temp = _head;

            for (int i = 0; i < Count; i++)
            {
                if (i == index) break;
                temp = temp.Next;
            }

            return temp.Data;
        }

        public bool SetIndex(int index, T item)
        {
            if (index < 0) throw new IndexOutOfRangeException();
            if (index > Count) throw new IndexOutOfRangeException();
            if (index == 0) _head.Data = item;

            var temp = _head;

            for (int i = 0; i < Count; i++)
            {
                if (i == index) break;
                temp = temp.Next;
            }

            temp.Data = item;
            return true;
        }

        public object this[int i]
        {
            get { return GetIndex(i); }
            set { SetIndex(i, (T)value); }
        }

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

        [Fact]
        public void Find_5_Should_Return_True()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            var isFound = myLinkedList.Find(5);

            // Assert
            Assert.True(isFound);
        }

        [Fact]
        public void IsEmpty_Should_Return_False_Count_Equal_5()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            var isEmpty = myLinkedList.IsEmpty;

            // Assert
            Assert.False(isEmpty);
        }

        [Fact]
        public void IsEmpty_Should_Return_True_Count_Equal_0()
        {
            // Arrange
            int[] myNums = { };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            var isEmpty = myLinkedList.IsEmpty;

            // Assert
            Assert.True(isEmpty);
        }

        [Fact]
        public void GetIndex_4_Should_Equal_5()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            var index = myLinkedList.GetIndex(4);

            // Assert
            Assert.Equal(5, index);
        }

        [Fact]
        public void SetIndex_2_10_Should_Set_Index_2_To_10()
        {
            // Arrange
            int[] myNums = { 1, 2, 3, 4, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.SetIndex(2, 10);

            // Assert
            Assert.Equal(10, myLinkedList[2]);
        }

        [Fact]
        public void RemoveAll_Should_Delete_All_5s()
        {
            // Arrange
            int[] myNums = { 5, 5, 5, 3, 2, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            myLinkedList.RemoveAll(5);

            // Assert
            Assert.False(myLinkedList.Find(5));
        }

        [Fact]
        public void Remove_1_Should_Return_True()
        {
            // Arrange
            int[] myNums = { 5, 5, 5, 3, 2, 5 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            bool isRemoved = myLinkedList.Remove(1);

            // Assert
            Assert.True(isRemoved);
        }

        [Fact]
        public void Remove_2_Should_Return_False()
        {
            // Arrange
            int[] myNums = { 1 };

            var myLinkedList = new LinkedList<int>(myNums);

            // Act
            bool isRemoved = myLinkedList.Remove(2);

            // Assert
            Assert.False(isRemoved);
        }

        [Fact]
        public void AddHead_Should_Increment_Count()
        {
            // Arrange
            int[] myNums = { 1 };

            var myLinkedList = new LinkedList<int>(myNums);

            var theCount = myLinkedList.Count;

            // Act
            myLinkedList.AddHead(7);
            myLinkedList.AddHead(7);
            myLinkedList.AddHead(7);
            myLinkedList.AddHead(7);
            myLinkedList.AddHead(7);

            // Assert
            Assert.Equal(theCount + 5, myLinkedList.Count);
        }

        [Fact]
        public void Remove_2_Should_Decrement_Count()
        {
            // Arrange
            int[] myNums = { 1 };

            var myLinkedList = new LinkedList<int>(myNums);

            var theCount = myLinkedList.Count;

            // Act
            myLinkedList.RemoveTail();

            // Assert
            Assert.Equal(theCount - 1, myLinkedList.Count);
        }
    }
}

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(1);
            myLinkedList.AddHead(2);
            myLinkedList.AddHead(3);
            myLinkedList.AddHead(4);
            myLinkedList.AddHead(5);
            myLinkedList.RemoveHead();
            myLinkedList.RemoveTail();
            myLinkedList.SetIndex(2, 10);
            myLinkedList[2] = 2;
            System.Console.WriteLine("Count = " + myLinkedList.Count);
            System.Console.WriteLine("Is Empty = " + myLinkedList.IsEmpty);
            PrintList<int>(myLinkedList);
        }

        static void PrintList<T>(LinkedList<T> myList)
        {
            if (myList.Head == null || myList.Tail == null) return;

            var listText = "LinkedList[";
            for (int i = 0; i < myList.Count; i++)
            {
                listText += myList[i];
                if (i < myList.Count - 1)
                {
                    listText += "<";
                    listText += "---";
                    listText += ">";
                }
            }
            listText += "]";

            System.Console.WriteLine(listText);
            System.Console.WriteLine("Found Data = 66 -> " + myList.Find((T)(object)66));
            System.Console.WriteLine("Found Data = 3 -> " + myList.Find((T)(object)3));
        }
    }
}

\$\endgroup\$
2
  • \$\begingroup\$ I think that Find(T item) is kind of useless as it is right now. I think that it should return the indecies of all matches. \$\endgroup\$ Apr 3 '19 at 2:42
  • \$\begingroup\$ nice stuff, but since you are doing it in C#, I would suggest following C# standards. You want to implement a list, and there is an interface IList along with its generic version. Instead of inventing your own names for methods and your own methods, you can implement this standard interface. Then it will nicely play along with the whole framework. Also, it can support synchronization, so that's a nice next step \$\endgroup\$ Apr 3 '19 at 10:01
1
\$\begingroup\$

Exception

I know this conflicts with @Henrik Hansen's advice on your previous review, however rather than throwing NullReferenceException, I'd suggest throwing InvalidOperationException. Throwing NullReferenceException gives a bit too much information about the implementation details of your class. It also suggests that there's a problem with your implementation, rather than telling the client they are trying to do something wrong (get an object from an empty list). Switching to InvalidOperationException will also mean that your classes behaviour matches that of other standard collections such as Queue and Stack.

Consistency

You're mixing an matching single line function definitions:

public T Tail => _tail == null ? throw new NullReferenceException() : _tail.Data;
public bool IsEmpty { get { return Count > 0 ? false : true; } }

I don't see why you didn't do the same with IsEmpty that you've done with Tail/Head.

public bool IsEmpty => Count > 0 ? false : true; 

Double Checking

As soon as you put something into your list, you update both the _head and _tail. When you add to the head/tail at the moment, you're checking both:

 if (_head == null && _tail == null)

This seems redundant. Either the list will have something in it (in which case _head/_tail should both not be null), or the list will be empty (in which case both _head and _tail should be null. Which brings me on to...

Bug(s)

You have a bug in your RemoveHead method (and a corresponding one in RemoveTail). If the list contains only one item, then both _head and _tail point to the same Node. So, when you remove that node, both references will need to be updated. At the moment, RemoveHead updates the head, but not the tail, which means that tail points to a node that shouldn't be there anymore. This can lead to trouble. Consider the following test, which should pass, but fails with a NullReference.

[Fact]
public void RemoveHead_ThenAdd_Should_Set_Head_Tail()
{
    // Arrange
    int[] myNums = { 1 };
    var myLinkedList = new LinkedList<int>(myNums);
    Assert.Equal(1, myLinkedList.Head);
    Assert.Equal(1, myLinkedList.Tail);

    //Act
    myLinkedList.RemoveHead();
    myLinkedList.AddTail(5);

    //Assert
    Assert.Equal(5, myLinkedList.Tail);
    Assert.Equal(5, myLinkedList.Head);  // This fails with NullReference
}

Misleading Behaviour / Bug

When removing from the head/tail, you return a default value if the list is empty. This feels wrong, since you throw an exception if the client tries to access the head/tail values of an empty list. It feels like removing the head/tail of an empty list should throw the same exception.

It also looks like the remove head/tail methods are supposed to return the data value from the removed Node. They don't, they return the data value from the new head/tail, or default if there's only one item in the list. Seems like a bug. At best, it's confusing.

\$\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.