1
\$\begingroup\$

I'm new to C# and would appreciate any feedback you might have on the following doubly-linked list implementation, particularly WRT the following language features:

  • Exception handling
  • Debug.Assert
  • Null state attributes (e.g. MaybeNullWhen)
  • The Try pattern with out params
  • Test style with xunit
  • Anything else that looks "weird" or unconventional

Thanks very much for your time! <3

Imlementation:

using System;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;

namespace DataStructures
{
    public class LinkedList<T>
    {
        public LinkedList(T val)
        {
            Add(val);
        }

        public LinkedList()
        {
        }

        public LinkedListNode<T>? HeadNode { get; set; }

        public LinkedListNode<T>? TailNode { get; set; }

        public int Count { get; private set; }

        public T GetHead()
        {
            return HeadNode is null ? throw new InvalidOperationException(nameof(HeadNode)) : HeadNode.Val;
        }

        public T GetTail()
        {
            return TailNode is null ? throw new InvalidOperationException(nameof(TailNode)) : TailNode.Val;
        }

        public T Add(T val, int? index = null)
        {
            return index switch
            {
                null => AddLast(val),
                0 => AddFirst(val),
                _ => index == Count ? AddLast(val) : AddToMiddle(val, index.Value)
            };
        }

        public void Clear()
        {
            HeadNode = null;
            TailNode = null;
            Count = 0;
        }

        public T GetAt(int index)
        {
            return GetNodeAt(index).Val;
        }

        public T RemoveAt(int index)
        {
            ValidateIndex(index);
            return Remove(GetNodeAt(index));
        }

        public bool TryRemoveFor(Predicate<T> predicate, [ MaybeNullWhen(false) ] out T removed)
        {
            if (TryFindNode(predicate, out LinkedListNode<T>? node))
            {
                removed = Remove(node);
                return true;
            }

            removed = default;
            return false;
        }

        public bool TryFind(Predicate<T> predicate, [ MaybeNullWhen(false) ] out T found)
        {
            if (TryFindNode(predicate, out LinkedListNode<T>? foundNode))
            {
                found = foundNode.Val;
                return true;
            }

            found = default;
            return false;
        }

        bool TryFindNode(Predicate<T> predicate, [ NotNullWhen(true) ] out LinkedListNode<T>? node)
        {
            node = HeadNode;
            while (node != null)
            {
                if (predicate(node.Val)) return true;
                node = node.Next;
            }

            return false;
        }

        LinkedListNode<T> GetNodeAt(int index)
        {
            ValidateIndex(index);

            Debug.Assert(TailNode != null, "The linked list should be non-empty");
            if (index == Count - 1)
            {
                return TailNode;
            }

            Debug.Assert(HeadNode != null, "The linked list should be non-empty");
            LinkedListNode<T> node = HeadNode;
            for (var i = 0; i != index; i++)
            {
                Debug.Assert(node != null, "All nodes within the linked list must be defined");
                Debug.Assert(node.Next != null, "This loop shouldn't run for the last entry in the linked list");
                node = node.Next;
            }

            return node;
        }

        T Remove(LinkedListNode<T> node)
        {
            if (node.Prev is null)
            {
                HeadNode = node.Next;
            }
            else
            {
                node.Prev.Next = node.Next;
            }

            if (node.Next is null)
            {
                TailNode = node.Prev;
            }
            else
            {
                node.Next.Prev = node.Prev;
            }

            Count--;
            if (Count <= 1) HeadNode = TailNode = HeadNode ?? TailNode;

            return node.Val;
        }

        T AddFirst(T val)
        {
            if (HeadNode is null) return AddLast(val);

            var newNode = new LinkedListNode<T>(val);
            HeadNode.Prev = newNode;
            HeadNode = newNode;
            Count++;
            return newNode.Val;
        }

        T AddToMiddle(T val, int index)
        {
            ValidateIndex(index, 1);
            var newNode = new LinkedListNode<T>(val);
            LinkedListNode<T> toShift = GetNodeAt(index);
            LinkedListNode<T>? precedingNode = toShift.Prev;
            Debug.Assert(precedingNode != null, "index should not refer to the head");

            precedingNode.Next = newNode;
            newNode.Prev = precedingNode;
            toShift.Prev = newNode;
            newNode.Next = toShift;
            Count++;
            return val;
        }


        T AddLast(T val)
        {
            var newNode = new LinkedListNode<T>(val);
            if (HeadNode is null)
            {
                HeadNode = TailNode = newNode;
            }
            else
            {
                Debug.Assert(TailNode != null, "Head and tail should both be either null or non-null");

                TailNode.Next = newNode;
                newNode.Prev = TailNode;
                TailNode = newNode;
            }

            Count++;
            return newNode.Val;
        }

        void ValidateIndex(int index, int lowerBoundInclusive = 0)
        {
            if (index >= lowerBoundInclusive ||
                index < Count)
            {
                return;
            }

            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }

    public class LinkedListNode<T>
    {
        public LinkedListNode(T val, LinkedListNode<T>? prev = null, LinkedListNode<T>? next = null)
        {
            Val = val;
            Prev = prev;
            Next = next;
        }

