Problem

Design and implement a stack using a linked list. The stack should support the following operations:

  • push(x): Push element x onto the stack.
  • pop(): Removes the element on top of the stack and returns it.
  • top(): Get the top element.
  • isEmpty(): Return whether the stack is empty.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
Operations: ["push(1)", "push(2)", "top()", "pop()", "isEmpty()"]
Output: 
[null, null, 2, 2, false]
Explanation: 
- push(1) adds 1 to the stack.
- push(2) adds 2 to the stack.
- top() returns the current top element, which is 2.
- pop() removes and returns the current top element, which is 2.
- isEmpty() returns false as the stack is not empty.

Solution

Method 1 - Using Linked list

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. By implementing it using a linked list, we can efficiently manage the stack operations as each node points to the next node, making insertions and deletions at the top of the stack constant time operations.

Node Structure

  • Each node in the linked list will contain a value and a reference to the next node.

    • Initialize the stack’s top reference to null.

Key Operations

Initialization

Define a variable last that points to the last node of the linked list. If the stack is empty, it points to null.

Push Operation
  • A new node (newNode) is created for the given data.
  • The next pointer of newNode is set to the current top.
  • The top is then updated to point to newNode, making it the new top of the stack.
Pop Operation
  • If top is null, an exception is thrown because the stack is empty.
  • The value from the top node is retrieved.
  • The top is updated to point to the next node.
  • The retrieved value is returned.
Other operations
  1. Top Operation:
    • If top is null, an exception is thrown because the stack is empty.
    • Otherwise, the value of the top node is returned.
  2. isEmpty Operation:
    • Check if top is null to determine if the stack is empty.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public class Solution {
    private ListNode top;

    private static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public Solution() {
        top = null;
    }

    // Push element x onto stack
    public void push(int x) {
        ListNode newNode = new ListNode(x);
        newNode.next = top;
        top = newNode;
    }

    // Removes the element on top of the stack and returns it
    public int pop() {
        if (top == null) {
            throw new IllegalStateException("Stack underflow");
        }
        int value = top.value;
        top = top.next;
        return value;
    }

    // Get the top element
    public int top() {
        if (top == null) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.value;
    }

    // Return whether the stack is empty
    public boolean isEmpty() {
        return top == null;
    }

    public static void main(String[] args) {
        Solution stack = new Solution();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());     // Outputs: 2
        System.out.println(stack.pop());     // Outputs: 2
        System.out.println(stack.isEmpty()); // Outputs: false
        stack.push(5);
        System.out.println(stack.pop());     // Outputs: 5
        System.out.println(stack.isEmpty()); // Outputs: true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class ListNode:
    def __init__(self, value: int):
        self.value = value
        self.next = None

class Solution:
    def __init__(self) -> None:
        self.top: 'ListNode' = None

    def push(self, x: int) -> None:
        new_node = ListNode(x)
        new_node.next = self.top
        self.top = new_node

    def pop(self) -> int:
        if self.top is None:
            raise Exception("Stack underflow")
        value = self.top.value
        self.top = self.top.next
        return value

    def top(self) -> int:
        if self.top is None:
            raise Exception("Stack is empty")
        return self.top.value

    def isEmpty(self) -> bool:
        return self.top is None

# Example usage
stack = Solution()
stack.push(1)
stack.push(2)
print(stack.top())     # Outputs: 2
print(stack.pop())     # Outputs: 2
print(stack.isEmpty()) # Outputs: False
stack.push(5)
print(stack.pop())     # Outputs: 5
print(stack.isEmpty()) # Outputs: True

Complexity

  • ⏰ Time complexity: O(1) for push, pop, top, and isEmpty operations, as insertions and deletions at the head of the linked list are constant time.
  • 🧺 Space complexity: O(n), where n is the number of elements in the stack, due to storing elements in the linked list nodes.

Resizing array vs linked list

Linked list implementation Resizing array implementation
Every operation takes constant time in worst case Every operation takes constant amortized time
Extra space and time as we have to deal with links Less wasted space