Linked list stack implementation

Question

I have used the following code for a stack implementation. The top keeps track of the topmost node of the stack. Now since top is a data member of the node function, each node created will have a top member, which ideally we wouldn't want.

1. Is this good approach to coding?
2. Will making top as static make it a better coding practice?
3. Should I have a global declaration of top?

#include<iostream>
using namespace std;
class node
{
 int data;
 node *top;
 node *link;
 public:
 node()
 {
 top=NULL;
 link=NULL;
 }
 void push(int x)
 {
 node *n=new node;
 n->data=x;
 n->link=top;
 top=n;
 cout<<"Pushed "<<n->data<<endl;
 }
 void pop()
 {
 node *n=new node;
 n=top;
 top=top->link;
 n->link=NULL;
 cout<<"Popped "<<n->data<<endl;
 delete n;
 }
 void print()
 {
 node *n=new node;
 n=top;
 while(n!=NULL)
 {
 cout<<n->data<<endl;
 n=n->link;
 }
 delete n;
 }
};
int main()
{
 node stack;
 stack.push(5);
 stack.push(7);
 stack.push(9);
 stack.pop();
 stack.print();
}

Any other suggestions welcome. I have also seen codes where there are two classes, where the second one has the top member. What about this?

• Shahbaz: making top global or static means you can use only one stack in your program! You might want to distinguish between the node and list classes.
• Quik Tester: Shahbaz, yes I get that. Thanks. :). So you suggest creating two classes where from the list I create an object of node to keep track?

Answer 1

1. In the pop and the print function, the new node seems unnecessary, since the next line modifies the pointer to point to the top. It could be simply

   node *n = top;
   

2. The delete n; also looks superfluous in the print since n will always be NULL there.

3. If I'm right making top as static or global would result that you can't have more than one stack in an application. Linked lists usually have two classes: one is a Node which stores a reference to the next node and the data, and the second is a LinkedList class which stores the head and the implementation of the push, pop, etc. methods. You can see an example in this answer.

4. Take care of the boundary cases. Calling pop on an empty stack gives a segmentation fault error. I suppose that's not the best error handling method :)

• Quik Tester: Thanks. I get that. :). What can I possibly do with node *top? Should I create a new class called list or something and move the top as a member of this class instead?
• palacsint: I think you should have two classes here, see the update please.
• Quik Tester: Alright. :). I accept your solution. And thank you very much!

Answer 2

I'd normally structure the code more like this:

template <class T>
class stack { 
 class node {
 T data;
 node *next;
 node(T const &i, node *n=NULL) : data(i), next(n) {}
 };
 node *top;
public:
 void push(T const &in) {
 top = new node(in, top);
 } 
 stack() : top(NULL) {}
};