        public LinkedListNode<T>? Next { get; set; }

        public LinkedListNode<T>? Prev { get; set; }

        public T Val { get; }
    }
}

Tests:

using System;
using DataStructures;
using Xunit;

namespace TestDataStructures
{
    public class LinkedListTest
    {
        const int TestValue = -100;

        [ Fact ]
        public void InitializeEmptyTest()
        {
            var ll = new LinkedList<int>();
            Assert.Equal(0, ll.Count);
            Assert.Null(ll.HeadNode!);
            Assert.Null(ll.TailNode!);
            Assert.Throws<InvalidOperationException>(() => ll.GetHead());
            Assert.Throws<InvalidOperationException>(() => ll.GetTail());
        }

        [ Fact ]
        public void InitializeNonEmptyTest()
        {
            var ll = new LinkedList<int>(TestValue);
            Assert.Equal(1, ll.Count);
            Assert.NotNull(ll.HeadNode!);
            Assert.NotNull(ll.TailNode!);
            Assert.Equal(TestValue, ll.GetHead());
            Assert.Equal(TestValue, ll.GetTail());
        }

        [ Fact ]
        public void AddTest()
        {
            const int numToAdd = 5;
            var ll = new LinkedList<int>();
            for (var i = 0; i < numToAdd; i++)
            {
                int added = ll.Add(i);
                Assert.Equal(i, added);
            }

            LinkedListNode<int>? node = ll.HeadNode;
            for (var i = 0; i < numToAdd; i++)
            {
                Assert.Equal(i, node?.Val);
                node = node?.Next;
            }

            Assert.Equal(numToAdd, ll.Count);
        }

        [ Theory ]
        [ InlineData(0, 0) ]
        [ InlineData(3, 0) ]
        [ InlineData(3, 1) ]
        [ InlineData(3, 2) ]
        [ InlineData(5, 3) ]
        [ InlineData(3, 3) ]
        public void AddAtIndexTest(int collectionSize, int? insertIndex = null)
        {
            var ll = new LinkedList<int>();
            for (var i = 0; i < collectionSize; i++)
            {
                ll.Add(i);
            }

            int added = ll.Add(TestValue, insertIndex);
            Assert.Equal(TestValue, added);

            LinkedListNode<int>? node = ll.HeadNode;
            for (var i = 0; i != insertIndex; i++)
            {
                node = node?.Next;
            }

            Assert.Equal(TestValue, node?.Val);
            Assert.Equal(collectionSize + 1, ll.Count);
        }

        [ Fact ]
        public void ClearTest()
        {
            const int numToAdd = 3;
            var ll = new LinkedList<int>();
            for (var i = 0; i < numToAdd; i++)
            {
                int added = ll.Add(i);
                Assert.Equal(i, added);
            }

            ll.Clear();
            Assert.Equal(0, ll.Count);
            Assert.Null(ll.HeadNode!);
            Assert.Null(ll.TailNode!);
            Assert.Throws<InvalidOperationException>(() => ll.GetHead());
            Assert.Throws<InvalidOperationException>(() => ll.GetTail());
        }

        [ Theory ]
        [ InlineData(0, 3) ]
        [ InlineData(1, 3) ]
        [ InlineData(2, 3) ]
        public void GetAtTest(int getIndex, int collectionSize)
        {
            var ll = new LinkedList<int>();
            for (var i = 0; i < collectionSize; i++)
            {
                ll.Add(i);
            }

            int got = ll.GetAt(getIndex);
            Assert.Equal(getIndex, got);
        }

        [ Theory ]
        [ InlineData(3, 0, 0) ]
        [ InlineData(3, 1, 1) ]
        [ InlineData(3, 2, 2) ]
        [ InlineData(3, 3) ]
        [ InlineData(3, -1) ]
        public void TryFindTest(int collectionSize, int toCompare, int? expected = null)
        {
            bool Predicate(int i)
            {
                return i == toCompare;
            }

            var ll = new LinkedList<int>();
            for (var i = 0; i < collectionSize; i++)
            {
                ll.Add(i);
            }

            bool wasFound = ll.TryFind(Predicate, out int got);
            Assert.Equal(expected.HasValue, wasFound);
            Assert.Equal(expected ?? default, got);
        }

        [ Theory ]
        [ InlineData(0, 3) ]
        [ InlineData(1, 3) ]
        [ InlineData(2, 3) ]
        [ InlineData(2, 5) ]
        public void RemoveAtTest(int removeIndex, int collectionSize)
        {
            var ll = new LinkedList<int>();
            for (var i = 0; i < collectionSize; i++)
            {
                ll.Add(i);
            }

            int got = ll.RemoveAt(removeIndex);
            Assert.Equal(removeIndex, got);
            Assert.Equal(collectionSize - 1, ll.Count);
        }

