3
\$\begingroup\$

Yesterday I posted my Generic List and received great feedback from it. I have taken the feedback to heart. Today I'm posting my take on the linked list in c#.

LinkedList.cs

using System;
using System.Collections;
using System.Linq;

namespace GenericDataStructures
{
    /// <summary>
    /// This is a singly Linked List Data Structure.
    /// </summary>
    public class SingleLinkedList<T>: ISingleLinkedList<T>, IEnumerable
    {
        /// <summary>
        /// This is the Node class that the list uses.
        /// </summary>
        private class Node
        {
            public T Value { get; private set; }
            public Node NextNode{ get; set;}
            public Node(T element)
            {
                Value = element;
                NextNode = null;
            }
            public Node(T element, Node previousNode): this(element)
            {
                previousNode.NextNode = this;
                NextNode = null;
            }
        }
        /// <summary>
        /// Head of the list.
        /// </summary>
        private Node Head;
        /// <summary>
        /// Tail of the list.
        /// </summary>
        private Node Tail;
        /// <summary>
        /// Implementatoin of the interace property.
        /// </summary>
        /// <value>Number of elements in the list</value>
        public int Count { get; private set;}
        /// <summary>
        /// Initializes a new instance of the <see cref="GenericDataStructures.SingleLinkedList`1"/> class.
        /// </summary>
        public SingleLinkedList()
        {
            Head = null;
            Tail = null;
            Count = 0;
        }
        /// <summary>
        /// Implementation of the interface method 
        /// </summary>
        public void Clear()
        {
            Head = null;
            Tail = null;
            Count = 0;
        }
        /// <summary>
        /// This is an implementation of its interface method
        /// </summary>
        /// <returns>Returns true if operation was successful. False if otherwise.</returns>
        /// <param name="element">Element to be added.</param>
        public bool Add(T element)
        {
            if (element == null)
            {
                throw new ArgumentNullException();
            }
            Node nodeToAdd = null;
            if (Count == 0)
            {
                nodeToAdd = new Node(element);
                Head = nodeToAdd;
                Tail = Head;
                Count++;
                return true;
            }
            else
            {
                nodeToAdd = new Node(element, Tail);
                Tail = nodeToAdd;
                Count++;
                return true;
            }
        } 
        /// <summary>
        /// Remove the first instance of the specified element from the list.
        /// </summary>
        /// <returns>This is an implementation of its interface method</returns>
        /// <param name="element">Element to be removed from the list</param>
        public bool Remove(T element)
        {
            Node nodeBeforeFoundNode = null;
            var currentNode = Head;
            if (element == null)
            {
                return false;
            }
            if (Count == 0)
            {
                return false;
            }
            while (!Equals(currentNode.Value, element))
            {
                nodeBeforeFoundNode.NextNode = currentNode;
                currentNode = currentNode.NextNode;
            }
            // Element was not found in the list.
            if (Equals(currentNode, null))
            {
                return false; 
            }
            // 2 cases,
            // 1. Head is to be removed
            // 2. Element to be removed is not the head
            if (currentNode == Head)
            {
                Head = currentNode.NextNode;
                Count--;
                return true;
            }
            nodeBeforeFoundNode.NextNode = currentNode.NextNode;
            Count--;
            return true;
        }
        /// <summary>
        /// This is an implementation of the interface method.
        /// </summary>
        /// <param name="element">Element.</param>
        /// <returns>True if operation was successful. False if otherwise.</returns>
        public bool Contains(T element)
        {
            if (Count == 0)
            {
                return false;
            }
            if (element == null)
            {
                throw new ArgumentNullException();
            }
            Node current = Head;
            while(!Equals(current, Tail))
            {
                current = current.NextNode;
            }
            if (Equals(current, null))
            {
                return false;
            }
            return true;
         }
        /// <summary>
        /// Implements the GetEnumerator method to allow the use
        ///  of foreach method in this class
        /// </summary>
        /// <returns>The enumerator.</returns>
        public IEnumerator GetEnumerator()
        {
            var node = Head;
            while (node != null)
            {
                yield return node.Value;
                node = node.NextNode;
            }
        }
    }
}

ILinkedList.cs

using System;
using System.Collections;

namespace GenericDataStructures
{
    public interface ISingleLinkedList<T>
    {
        /// <summary>
        /// Count property of list.
        /// </summary>
        /// <value>Number of elements in the list</value>
        int Count {get;}
        /// <summary> Add the specified element to the end of the list. </summary>
        /// <returns>
        /// Returns true if operation was successful. False if otherwise.
        /// </returns>
        /// <param name="element">Element to be added.</param>
        bool Add(T element);
        /// <summary>
        /// Remove the first instance of the specified element from the list. 
        /// </summary>
        /// <returns> True if operation was successful. False if otherwise</returns>
        /// <param name="element">Element to be removed from the list</param>
        bool Remove(T element);
        /// <summary>
        /// Clears all the elements inside the List and resets its Count property to 0.
        /// </summary>
        void Clear();
        /// <summary>
        /// Checks to see if the specified element is present in the list. 
        /// </summary>
        /// <param name="element">Element.</param>
        /// <returns> True if operation was successful. False if otherwise.</returns>
        bool Contains(T element);

    }
}

One question I have is about documenting my implementation. I've read mixed opinions on writing documentation on both the interface and its implementation. What's the technique that I should adopt?

