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.
