Skip to content

Instantly share code, notes, and snippets.

@aaronjwood
Last active February 12, 2017 06:54
Show Gist options
  • Save aaronjwood/d2058e3c48de9eb35b9dcb55bca4a462 to your computer and use it in GitHub Desktop.
Save aaronjwood/d2058e3c48de9eb35b9dcb55bca4a462 to your computer and use it in GitHub Desktop.
Stack using a linked list
public class Stack<E> {
private class Node<V> {
private V data;
private Node<V> next;
Node(V data) {
this.data = data;
}
}
private Node<E> top;
// Time: O(1)
// Space: O(1)
public E push(E item) {
Node<E> node = new Node<>(item);
node.next = top;
top = node;
return item;
}
// Time: O(1)
// Space: O(1)
public E pop() {
if (top != null) {
Node<E> popped = top;
top = top.next;
return popped.data;
}
return null;
}
// Time: O(1)
// Space: O(1)
public boolean isEmpty() {
return top == null;
}
// Time: O(1)
// Space: O(1)
public E peek() {
return top != null ? top.data : null;
}
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
for (int i = 0; i < 10; i++) {
stack.push("Item " + i);
}
System.out.println("Empty stack: " + stack.isEmpty());
System.out.println("Peek: " + stack.peek());
for (int i = 0; i < 10; i++) {
System.out.println(stack.pop());
}
System.out.println("Empty stack: " + stack.isEmpty());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment