8.11 Lock-Free Stack Using Linked List (CAS)

8.11.1 Problem Metadata

  • Platform: Interview Prep
  • Problem ID: Stack via Linked List
  • Difficulty: Easy
  • URL: N/A
  • Tags:
  • Techniques: Stack, Linked List, Lock-Free (CAS)

8.11.2 Description

Design a lock-free, thread-safe stack using a singly linked list and a CAS-based AtomicReference head. Support push, pop, top, and empty in constant time. If the stack is empty, pop and top return -1.

Assume the following helper classes are available:

//Given
staic class Node {
    public int val;

    putlic Node next;

    public Node(int v) {
        this.val = v;
    }
}

//Given
static class AtomicReference<T> {
    private T ref;

    public T get() {
        return ref;
    }   

    public set(T newRef) {
        this.ref = newRef;
    }

    public boolean compareAndSet(T expected, E newRef) {
        if(ref == expected) {
            ref = newRef;
            return true;
        } 

        return false;
    }

}

8.11.3 Examples

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 2
stack.pop(); // 2
stack.empty(); // false

8.11.4 Constraints

  • Use a linked list node structure with value and next pointers
  • All operations must run in O(1) time
  • If the stack is empty, pop and top return -1
  • Use a lock-free approach with AtomicReference<T> for thread safety

8.11.5 Solution - Linked List Head as Top

8.11.5.1 Walkthrough

Use the list head as the stack top, stored in an AtomicReference. push and pop update the head with a compare-and-set (CAS) loop so that multiple threads can operate without locks. Peeking reads the current head without modifying it. Empty is a null head check. When the stack is empty, pop and top return -1 by definition.

8.11.5.2 Analysis

  • Time Complexity: O(1) for all operations
  • Space Complexity: O(n) for n stored nodes

8.11.5.3 Implementation Steps

  1. Store a head AtomicReference<Node> for the top of the stack.
  2. push(x): create a new node and CAS it as the new head, retrying if the head changes.
  3. pop(): read head; if null return -1, otherwise CAS head to next and return the old value.
  4. top(): read head; if null return -1, otherwise return head value.
  5. empty(): return whether head is null.

8.11.5.4 Code - Java

class MyStack {
    private final AtomicReference<Node> head = new AtomicReference<>();

    public void push(int val) {
        Node newNode = new Node(val);
        while (true) {
            Node current = head.get();
            newNode.next = current;
            if (head.compareAndSet(current, newNode)) {
                return;
            }
        }
    }

    public int pop() {
        while (true) {
            Node current = head.get();
            if (current == null) {
                return -1;
            }
            Node next = current.next;
            if (head.compareAndSet(current, next)) {
                return current.val;
            }
        }
    }

    public int top() {
        Node current = head.get();
        return current == null ? -1 : current.val;
    }

    public boolean empty() {
        return head.get() == null;
    }

    private static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }
}