Stack Implementation Using Linked List

What is Stack implementation using Linked List?

A stack implemented using a linked list follows the LIFO (Last In First Out) principle. Unlike array implementation, linked list stacks dynamically allocate memory for each element and don't have size limitations (until memory is exhausted).

Core Stack Operations

push(item)
pop()
peek()
isEmpty()
size()

Algorithmic Steps

Stack Basic Operations

Initialize Stack

  1. Create a head pointer initialized to null
  2. Optional: Maintain a size counter initialized to 0

push()

  1. Create a new node with the given data
  2. Set new node's next pointer to current head
  3. Update head to point to the new node
  4. Increment size counter (if maintained)

pop()

  1. Check if stack is empty (head is null)
  2. If empty, return "Stack Underflow"
  3. Store current head node in a temporary variable
  4. Update head to point to the next node
  5. Decrement size counter (if maintained)
  6. Return data from the temporary node

Stack Helper Operations

peek()

  1. Check if stack is empty (head is null)
  2. If empty, return null
  3. Return data from head node without removal

isEmpty()

  1. Return true if head is null
  2. Return false otherwise

size()

  1. If size counter is maintained, return its value
  2. Otherwise, traverse the list and count nodes

Visual Representation

Head
8
(top)
17
42
null
Stack after operations: push(42), push(17), push(8)

Time Complexity

OperationComplexity
push()O(1)
pop()O(1)
peek()O(1)
isEmpty()O(1)
size()O(1) or O(n)

Key Characteristics

  • *Dynamic Size: No fixed capacity (grows as needed)
  • *Memory Efficiency: Uses only needed memory
  • *No Wasted Space: Unlike array implementation
  • *Extra Memory: Requires space for pointers
  • *Flexibility: Can grow until memory exhausted

Linked List vs Array Implementation

FeatureLinked ListArray
Memory UsageExtra for pointersFixed size, may be wasted
Dynamic SizeYesNo (unless resized)
Memory AllocationDynamicStatic (usually)
Access TimeO(1) for topO(1) for all
Implementation ComplexitySlightly more complexSimpler

Stack Implementation using Linked List

// Stack Implementation using Linked List (JavaScript)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Push operation
  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

  // Pop operation
  pop() {
    if (this.isEmpty()) {
      console.log("Stack Underflow");
      return null;
    }
    const value = this.top.value;
    this.top = this.top.next;
    this.size--;
    return value;
  }

  // Peek operation
  peek() {
    if (this.isEmpty()) {
      console.log("Stack is empty");
      return null;
    }
    return this.top.value;
  }

  // Check if stack is empty
  isEmpty() {
    return this.size === 0;
  }

  // Get stack size
  getSize() {
    return this.size;
  }

  // Print stack contents
  print() {
    if (this.isEmpty()) {
      console.log("Stack is empty");
      return;
    }
    let current = this.top;
    console.log("Stack contents (top to bottom):");
    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

// Usage
const stack = new LinkedListStack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log("Top element:", stack.peek()); // 30
console.log("Stack size:", stack.getSize()); // 3
stack.print();
stack.pop();
console.log("After pop, top element:", stack.peek()); // 20

Features: Push, Pop, Peek, isEmpty, Size, and Print operations

Note: Linked list implementation doesn't have fixed size limitation

Explore other implementation

Using Array