8
\$\begingroup\$

I am trying to learn C# and created this project to improve. I will be using C# professionally so a harsh critique is welcome.

class Node<T>
{
    public T value;
    public Node<T>? next;
    public Node(T val, Node<T>? n)
    {
        value = val;
        next = n;
    }
}

public class LinkedList<T> : IEnumerable<T>
{

    Node<T>? head;

    public LinkedList()
    {
        head = null;
    }
    public LinkedList(IEnumerable<T> values)
    {
        foreach (var v in values)
        {
            append(v);
        }
    }

    public void append(T val)
    {
        Node<T> node = new Node<T>(val, head);
        head = node;
    }

    public T peek()
    {
        if (head == null)
        {
            throw new Exception("Empty list");
        }
        return head.value;
    }

    public T pop()
    {
        if (head == null)
        {
            throw new Exception("Empty list");
        }
        var temp = head.value;
        head = head.next;
        return temp;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var node = head;
        while (node != null)
        {
            var temp = node.value;
            node = node.next;
            yield return temp;
        }
    }

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

I am really bothered that peek() and pop() have to throw errors. I tried returning T? but the compiler refused it because T can be a value type. In other languages I would have used Option<T>. I could have also returned default(T) which is even worse because you do not know if you are getting the default value or an actual value (such as 0).

\$\endgroup\$
2
  • \$\begingroup\$ Is there any particular reason why did you choose to implement your own version of LinkedList? \$\endgroup\$ Commented Jun 25 at 12:16
  • \$\begingroup\$ @PeterCsala The beginner tag hints that it can be a learning exercise. And not an unusual one, BTW. \$\endgroup\$
    – Alejandro
    Commented Jun 26 at 18:22

2 Answers 2

20
\$\begingroup\$

Substance

The following issues are substantive, and unrelated to a particular coding style.

append does not append.

Append means adding to the end. Your append method actually prepends to the start of the list. Change the name to "prepend" or "push".

Your constructor reverses the order of its inputs

Because of the prepend behavior above, if I call new LinkedList<int>(new int[] {0, 1, 2, 3, 4});, I will get a list of {4, 3, 2, 1, 0}. Call values.Reverse() to prepend the values in reverse order.

Do not throw the Exception base class

peek and pop throwing is fine and is standard practice in C# - however you should throw a typed exception. System.Collections.Generic.Queue<T> throws InvalidOperationException if you attempt to dequeue when its empty, so I believe you should do the same here.

The Exception base class should never be thrown, nor caught, in production code.

Consider adding methods which try peek or try pop

In order to avoid exceptions, the idiomatic approach in C# is to have methods whose name starts with Try which return bool, with their data in an out parameter. For example

public bool TryPop(out Node<T> result)
{
    if (head == null)
    {
        result = null;
        return false;
    }

    result = head.value;
    head = head.next;
    return true;
}

These methods should be in addition to the direct pop and peek methods. Furthermore, because constructing an Exception object is expensive, I recommend implementing Peek in terms of TryPeek rather than vice-versa.

Use is to check for null

The equality operator == is not quite as dangerous in C# as it is in javascript, but it still can be overridden to do unexpected things. While if (foo == null) would be perfectly acceptable in most codebases, if (foo is null) should be preferred as it is guaranteed to do what you expect.

Style

While the language itself doesn't mandate any particular style, the .NET Coding Convention which is obeyed by .NET itself is often recommended as a starting point for C# coding styles and are obeyed by most popular packages on NuGet. There are also things which aren't spelled out in the convention but which are still obeyed by .NET, and which are often enforced by linting tools like StyleCop.

Your mileage may vary on these as every group has its own coding convention, and some platforms which use C# (such as Unity) don't follow these conventions in their public APIs.

Add XmlDoc comments for public classes and members

Like many languages, C# has a documentation standard where if you write comments in a particular form, IDEs will read those comments and show them contextually to consumers of your APIs. For C#, the standard is XmlDoc.

Member identifier names should start with a capital letter

Per the C# Identifier Names convention:

  • Use PascalCase for class names and method names.
  • Use camelCase for method parameters and local variables.
  • Use PascalCase for constant names, both fields and local constants.
  • Private instance fields start with an underscore (_) and the remaining text is camelCased.

This means that append should be Append, etc. for other methods.

Do not abbreviate identifier names

Per the C# naming convention above:

Avoid using abbreviations or acronyms in names, except for widely known and accepted abbreviations.

As commonly interpreted, "Widely known and accepted abbreviations" refers to things like writing Http instead of HyperTextTransferProtocol, where the abbreviation is so widely used as to have completely replaced the term its abbreviating in common usage. While most people would recognize that val is probably abbreviating value, it doesn't meet that bar.

Relatedly: Most C# IDEs will support autocomplete based on initialisms, for example, if you have a property named CountDistinctBuckets, and then type this.CDB and hit tab, Visual Studio and most other editors will correctly autocomplete. With this support, it's common to see identifiers in C# which are dozens of characters long, without any abbreviations.

Fields should never be public

Fields should be private. For everything you would use a public field for, use an auto property instead.

Always write your access controls

While a field that is not marked public nor private will default to private, it is preferred to write your access controls out anyway e.g. private Node<T>? head.

Node<T> should be a nested type within LinkedList<T>

Since Node<T> is intended for use only as part of a LinkedList<T>, I would recommend moving the definition of Node<T> into LinkedList<T> and remove the generic modifier. The fully of the class will then be (namespace).LinkedList<T>.Node, which makes it clear that this is a Node of a linked list and not a node of a B-Tree or something else.

Rewritten

/// <summary>
/// A collection which allows for O(1) insertion and removal of elements at the beginning of the list.
/// </summary>
/// <typeparam name="T">The type to store within the list</typeparam>
public class LinkedList<T> : IEnumerable<T>
{
    /// <summary>
    /// The head element of the list
    /// </summary>
    private Node? _head;

