Implementation of stack using linked list

 Linked Lists in Stack Implementation

• Linked lists offer a dynamic memory allocation alternative to arrays.
• Despite different data structures, time complexities for stack operations remain consistent.
• Nodes are non-contiguously maintained in memory, each with a pointer to its successor node.
• Stack overflow occurs when insufficient memory heap space is available for node creation.
• Singly linked lists align standard linked list operations with stack operations, adhering to the Last In, First Out (LIFO) principle.
• Top variable guides operations like Pop, Push, Peek, and Display.
• Unlike arrays, linked lists offer flexibility, eliminating risk of overflow.

 

 Stack Implementation vs. Array vs. Linked List

• Array-based stacks work for a fixed number of data values, making them unsuitable for unknown data sizes.
•  Linked list stacks can work for unlimited data values, eliminating the need to fix the initial size.
• Linked list stacks insert new elements as 'top' elements, pointing to the 'top' node.
• To remove an element, move 'top' to its previous node in the list.
• The first element's next field must always be NULL.

Operations performed on Stack

Following operations can be performed on a stack:

• push(): It inserts an element to the top of the stack. It takes O(1) time, as each node is inserted at the head/top of the linked list.
• pop(): It removes an element from the top of the stack. It takes O(1) time, as the top always points to the newly inserted node.
• peek(): It returns the top element of the stack.
• size(): It returns the size of the stack, i.e., the total number of items in a stack.
• isEmpty(): Returns a boolean value. It returns true if the stack is empty. Else, it returns false.

 Before performing all the above operations, lets first define node structure

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define a Node pointer 'top' and set it to NULL.
• Step 4 - Implement the main method by displaying Menu with list of operations and make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'.