Please navigate to the bottom of the page for Table of Contents

Sunday, May 22, 2011

Implement a basic Stack using linked List

Implementing a stack using linked list is the a very basic application of the linked list data structure. It tests your ability to visualize the usage of a complex data structure (such as a Stack) in terms of a more primitive data structure such as a linked list. Stack is a LIFO (Last In First Out) structure. That means that the last element in is the first element out. In programming terms, that means that you insert new elements at the top of the list and you remove elements from the top too. Simple, right?

First, let's define our linked list data structure. This is the same as in our previous examples:

typedef struct linked_list
{
int data;
struct linked_list *next;
} Node;


For us to be able to test our code, we need to define a way to display our stack. There are multiple ways to display the stack – you can use a loop (do-while) or you can use recursion. Guess what? We have already covered recursion. So let's try recursion to display the stack.


// recursively display the contents 
// of the stack
void DisplayStack(Node* currentNode)
{
// recursive termination condition
if (currentNode == NULL)
{
return;
}

// the node is not null
// display the data
printf(" -> %d", currentNode->data);
// recursively call the display to
// display the next element in the stack
DisplayStack(currentNode->next);
}


Now that we have figured out the display, let's check out the code for pushing an element onto the stack.


// push item on the stack
// this is same as adding a node
// at the top of the list
void Push(int dataToAdd)
{
// assumption: head is already defined elsewhere in the program
// 1. create the new node
Node *temp = new Node;
temp->data = dataToAdd;

// 2. insert it at the first position
temp->next = head;

// 3. update the head to point to this new node
head = temp;
}
 

As it is evident from the function above, adding new elements on the stack is fairly intuitive and simple. Now let's tackle the last part of the Stack structure: popping an element of the stack. It is equally simple. You remove the first (head) element from the linked list. The only caveat here is that you have to take care of empty list.

 

// pop an element from the stack
// this is same as removing the first element
// from the list
Node* Pop()
{
// check for empty list
if (head == NULL)
{
printf("Stack is empty\n");
return NULL;
}

// get the top node
Node *firstNode = head;

// move the head
head = head->next;

// disconnect the node
// from the list
firstNode->next = NULL;

// return the top node
return firstNode;
}


That's it. You now know how you can implement a stack using linked list. We will discuss another application of stacks (using linked lists) in a future post.

21 comments:

  1. cooooollllll maaaahnnnnn
    ;*

    ReplyDelete
  2. damn interview!!!!!!!!
    wot d hell s wrong wt u...:/:/

    ReplyDelete
  3. Awesome..You have clearly explained.it is very simple to understand.it's very useful for me to know about new things..Keep posting.Thank You...
    aws online training
    aws training in hyderabad
    amazon web services(AWS) online training
    amazon web services(AWS) training online


    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. The WB 10th results 2019 are much awaited for release. Students are eager to know their performance in the exam. Students are hereby informed that the results of madhyamik result 2019 was released online.

    karresults.nic.in SSLC result 2019 will be declared in the month of May 2019. Result will be declared on the official website. Check the Karnataka SSLC Result 2019 Date here.

    Madhya Pradesh Board of Secondary Education (MPBSE) declares the results of the mp board 10th result 2019 board examinations in the MP board result website.

    Waiting for the declaration of bihar board 10th result 2019 Some good news is coming your way soon. As per the latest buzz, the Bihar School Examination Board (BSEB) is planning to declare the BSEB Matric Result 2019 and Bihar Board Intermediate Result 2019 soon.

    ReplyDelete
  6. I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!
    it course

    ReplyDelete
  7. This was nice and amazing and the given contents were very useful and the precision has given here is good.

    Apache Spark Training in Pune
    Spark Training Institute in Pune

    ReplyDelete
  8. Cool stuff you have and you keep overhaul every one of us
    data science course in delhi

    ReplyDelete
  9. Really Nice Information It's Very Helpful All courses Checkout Here.
    data scientist courses aurangabad

    ReplyDelete
  10. It’s my fortune to go to at this blog and realize out my required stuff that is also in the quality.
    UI UX design firm

    ReplyDelete
  11. I agree with what you are introducing. It is important to form a consensus, and I think it is good enough to influence my next post. In the next article, I will try to post related to Cloud Telephony Software

    ReplyDelete