Stack using a Linked List

Question

I thought implementing a stack using a linked list was a good option since an array implementation involves reallocation of array size and so on.

I have implemented basic Push, Pop and Print operation: What best practices can I follow?

class StackusingLinkedList
{
    public Node<int> Head;
    int Nodecount = 0;
    public void Push(int data)
    {
        if (Nodecount == 0)
        {
            Head = new Node<int>(data);
            Nodecount++;
            return; ;
        }
        var temp = new Node<int>(data);
        temp.Next = Head;
        Head = temp;
        Nodecount++;
    }
    public void Pop()
    {
        var temp = Head;
        Head = temp.Next;
    }
    public void Print()
    {
        var prtemp = Head;
        StringBuilder sb = new StringBuilder();
        while (true)
        {
            if (prtemp == null)
            {
                break;
            }
            sb.Append("|"+prtemp.Data+"|");
            var temp = prtemp;
            prtemp = temp.Next;
        }
        Console.WriteLine(sb.ToString());
    }
}

class Node<T>
{
    public Node<T> Next { get; set; }

    public T Data { get; set; }

    public Node(T data)
    {
        Data = data;
    }

}

Answer 1

Major Issues

• The class access modifier does not allow public access, so your class is not usable by third party consumers. Make it public.
• Your class should be generic to be usable.
• You should always provide unit tests when providing a class to consumers of your API.
• Pop is ill-defined. It does not return anything. It can throw a NullReferenceException when the stack is empty. It does not decrement the count. It should throw InvalidOperationException when empty.
• A class representing a collection should always implement the correct interfaces. Implement IEnumerable<T> to let consumers iterate the items. Implement IReadOnlyCollection<T> to provide a property Count. Don't be fooled by its name, collections implementing this interface are not stipulated to be immutable. They provide a Count to indicate eager iteration is provided (Interesting Discussion about IReadOnlyCollection).

Review

• The name of a class should tell you what it is, not how it's implemented. Call it LinkedStack (conform naming convention LinkedList).
• Node could be made public, but then its state should be private or internal at best. Given the few operations you provide, it could be made private. Consider making it public if you would provide mehods as Remove(Node<T> node). This would remove a specific node, even if multiple nodes hold the same value as the specified node.
• Push has a redundant creation of a node. Create the node before the first if statement.
• Print has no purpose in this class. It should be an extension method declared elsewhere.
• Node should be a nested class for better encapsulation.
• A property IsEmpty, as suggested in another answer, is syntactic sugar that improves readability.

---

Refactored

In this solution the Node remains private. Some API's allow it to be public.

public class LinkedStack<T> : IReadOnlyCollection<T>, IEnumerable<T>
{
    private class Node
    {
        internal Node next;
        internal T Value { get; }

        public Node(T value) => Value = value;
    }

    private Node head;

    public void Push(T item)
    {
        var node = new Node(item);
        if (IsEmpty)
        {
            head = node;
        }
        else
        {
            node.next = head;
            head = node;
        }
        Count++;
    }

    public T Pop()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException();
        }
        var value = head.Value;
        head = head.next;
        Count--;
        return value;
    }

    public int Count { get; private set; }
    public bool IsEmpty => Count == 0;

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

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

Unit Tests

[TestClass]
public class LinkedStackTests
{
    [TestMethod]
    public void LinkedStackTest()
    {
        var stack = new LinkedStack<int>();

        stack.Push(0);
        stack.Push(0);
        stack.Push(1);

        Assert.AreEqual(3, stack.Count);

        Assert.AreEqual(1, stack.Pop());
        Assert.AreEqual(0, stack.Pop());
        Assert.AreEqual(0, stack.Pop());

        Assert.AreEqual(0, stack.Count);
    }
}

Answer 2

Spacing

A small thing, but a few more line-breaks between methods and control-flow constructs would be appreciated. It helps to break up the different members and parts of methods.

You should also pad your operators with spaces: "|" + prtemp.Data + "|".

Naming

StackusingLinkedList is a slightly odd name... there should probably be a capital U on Using.

You've used ProperCamelCase for all exposed members and lowerCamelCase for parameters, which is all good. It doesn't really matter how you name private members and variable, but they should be consistent and CamelCase of somesort (NodeCount rather than Nodecount). This is just convention, but if you follow Microsofts Conventions, your code will be easier to understand (because everyone follows them).

Encapsulation and Mutability

Node<T> class

The Node<T> class is (presumably) completely specific to the StackUsingLinkedList. It would be better to enclose it as a private class within StackUsingLinkedList, as it is nothing but an implementation detail.

Inside the Node<T> class, you have the Data property, which is publically writeable. Very simply, it is usually best to have the most restrictive accessibility you can get away with. Data does need to be publically readable, but does it need to be publically writable? No! Does it even need to be privately writeable? No! This property can be readonly.

Furthermore, the only time you modify Next is directly after creating a Node<T>. This isn't very nice, and currently your constructor leaves Head to a default value, which is never ideal. It is obvious that you want to support a 'bottom' Node, which has no Next as well as a node with both Data and Next, so why not provide 2 constructors? This allows you to make Next readonly as well, making the whole class immutable:

// within StackUsingLinkedList
private class Node<T>
{
    public Node<T> Next { get; } // no 'set;' means it is readonly (can only be modified in a constructor)
    public T Data { get; }

    public Node(T data)
    {
        Data = data;
        Next = null; // explicitly mark this as null
    }

    public Node(T Data, Node<T> next)
    {
        Data = data;
        Next = next;
    }
}

