Sunday, February 8, 2015

Implementation of STACK using Linked List in C language

9:34 PMSunday, February 8, 2015
Implementation of STACK using Linked List

             To implement the STACK using Linked List, the Linked List itself is created in different manner. In this case instead of ROOT in normal Linked List, an external pointer TOP is used to point all the time to the just added node.
      Initially when the STACK is empty TOP points to a NULL address.

When the PUSH operation is to be done, a NEW node is created and TOP is made point to it. Suppose for the first time one PUSH operation is done. The linked list is shown below:

When again another ITEM is PUSHed, a NEW node is created and the address of the node pointer by TOP, is copied in the LINK field of NEW node the TOP is made point to the NEW node. The Linked List is as below:
When again another item is to be PUSHed it is done similarly. After the PUSH of one more ITEM the Linked List is as shown below:
So, the Linked List created as STACK can be graphically shown as below:
While deletion, POPping is to be done from the STACK, TOP is checked. If it is NULL then the STACK is empty and ‘underflow’ occurs otherwise the ITEM of the node pointed by TOP can be copied in a variable and TOP is updated by link of TOP. Then ITEM is returned.
                      In the above-created STACK, if the POP operation is done once, the Linked List can be shown as below:

Protected by Copyscape Online Copyright Protection Software


Post a Comment

Toggle Footer