        [ Theory ]
        [ InlineData(3, 0, 0) ]
        [ InlineData(3, 1, 1) ]
        [ InlineData(3, 2, 2) ]
        [ InlineData(3, 3) ]
        [ InlineData(3, -1) ]
        public void RemoveForTest(int collectionSize, int toCompare, int? expected = null)
        {
            bool Predicate(int i)
            {
                return i == toCompare;
            }

            var ll = new LinkedList<int>();
            for (var i = 0; i < collectionSize; i++)
            {
                ll.Add(i);
            }

            bool wasFound = ll.TryRemoveFor(Predicate, out int got);
            Assert.Equal(expected.HasValue, wasFound);
            Assert.Equal(expected ?? default, got);
            Assert.Equal(wasFound ? collectionSize - 1 : collectionSize, ll.Count);
        }
    }
}
```
\$\endgroup\$
5
  • \$\begingroup\$ If someone with 300+ rep could create the nullable-reference-types tag I'll add it to this question. StackOverflow has the feature tagged with that name, so best to keep it the same. \$\endgroup\$
    – Manningham
    Apr 1 at 5:28
  • 3
    \$\begingroup\$ Please don't edit the question after it has been answered, especially the code. Everyone must be able to view the code as the original reviewer did. \$\endgroup\$
    – pacmaninbw
    Apr 1 at 12:55
  • \$\begingroup\$ @pacmaninbw Ah, I left the original question's code alone and just added a new section with the updated code according to the feedback I got, the header explained this. I've seen that done on stack overflow, but if it's frowned upon I'll not do it again. \$\endgroup\$
    – Manningham
    Apr 1 at 13:08
  • 1
    \$\begingroup\$ For more information, please see what you may and may not do after receiving answers. \$\endgroup\$
    – Mast
    Apr 1 at 16:19
  • \$\begingroup\$ @Mast Great post, thanks for that! I'll be sure not to edit the question in this way again :) \$\endgroup\$
    – Manningham
    Apr 2 at 2:18
2
\$\begingroup\$

In this review I'll focus on the implementation.

LinkedList

I have two problem with this name:

I would highly recommend you to scrutinize the built-in class before you start to re-invent the wheel.

Just to name a few things:

  • There is a ctor which can receive an IEnumerable
    • This is a really powerful feature to help integrate with other collections
  • CopyTo is yet again an extremely useful method from integration perspective
  • There are methods like AddAfter, AddBefore which can ease the usage
    • Because we do not need to know the index
  • GetEnumerator provides the ability to use foreach loops
    • In your case GetForwardXYZ and GetBackwardXYZ would make sense also

In case of doubly linked list it might not make too much sense to expose things like: Head and Tail. Their meaning are true only in case of forward iteration. But if you provide backward iteration as well their semantics break.

LinkedListNode

LinkedListNode yet again this is also a built-in type

  • It has a really useful property called List
    • This give you a pointer to that LinkedList where this node belongs

Unnecessary abbreviations:

  • T val >> T value
  • Prev >> Previous

IMO these are just making your API look weird.

  • If you don’t need to abbreviate then don’t do that

GetHead / GetTail

  • Personally I prefer this kind of one-liners:
    • if data is present then return that one otherwise fallback
  • In case of C# 9:

public T GetHead() => HeadNode is not null ? HeadNode.Val : throw new InvalidOperationException(nameof(HeadNode));
  • In case of C# 8:
public T GetHead() => HeadNode?.Val ?? throw new InvalidOperationException(nameof(HeadNode));
  • Please bear in mind that this could work only if you restrict T either to struct or class

Add

  • I think instead of int? index = null I would use int? index = default
    • It expresses the intent in a bit more clear way
  • I would split your default case in your switch expression like this:
public T Add(T val, int? index = null)
    => index switch
    {
        null => AddLast(val),
        0 => AddFirst(val),
        _ when index == Count => AddLast(val),
        _ => AddToMiddle(val, index.Value)
    };
  • Maybe it might make sense to split this method into two: Add and AddAt

TryRemoveFor, TryFind

  • They had a huge resemblance, it might make sense to have a common ground
  • I’m not really a huge fan of naming like Predicate<T> predicate
    • I prefer names like nodeSelector, nodeValueMatcher, etc.

GetNodeAt / Remove

  • node.Next might have null, because it has a public setter that means you can easily have NullReferenceException here
  • Same applies to node.Prev.Next and node.Next.Prev

ValidateIndex

  • Even though ArgumentOutOfRangeException does not have a ctor where you can specify the allowed range, I do recommend to provide helpful error message, something like this:

The allowed range is [0…n], the provided index is n+3. Please try to provide index inside the range.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks very much, there's some great advice here! I'll make some changes. I'll edit the original post to make it clear that this was just a code exercise and I'm not intending to use this implementation in an application. I would definitely use System.Collections.Generic.LinkedList in that case. \$\endgroup\$
    – Manningham
    Apr 1 at 10:41
  • 1
    \$\begingroup\$ WRT TryRemoveFor and TryFind, good point they are super similar. I merged them but then decided to pull them apart again - they're pretty simple functions and not much was saved by having a common base. I often wait until I have 3 repetitions before refactoring, anyways. WRT the potential NullReferenceExceptions, yes good point! I added some exceptions to the code, but I guess if I wanted to do this properly I would add safety guards to ensure consumers couldn't inject null nodes to the middle of the list. \$\endgroup\$
    – Manningham
    Apr 1 at 11:45

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.