The benefits of making properties (and whole classes) immutable where appropriate is that they are very predictable (values can never change) and difficult to misuse. It is all part of expressing your intent to the compiler. By saying "I don't want to change this", it will prevent you from changing it. This sounds obvious and simple, but expressing your intent in code is the most fundamental concept in writing usable and maintainable systems.

Exposed API

The exposed classes and members should ideally all have inline-documentation (///) so that it everyone knows what the method is meant to do. For example:

/// <summary>
/// Prints the stack to the console
/// </summary>
public void Print()

Other

If you make Node<T> private, then the compiler will error on public Node<int> Head. This is great! We have expressed our intent that Node<T> is only the concern of StackUsingLinkedList, and it is stopping us from exposing this implementation detail to the world. Head should indeed be private. If someone trying to use your class was to modify Head, they could leave you in invalid state, and shoot themselves in the foot. As a general rule, unless you are writing some delicate code using structs, there is no harm in making all your fields into properties, but this isn't essential. It is good to explicitly mark private members of private (though thankfully this is the default):

private Node<int> Head { get; set; }
private int NodeCount { get; set; }

Generics

You have produced a generic Node<T> class, but you haven't made StackUsingLinkedList generic! If this is intended to be a reusable type, then it should be generic if possible. You haven't shown us how you intend to use this type, but there is nothing that stops it being generic, so you should strongly consider making it generic.

(Note that using inner classes with generic parameters of the same name is weird, but here they are the same parameter, so if you put Node<T> inside StackUsingLinkedList<T> you can just remove the parameter on Node<T> (make it Node).

Methods

Push(...)

This should take a generic parameter (if the type is made generic) and add it accordingly. Returning from within an if is usually harder to read than simply using an else.

The readability could be improved by defining a variable or property called 'isEmpty', making it clear what the if is switching on. Such a property could be private, but it might also be useful to make it public, since "are you empty?" this is a reasonable question to ask of a Stack.

public bool IsEmpty => Nodecount == 0;

public void Push(T data)
{
    if (IsEmpty)
    {
        Head = new Node<T>(data);
        Nodecount++;
    }
    else
    {
        Head = new Node(data, Head);cleaner
        NodeCount++;
    }
}

Pop()

Pop methods usually return the value that has been popped. Presently you record the current Head in temp unnecessarily, and then look up temp instead of Head, which is perhaps less clear. Somehting like this following may be better and more useful.

/// <summary> Pops a value from the top of the stack, and returns this value </summary>
public T Pop()
{
    T temp = Head;
    Head = Head.Next;
    NodeCount--;

    return temp.Data;
}

There is also a NodeCount-- in there. This was missing in your original code (thanks to JSextonn for pointing that out)

Print()

This is a slightly odd method. A Stack is usually considered a general-purpose data-type, but this method performs some very specific behaviour. At the very least.

What does prtemp mean? Temporary Pointer??? I don't know, it could do with a better name. I usually call these sort of things 'current', because they are thing we are currently looking at, but I'm sure opinions will vary on this.

You have an if...break statement at the start of your while loop: I would just make this condition part of the while.

while (prtemp != null)
{
    // ...
}

Since you arn't returning the string you build - only printing it - you could just print it directly.

Putting it all together

I can't say I'm overly fond of how your linked list actually works, but putting all of these simple changes together gives this (with extra comments indicating changes):

/// <summary>
/// Represents a stack of items implemented internally as a linked list
/// </summary>
/// <typeparam name="T">The type of items sorted in the stack</typeparam>
public class StackUsingLinkedList<T>
{
    // private inner class
    private class Node
    {
        public Node Next { get; }
        public T Data { get; }

        public Node(T data)
        {
            Data = data;
            Next = null;
        }

        public Node(T data, Node next)
        {
            Data = data;
            Next = next;
        }
    }

    private Node Head; // private
    private int NodeCount = 0; // choice of CamelCase

    /// <summary>
    /// True is the stack is empty, otherwise False
    /// </summary>
    public bool IsEmpty => NodeCount == 0;

    /// <summary>
    /// Pushes the data to the top of the stack
    /// </summary>
    /// <param name="data">The value to pushed onto the stack</param>
    public void Push(T data)
    {
        if (IsEmpty) // easier to read and reason about
        {
            Head = new Node(data);
            NodeCount++;
        }
        else // else clause makes control-flow clearer
        {
            Head = new Node(data, Head); // no need for a tempory value, much cleaner
            NodeCount++;
        }
    }

    /// <summary>
    /// Pops the top value from the stack, and returns the popped value
    /// </summary>
    public T Pop()
    {
        var temp = Head;
        Head = Head.Next;
        NodeCount--;

        return temp.Data; // return the value popped
    }

    /// <summary>
    /// Prints the stack to the console
    /// </summary>
    public void Print()
    {
        var current = Head;
        StringBuilder sb = new StringBuilder();

        while (current != null)
        {
            sb.Append("|" + current.Data.ToString() + "|"); // operator padding
            current = current.Next;
        }

        Console.WriteLine(sb.ToString());
    }
}

A short comment about Array performance

You talk about wanting to use a linked list rather than an array for performance reasons. The reality is that a normal array/vector based stack will probably be more efficient in .NET! If you consider List<T>, it works by growing an array. The cost of each addition varies depending on whether it has to grow the array or not, and on average the cost is constant (i.e. not a function of the size of the array), which is the same complexity as handling a linked list. However, the linked list requires an allocation for every element, whilst a well-managed array based list won't, and in systems with high-level 'hands-off' memory management (like .NET) this can easily be more efficient in practise.