1
\$\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\$
  • \$\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\$ – feature_creep Apr 3 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\$ – Krzysztof Skowronek Apr 3 at 10:01

Your Answer

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

Browse other questions tagged or ask your own question.