Stack Implementation Using Linked List
Implementing stack operations using a linked list
Implementation
Push Operation
- Create a new node with the given
data
. - Set the
next
pointer of the new node to the currenttop
. - Update
top
to point to the new node.- Increment
len
by 1.
- Increment
Pop Operation
- Check if
top
isNULL
(stack is empty). - If
true
, print "Stack is empty" and exit.
Otherwise:
-
Store the current
top
node in a temporary variable (del
). -
Update
top
to point totop->next
(the next node). -
Free the memory of the node stored in
del
. -
Decrement
len
by 1.
Peek Operation
-
Check if the stack is empty (
top == NULL
). -
If
true
, print "Stack is empty" and return-1
. -
Otherwise, return the
data
value of thetop
node.
IsEmpty Operation
-
Check if
top == NULL
. -
Return
true
if the stack is empty, otherwisefalse
.
Size Operation
- Return the value of
len
.
Coding Implementation
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = NULL;
}
};
class Stack {
private:
Node* top;
int len;
public:
Stack() {
top = NULL;
len = 0;
}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
len++;
}
void pop() {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return;
}
Node* temp = top;
top = top->next;
delete temp;
len--;
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return -1;
}
return top->data;
}
bool isEmpty() {
return top == NULL;
}
int size() {
return len;
}
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.peek() << endl;
cout << s.size() << endl;
s.pop();
cout << s.peek() << endl;
cout << s.size() << endl;
return 0;
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
self.length = 0
def push(self, value):
new_node = Node(value)
new_node.next = self.top
self.top = new_node
self.length += 1
def pop(self):
if self.is_empty():
print("Stack is empty")
return
self.top = self.top.next
self.length -= 1
def peek(self):
if self.is_empty():
print("Stack is empty")
return -1
return self.top.data
def is_empty(self):
return self.top is None
def size(self):
return self.length
# Example Usage
s = Stack()
s.push(5)
s.push(10)
s.push(15)
print(s.peek())
print(s.size())
s.pop()
print(s.peek())
print(s.size())
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Stack {
constructor() {
this.top = null;
this.length = 0;
}
push(data) {
const newNode = new Node(data);
newNode.next = this.top;
this.top = newNode;
this.length++;
}
pop() {
if (this.isEmpty()) {
console.log("Stack is empty");
return;
}
this.top = this.top.next;
this.length--;
}
peek() {
if (this.isEmpty()) {
console.log("Stack is empty");
return -1;
}
return this.top.data;
}
isEmpty() {
return this.top === null;
}
size() {
return this.length;
}
}
// Example Usage
const stack = new Stack();
stack.push(100);
stack.push(200);
stack.push(300);
console.log(stack.peek());
console.log(stack.size());
stack.pop();
console.log(stack.peek());
console.log(stack.size());
Comparison of Stack Implementation Using Array and Linked List
Feature | Array | Linked List |
---|---|---|
Memory Allocation | Requires a contiguous block of memory. | Uses non-contiguous memory; nodes allocated dynamically. |
Size | Fixed size (needs resizing for dynamic growth). | Dynamic size; no resizing needed. |
Memory Efficiency | Can waste space if resized or over-allocated. | Allocates memory exactly as needed. |
Push Operation (Insert) | O(1) , unless resizing is needed. | O(1) , always efficient. |
Pop Operation (Delete) | O(1) , straightforward. | O(1) , straightforward. |
How is this guide?