    /// <summary>
    /// Initializes a new LinkedList.
    /// </summary>
    public LinkedList()
    {
        _head = null;
    }

    /// <summary>
    /// Initializes a new LinkedList with the given values.
    /// </summary>
    /// <param name="values">The values to initialize the list with</param>
    public LinkedList(IEnumerable<T> values)
    {
        foreach (var v in values.Reverse())
        {
            Push(v);
        }
    }

    /// <summary>
    /// Inserts a new element at the front of the list.
    /// </summary>
    /// <param name="val">The value to insert</param>
    public void Push(T val)
    {
        Node node = new Node(val, _head);
        _head = node;
    }

    /// <summary>
    /// Attempts to read the value at the start of the list.
    /// </summary>
    /// <param name="result">(Out) the value at the start of the list</param>
    /// <returns>true if a value was read, false otherwise</returns>
    public bool TryPeek([NotNullWhen(true)] out T? result)
    {
        if (_head == null)
        {
            result = default;
            return false;
        }

        result = _head.Value;
        return true;
    }

    /// <summary>
    /// Reads the value at the start of the list.
    /// </summary>
    /// <returns>The value at the start of the list</returns>
    /// <exception cref="InvalidOperationException">If the list is empty</exception>
    public T Peek()
    {
        if (TryPeek(out var value))
        {
            return value;
        }
        else
        {
            throw new InvalidOperationException("Cannot Peek from an empty list");
        }
    }

    /// <summary>
    /// Attempts to read and remove the value at the start of the list
    /// </summary>
    /// <param name="result">The value which was previously at the start of the list, which was removed</param>
    /// <returns>true if a value was read, false otherwise</returns>
    public bool TryPop([NotNullWhen(true)] out T? result)
    {
        if (_head == null)
        {
            result = default;
            return false;
        }

        result = _head.Value;
        _head = _head.Next;
        return true;
    }

    /// <summary>
    /// Reads and removes the value from the start of hte list
    /// </summary>
    /// <returns>The value which was previously at the start of the list, which was removed</returns>
    /// <exception cref="InvalidOperationException"></exception>
    public T Pop()
    {
        if (TryPop(out var value))
        {
            return value;
        }
        else
        {
            throw new InvalidOperationException("Cannot Pop from an empty list");
        }
    }

    /// <inheritdoc/>
    public IEnumerator<T> GetEnumerator()
    {
        var node = _head;
        while (node != null)
        {
            var temp = node.Value;
            node = node.Next;
            yield return temp;
        }
    }

    /// <inheritdoc/>
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    /// <summary>
    /// A single node of the linked list
    /// </summary>
    private class Node
    {
        /// <summary>
        /// The value stored at this position
        /// </summary>
        [NotNull]
        public T Value { get; }

        /// <summary>
        /// The next node, or null if this is the end of the list
        /// </summary>
        public Node? Next { get; }

        /// <summary>
        /// Initializes a new Node.
        /// </summary>
        /// <param name="value">The value to store at this position</param>
        /// <param name="next">The node after this one</param>
        /// <exception cref="ArgumentNullException">If the value to store is null</exception>
        public Node(T value, Node? next)
        {
            Value = value ?? throw new ArgumentNullException(nameof(value));
            Next = next;
        }
    }
}

As a note, this rewrite explicitly rejects the user inserting a node containing null. There is some precedent for collections doing this (HashSet can't contain nulls, and Dictionary rejects null keys), but it's not really a good thing for a linked list to do so. It's possible to avoid this, but TryPop and TryPeek would no longer be able to confidently claim [NotNullWhen(true)] for their output if I did that. I couldn't find a beginner-friendly way of handling this.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ +1 but I think tryPeek and tryPoke are unnecessarily complicated, I would add an isEmpty property to check whether the list is empty or not which can be queried before calling the existing peek/poke methods whilst also being more generally useful. \$\endgroup\$ Commented Jun 26 at 12:15
  • 2
    \$\begingroup\$ @JackAidley - TryXxx is the common convention in C# and easily extends to other collection types designed to be used concurrently. \$\endgroup\$ Commented Jun 26 at 13:10
  • 1
    \$\begingroup\$ @Damien_The_Unbeliever Yet the standard implementation of LinkedList<> does not have TryXxx methods. \$\endgroup\$ Commented Jun 26 at 13:33
  • 2
    \$\begingroup\$ This is a fantastic answer for a fairly new contributor. Covers so many points and is formatted quite nicely. There is an exception to fields should private: non-constant fields should always be private. A constant field may be public. \$\endgroup\$
    – Rick Davin
    Commented Jun 26 at 15:02
5
\$\begingroup\$

This is bog standard and the code looks Just Fine.

I don't see an isEmpty() predicate :-(

bothered that peek() and pop() have to throw errors.

It all depends on the contract your Public API chooses to support. The current API is a good one, with very clear semantics.

Returning a well-known default value or null Would Be Bad, for the reasons you describe.

A common alternative is for the library to define a new unique empty sentinel object, and return that. Since you allocated it, you can be sure the caller did not already possess such an object, so it will compare unique. Throw fatal exception if caller is foolish enough to attempt to append() the sentinel.

(You didn't want to name it push() instead?)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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