\$\endgroup\$
  • 2
    \$\begingroup\$ One of the points in yesterday's feedback is also applicable here: you have a generic class that implements a non-generic IEnumerable interface, which means you can't use your class in place of an IEnumerable<T>, which means you're boxing value types into an object on iteration when you could fully leverage generics and avoid the boxing/unboxing penalty. It's also unclear why the class should implement ISingleLinkedList<T> rather than the more standard ICollection<T> which has pretty much the exact same members (plus CopyTo(T[], int) and IsReadOnly) and inherits IEnumerable<T>. \$\endgroup\$ – Mathieu Guindon Oct 17 '16 at 14:58
  • 1
    \$\begingroup\$ Please add a link to your previous question. \$\endgroup\$ – Heslacher Oct 18 '16 at 8:09
13
\$\begingroup\$

Correctness

Does it even work? Did you write unit tests for it?

For example I can't see where the Contains method makes any use of element argument (other than to assert it's not null).

public bool Contains(T element)
{
    if (Count == 0)
    {
        return false;
    }
    if (element == null)
    {
        throw new ArgumentNullException();
    }
    Node current = Head;
    while(!Equals(current, Tail))
    {
        current = current.NextNode;
    }
    if (Equals(current, null))
    {
        return false;
    }
    return true;
}

So how on earth is it able to correctly detect whether element is present in the collection?

Standardization

Custom collections should support standard .NET interfaces such as IList.

Otherwise other code can't really use it (other than as an IEnumerable) unless specifically refactored to do so.

Besides, your implementation doesn't allow inserting an element in between pre-existing elements, which pretty much defeats any major benefits of implementing a collection as a linked list.

Generics

As @MatsMug remarked already, it's supposed to be generic, yet - same as your previous implementation - it doesn't support IEnumerable<T>, only its non-generic, legacy version.

Documentation

It's good that you now use documentation comments (at least for a class that's supposed to be of general use). But this "this is" (as in "this is a singly linked list data structure" or "this is the Node class") is unnecessary. It's just fluff. We understand that it's a class, and that the comment must refer to this class, not some other class elsewhere.

Typos don't make great impression either ("Implementatoin").

If your class is opinionated about nullability (which is an improvement over your previous submission), this should be described in documentation comments.

As of now, your comments are stating the obvious, for example:

/// <summary>
/// Initializes a new instance of the <see cref="GenericDataStructures.SingleLinkedList`1"/> class.
/// </summary>
public SingleLinkedList()

But I know that a constructor initializes a new instance of a class. This is true for C# in general, and it's in no way specific to this class.

It may be a useful piece of info if I didn't know that sitting down to read this code, but it means these documentation comments become a C# tutorial for beginners now, which isn't their purpose.

Or:

<param name="element">Element.</param>

Who would have thunk! Not too informative...

In contrast, this code doesn't comment the non-obvious stuff.

For instance, now your class has a certain policy regarding nullability - which, as I said, is by itself an improvement over the previous code, where this policy was sort of accidental.

But is it obvious that Add(null) throws an exception whereas Remove(null) is ignored? I wouldn't have guessed that correctly, and yet the documentation doesn't say a word about it. It's too busy telling me that element is element.

By the way, it's not just a question of documentation - I'm not sure I like this asymmetry in principle.

And it isn't the only inconsistency lurking in the implementation, either. For example Contains(null) won't crash when the list is empty - but will if there are already elements in it. What's the rationale for that? :) That's not predictable behaviour in my book.

Speaking of Contains, this comment is just plain wrong:

/// <returns> True if operation was successful. False if otherwise.</returns>
bool Contains(T element);

Looking for an element and finding out that it's NOT present in the collection IS a successful operation. Just because an operation renderered a negative answer doesn't mean it failed. The purpose was to find this answer, and this we did.

Encapsulation

I don't like that Node.NextNode is public. Wouldn't a more restrictive visibility modifier do?

Rendundancies

As I pointed out before, else after a return is always redundant.

    return true;
}
else

doesn't make sense to me.

When your code is conditional, DRY (Don't Repeat Yourself) and try to extract whatever is common for all execution paths.

Eg.

if (Count == 0)
{
    nodeToAdd = new Node(element);
    Head = nodeToAdd;
    Tail = Head;
    Count++;
    return true;
}
else
{
    nodeToAdd = new Node(element, Tail);
    Tail = nodeToAdd;
    Count++;
    return true;
}

Could be replaced by:

if (Count == 0)
{
    nodeToAdd = new Node(element);
    Head = nodeToAdd;
}
else
{
    nodeToAdd = new Node(element, Tail);
    Tail = nodeToAdd;    
}
Count++;
return true;

Because the last two lines of code are the same for both cases.

Then there's the while loop iterating over the nodes sort of repeats in Remove and Contains. It's a bit of an awkward construct... which you already implemented once as IEnumerable. Why not reuse it? The class can just iterate over itself: foreach (T element in this). The clunkiness of traversing the list node by node gets abstracted away.

The main takeaway in my opinion is that you should start writing unit tests for your code. It not only helps to catch out bugs, but also implementation inconsistencies, as it forces you to think about the contract and all the edge cases.

I'd also put more emphasis on making code documentation actually useful for a hypothetical developer who'd want to use your code. Try to put yourself in their shoes: would you be happy having these comments to figure out how to use the class?

| improve this answer | |
\$\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.