With this general structure, you get only one top per stack (instead of one in each node), but you can still create as many stack objects as you want (something that won't work if you make top a static or global).

I've left pop un-implemented for the moment because it's really somewhat tricky to get correct. In particular, the typical definition of pop that removes the top item from the stack and returns its value can't be made exception safe unless you place some fairly tight restrictions on the data that can be stored. The stack class in the standard library takes the route of separating the two actions -- one function to get the value of the top-most item, and a second to remove the top item from the stack.

It's not at all clear to me whether you'd really prefer to do that, or stick with a design that's easy to use, but may be unsafe.

I see a couple of problems with your print. First of all, it leaks memory -- it allocates an object, and attempts to delete it, but before the delete, the pointer has been set to NULL, so the delete is a nop. I think that's a direct consequence of the second problem: it's really quite a bit more complex than necessary. I'd normally use something closer to this:

void print() { 
 for (node *p=top; p!=NULL; p=p->next)
 std::cout << p->data << "\n";
}

One more possibility to consider would be to implement the stack as a linked list of nodes, but have each node capable of holding a number of items instead of just one. This can reduce the overhead of the pointers quite a bit (e.g., as your code is written right now, in a typical implementation you have twice as much space devoted to pointers as to the data).

Answer 3

One alternative to having a separate class is to use the return value. For example:

Node * push(int x)
{
 node *top = new node;
 top->data = x;
 top->link = this;
 return top;
}

Then:

stack = stack->push(5);
stack = stack->push(7);
stack = stack->pop();

A separate stack class is probably easier to work with, but this is an option.

Additionally, a linked list is a poor choice of data structure for a stack. In almost all circumstances, a resizable array is a much better choice.

• Loki Astari: Good advice for C. Not for C++.

Answer 4

By the time I had this code together lots of people have made similar comments.

Anyway, here is my attempt at refactoring your code.

Main changes:

1. templated type - more flexible.
2. cleanup mechanism - destructor.
3. general cleanup - lots of new where not required.

Looks like this:

#include<iostream>
using namespace std;
template<typename T>
class node
{
 T data;
 node *top;
 node *link;
 public:
 node()
 {
 top=NULL;
 link=NULL;
 }
 void push(const T& x)
 {
 node *n=new node;
 n->data=x;
 n->link=top;
 top=n;
 cout<<"Pushed "<<n->data<<endl;
 }
 void pop()
 {
 node *n=top;
 top=top->link;
 n->link=NULL;
 cout<<"Popped "<<n->data<<endl;
 delete n;
 }
 void print()
 {
 node *n= top;
 while(n!=NULL)
 {
 cout<<n->data<<endl;
 n=n->link;
 }
 }
 ~node() {
 if(top) {
 node* current = top;
 node* next = 0;
 while (current != NULL) {
 next = current->link;
 delete current;
 current = next;
 }
 }
 }
};
int main()
{
 node<int> stack;
 stack.push(5);
 stack.push(7);
 stack.push(9);
 stack.pop();
 stack.print();
 return 0;
}

See @Loki's comment regarding The Rule of Three. In view of that here is my flawed second attempt:

#include<iostream>
using namespace std; //should not be in header file - just to remove std:: below
template <class T>
class stack { 
 class node {
 public:
 T data;
 node* next;
 node(T const &d) : data(d), next(0) {}
 node() : data(0), next(0) {}
 };
 node *top;
 public:
 stack() : top(0) {}
 stack(const stack& s) {
 node* nextnode = s.top;
 while(nextnode != 0)
 {
 node* newnode = new node;
 newnode->data = nextnode->data;
 newnode->next = nextnode->next;
 nextnode=nextnode->next;
 top = newnode;
 cout<<"copy constructed "<< newnode->data <<endl;
 }
 }
 stack& operator=(const stack& s) {
 node* nextnode = s.top;
 while(nextnode != 0)
 {
 node* newnode = new node;
 newnode->data = nextnode->data;
 newnode->next = nextnode->next;
 top = newnode;
 cout<<"operator = "<< newnode->data <<endl;
 delete nextnode;
 nextnode=nextnode->next;
 } 
 }
 ~stack() {
 if(top) {
 node* current = top;
 node* next = 0;
 while (current != 0) {
 next = current->next;
 cout << "dtor deleting node " << current->data << endl;
 delete current;
 current = next;
 }
 }
 }
 void push(const T& item)
 {
 node *n=new node;
 n->data=item;
 n->next = top;
 top=n;
 cout<<"Push new'd node "<< n->data << endl;
 }
 void pop()
 {
 node *n=top;
 top=top->next;
 n->next=NULL;
 cout<<"Pop delete'd node "<< n->data << endl;
 delete n;
 }
 void print()
 {
 node *n= top;
 while(n != 0)
 {
 cout<<n->data<<endl;
 n=n->next;
 }
 }
};
int main()
{
 {
 stack<int> mystack;
 mystack.push(5);
 mystack.push(7);
 mystack.push(9);
 mystack.pop();
 mystack.print();
 //test of copy ctor
 stack<int> second(mystack);
 //test of assign operator
 stack<int> third = mystack;
 }
 return 0;
}

• Loki Astari: Nice try. But this is not good. At a glance you fail the rule of three thus exposing yourself to double deletion and memory leaks all in one go. Try splitting into two classes List and Node. Then make sure the list implements rule of three.
• arcomber: @Loki - yes agreed. I just took posters code without really thinking too hard. I will spend time on it later on.
• German Petrov: are you sure that your copy and assignment constructor work in correct way? Did you try to print, for example second.print()