PPractick

The problem

A text editor's undo history can grow without limit, so a fixed-size array stack isn't suitable. A linked-list stack grows one node at a time and never needs resizing. All activity happens at the head of the list: push creates a node that points to the old head, and pop removes the head. Both are O(1) with no capacity limit. The details interviewers check are handling an empty stack (return −1) and freeing nodes so memory isn't leaked.

Example: push(2), push(3), pop() → 3, push(4), pop() → 4.

Function signature

class LinkedStack {
public:
    void push(int x);
    int pop();            // -1 if empty
    int top() const;      // -1 if empty
    bool isEmpty() const;
    int size() const;
};

Test cases

Operations	Output	Explanation
push(2) push(3) pop() push(4) pop()	3 4
pop() on an empty stack	-1
push(1) push(2) push(3) size()	3	No capacity limit
push(5) top()	5	top doesn't remove
push(7) pop() isEmpty()	7 true

(Confirm: O(1) per operation; −1 signals "empty"; all nodes are freed when the stack is destroyed.)

How interviewers phrase it

• "Implement a stack using a linked list, with push, pop and peek" (GeeksforGeeks).

Clarifying questions to ask

1. What should pop or top return on an empty stack?
2. Is there a capacity limit? (No: the list grows as needed.)
3. Should size() be O(1)? (Keep a counter.)

Follow-ups to expect

1. "Why push and pop at the head, not the tail?"
2. "Array stack or linked stack?"
3. "How do you avoid leaks?"
4. "Is size() O(1)?"
5. "Complexity?"

Related questions

• Introduction to Singly LinkedList Easy
• Insertion at the head of Linked List Easy
• Deletion of the head of LL Easy
• Find the length of the Linked List Easy
• Introduction to Doubly LL Easy
• Insert node before head in Doubly Linked List Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in