[go: up one dir, main page]
Scribd
Upload
6 views4 pages

Adding A Node To The Stack (Push Operation)

Data structure

Uploaded by

504 ,DALVI RUDRA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views4 pages

Adding A Node To The Stack (Push Operation)

Data structure

Uploaded by

504 ,DALVI RUDRA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

STACK USING LINKED LIST

Linked list implementation of stack


Instead of using array, we can also use linked list to implement stack. Linked list allocates
the memory dynamically. However, time complexity in both the scenario is same for all the
operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack is
said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way
in which, each operation is performed in linked list implementation of stack.

Adding a node to the stack (Push operation)


Adding a node to the stack is referred to as push operation. Pushing an element to a
stack in linked list implementation is different from that of an array implementation. In
order to push an element onto the stack, the following steps are involved.

Create a node first and allocate memory to it.


If the list is empty then the item is to be pushed as the start node of the list. This
includes assigning value to the data part of the node and assign null to the address
part of the node.
If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign
the address of the starting element to the address field of the new node and make the
new node, the starting node of the list.
Time Complexity : o(1)
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node
from the linked list implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need to follow the
following steps :

Check for the underflow condition: The underflow condition occurs when we try to
pop from an already empty stack. The stack will be empty if the head pointer of the list
points to null.
Adjust the head pointer accordingly: In stack, the elements are popped only from one
end, therefore, the value stored in the head pointer must be deleted and the node
must be freed. The next node of the head node now becomes the head node
Time Complexity : o(n)
Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the
linked list organized in the form of stack. For this purpose, we need to
follow the following steps.Copy the head pointer into a temporary
pointer.Move the temporary pointer through all the nodes of the list and
print the value field attached to every node.

Time Complexity : o(n)

isEmpty() Function
The isEmpty function checks whether the stack is empty or not. To
implement this function with a singly linked list, we just check if the head is
NULL or not. If the head is NULL, it means that the list is empty, so we will
return true. If the head is not NULL, it means that the list is not empty, so
we will return false.

Program:
OUTPUT: -
Conclusion:-

Stack is a linear data structure that follows the Last in, First Out Principle
(LIFO).
Stack can be represented using nodes of a linked list.
Stack supports operations such as push, pop, size, peek, and is Empty.
Elements can be pushed or popped from one end only.
Push and Pop operations take O(1) time.

You might also like