Implementation Using Linked List

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

Core Operations

Initialize Stack

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

push()

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

pop()

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

Utility Functions

peek()

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

isEmpty()

Return true if head is null.
Return false otherwise.

size()

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

Efficiency Analysis

Time Complexity

Push/Pop/Peek:O(1)
Search:O(n)

Space Complexity

Overall Space:O(n)
Memory overhead:
(1 pointer per node)

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

Implementation Comparison

Feature	Linked List	Array
Memory Usage	Extra for pointers	Fixed size, may be wasted
Dynamic Size	Yes	No (unless resized)
Memory Allocation	Dynamic	Static (usually)
Access Time	O(1) for top	O(1) for all
Complexity	Slightly higher	Very Simple

algorithm.txt

1234567891011121314151617181920212223242526272829303132333435363738// Stack using Linked List in JavaScript
structure Node
    initialize(value)
        this.value=value
        this.next=null
structure LinkedListStack
    initialize()
        this.top=null
        this.size=0
    push(value)
        newNode ← new Node(value)
        newNode.next=this.top
        this.top=newNode
        this.size++
    pop()
        if this.isEmpty( then)
            console.log("Stack Underflow")
            return
        value ← this.top.value
        this.top=this.top.next
        this.size--
        return value
    peek()
        if this.isEmpty( then)
            return null
        return this.top.value
    isEmpty()
        return this.size = 0
    getSize()
        return this.size
// Usage
stack ← new LinkedListStack()
stack.push(10)
stack.push(20)
stack.push(30)
console.log("Top:",stack.peek())
stack.pop()
console.log("After pop:",stack.peek())

Explore other implementation

Using Array