Stacks Using Linked Lists

A stack can be created using a linked list to allow for storing of stack elements as long as sufficient memory is available to create a new node. This circumvents the limits set by the array structure on storing elements.

Creating the stack

Before implementing the operations

1. Include all header files and declare the main function.
2. Define a Node structure with two members data and next.
3. Define a Node pointer top and set it to NULL.

struct Node
{
   int data;
   struct Node *next;
} *top = NULL;

Pushing to the stack

Steps

1. Create a new Node with given value.
2. First check if the stack is empty by checking the underflow condition.
3. If it is Empty, then set newNode → next = NULL.
4. If it is Not Empty, then set newNode → next = top.
5. Finally, set the top pointer to the new Node (top = newNode).

void push(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = value;
   if(top == NULL)
      newNode->next = NULL;
   else
      newNode->next = top;
   top = newNode;
   printf("\nInsertion is Successful\n");
}

Popping from the stack

Steps

1. Check whether stack is Empty (top == NULL).
2. If it is Empty, then display an error message and terminate the function.
3. If it is Not Empty, then define a Node pointer temp and set it to top.
4. Then set top = top → next.
5. Finally, delete temp using free(temp).

void pop()
{
   if(top == NULL)
      printf("\nUnderflow. Stack is empty\n");
   else{
      struct Node *temp = top;
      printf("\nDeleted element is: %d", temp->data);
      top = temp->next;
      free(temp);
   }
}

Visualizations

• Data Structures: Linked List implementation of stacks | mycodeschool Good explanation from mycodeschool about the implementation using linked list.
• Data Structures: Stacks and Queues | HackerRank Popular book writer Gayle Laakmann McDowell explains about stacks and queues in this HackerRank video.
• Stacks and Queues | 0612 TV w/ NERDfirst <>