Stack Using Linked List
A stack can also be implemented using a linked list, giving dynamic size without overflow. The top of the stack corresponds to the head of the linked list. Insertions and deletions happen at the head for O(1) time.
Linked list-based stack implementation
public class LinkedListStack<T> {
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
private Node<T> top;
private int size;
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
T data = top.data;
top = top.next;
size--;
return data;
}
public T peek() {
if (isEmpty()) throw new RuntimeException("Stack empty");
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
}
Two Minute Drill
- Linked list stack uses nodes; top is head of list.
- push: O(1), pop: O(1), peek: O(1).
- Dynamic size, no overflow (except memory limit).
- Each element consumes extra memory for the next pointer.
Need more clarification?
Drop us an email at career@quipoinfotech.com