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).

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 variabl.
    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.

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

Done With the Learning

Mark Stack using Linked List as done and view it on your dashboard

Explore other implementation

Using Array