How to build a stack (Linked List implementation)

We already saw how a Stack can be implemented based on an stack-array, now let's take a look at how we can implement the Stack using a linked list.

We are going to implement the same basic operations:

• Push - adds an item to the top of the collection
• Pop - removes the most recently added item

 

 

It will be the same approach we took when we did in the linked list. We need a nested Node class:

    private sealed class Node
    {
        public Node Next;
        public T Value;
    }

The Push method:

    /// <summary>
    /// Add item on the top of the stack
    /// </summary>
    public void Push(T value)
    {
        Node previousHead = _head;
        _head = new Node
        {
            Value = value,
            Next = previousHead
        };
    }

The Pop method:

    /// <summary>
    /// Return a value from the top of the stack
    /// </summary>
    public T Pop()
    {
        T result = _head.Value;
        _head = _head.Next;
        return result;
    }

Full implementation:

    public class StackLinkedList<T>
    {
        private Node _head;

        public T Pop()
        {
            T result = _head.Value;
            _head = _head.Next;
            return result;
        }

        public void Push(T value)
        {
            Node previousHead = _head;
            _head = new Node
            {
                Value = value,
                Next = previousHead
            };
        }

        private sealed class Node
        {
            public Node Next;
            public T Value;
        }
    }

Note: The above code is not production ready, it does not check all corner cases such as the case with no elements in the stack. The main goal is to show how a stack can be implemented and what is under the hood.