Implementing LinkedStack

Here is the Stack interface:

public interface Stack<T> {
  void push(T item);  // throws IllegalArgumentException if item is null
  void pop();         // throws NoSuchElementException if the stack is empty
  T top();            // throws NoSuchElementException if the stack is empty
  boolean isEmpty();
}

LinkedStack<T> implements the Stack<T> interface with a singly linked list of nodes. The head of the list is the top of the stack:

import java.util.NoSuchElementException;

public class LinkedStack<T> implements Stack<T> {

  private Node<T> head;  // the first node

  private static class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
      this.value = value;
    }
  }

  public LinkedStack() {
    head = null;
  }

  // push, pop, top, and isEmpty go here
}

Solution

public boolean isEmpty() {
  return head == null;
}

public T top() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return head.value;
}

public void pop() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  head = head.next;
}

Solution

public void push(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> newNode = new Node<>(item);
  newNode.next = head;
  head = newNode;
}

Solution

All four are $O (1)$ in the worst case. isEmpty and top read head and at most one node. pop and push change head and one next reference, with no traversal.

Solution

push needs a tail reference, so a new node can be linked after the tail without a traversal. pop needs a doubly linked list, so the tail can move to the previous node without a traversal.

Solution

Both use $O (n)$ space. The array usually has more slots than items, and it keeps its largest capacity after the stack gets smaller. LinkedStack allocates exactly one node per item, but each node also stores a next reference.