Linked lists and Stack

This is the place where all the pointers, objects and structures come together. A pointer can be used to point towards a memory location. That memory location can hold a pointer, a variable, a structure an array of structure and so on. Once we have pointers that start pointing towards structures, the C++ starts to become both interesting and complicated. Again, if you do not forget how the pointers work, you will have no problem in understanding the concept of linked lists.

We start off by defining a very basic structure called "node" which holds the data that we want to store and a pointer that helps in pointing towards other nodes. This structure can be defined as this:

struct node

{

char data;

node* next;

};

Now, we define our interface for the stack class that we are going to create, like this:

class stack

{

private:

node* head;

public:

stack();

~stack();

void push(char c);

char pop();

};

if you remember the stack implementation through arrays, you will see that the class looks almost the same, with slight differences. The real differences come when you start to implement the various functions. In order to understand how these functions work, attending the classes should do you good. The code that lets you make a stack is as following:

stack::stack()

{

head = NULL;

}

stack::~stack()

{

}

void stack::push(char c)

{

if(head == NULL)

{

head = new node;

head->data = c;

head->next = NULL;

}

else

{

node* temp = new node;

temp->data = c;

temp->next = head;

head = temp;

temp = NULL;

}

}

char stack::pop()

{

char c = '\0';

if(head == NULL)

{

cout<<"\nStack Empty";

return c;

}

else

{

node* temp = head;

head = head->next;

c = temp->data;

delete temp;

temp = NULL;

}

return c;

}

I have made and performed this code myself, so there does not seem to be any problem. You can now try the code yourself and see how the stack works by using nodes. Once you learn this, going through queues and trees is going to be a lot of fun.