What is wrong in below linked list program in cpp?

Question

I'm facing weird problem that the only 1st element of the list is get printed. I have writing linked list program after long time. thanks for the help. Is there something wrong with printAll function or add function in list class. I have tried printing previous elements while adding new one & it works. So, I'm not getting why only 1st element .ie. head is getting printed & head->next seems to be null.

 #include<iostream>
using namespace std;

class Node{
public: int data;
public: Node *next;

public: Node(int data){
this->data = data;
this->next = NULL;
}
 };

class List{
 Node *head, *trav;
 public: List(){
this->head = NULL;
this->trav = NULL;
 };

 void add(int data){
 if(this->head==NULL && this->trav==NULL){

  cout<<"inside the if block"<<endl;
  this->head = new Node(data);
  this->trav = this->head->next;
}
else{
  cout <<"inside the else block"<<endl;
  this->trav = new Node(data);
  this->trav = this->trav->next;
}
  }

 void printAll(){
  this->trav = this->head;

while(this->trav!=NULL){
  cout<<this->trav->data<<endl;
  this->trav = this->trav->next;
  }
  }
    };

int main(){

 List list;

 list.add(2);
 list.add(3);
 list.add(4);
 list.add(5);
 list.printAll();

 cout<<sizeof(list);
  }

Did you do some debugging? Simplest way is to print everything before and after using it. Then https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ then https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb and if everyting else fails https://ericlippert.com/2014/03/21/find-a-simpler-problem/ — Yunnosch, May 01 '18 at 06:55

Support Ukraine · Answer 1 · 2018-05-01T09:10:21.210

Your add function doesn't link anything. Whenever you get into the else block trav is NULL and you set it equal a new node. But you never link that new node to the previous last node.

Normally trav would be named tail and point to the last element so that you can link a new element to the current last element.

Something like:

if(this->head==NULL && this->trav==NULL){
  cout<<"inside the if block"<<endl;
  this->head = new Node(data);
  this->trav = this->head;
}
else{
  cout <<"inside the else block"<<endl;
  this->trav->next = new Node(data);
  this->trav = this->trav->next;
}

Edit

OP commented that trav is not considered a tail pointer but just a pointer to traverse the list.

So therefore the answer is different as the code need to find the current tail using a loop.

Something like:

if(this->head==NULL){
  cout<<"inside the if block"<<endl;
  this->head = new Node(data);
}
else{
  cout <<"inside the else block"<<endl;
  this->trav = this->head;
  while(this->trav->next)
  {
      this->trav = this->trav->next;
  }
  this->trav->next = new Node(data);
}

However, notice:

If trav is "just" a pointer to traverse the list, there is no real purpose in making it a member of List. Simply use a local variable inside the functions that need to traverse the list.

Since your code adds new elements to end-of-list it's often a very good idea to have a tail pointer as member in List. Especially if the list can hold many elements and you frequently add new elements.

Your code use this->some_member in many places where it's not needed. Avoiding that will make your code easier to read.

In if block i'm setting trav to this->head->next; I'm using trav pointer for traversing the list. I don't want to use tail pointer. — Akshay Barpute, May 01 '18 at 07:10
@AkshayBarpute Well, if `trav` is **not** supposed to be a tail pointer then your code is even more wrong. Without a tail pointer, you'll need a `while` loop inside the `else`-block to find the current last element. — Support Ukraine, May 01 '18 at 07:13
the trav pointer is supposed to act as tail pointer while adding elements & it is used for traversing linked list while printing. — Akshay Barpute, May 01 '18 at 07:24
@AkshayBarpute then why is it a class member instead of a function-scope variable? — James Picone, May 01 '18 at 07:37

score 1 · Accepted Answer · answered May 01 '18 at 07:14

The add() method else part is not linking list properly, do some paper work. Here is the working one, I tried to explain in comments.

void add(int data){
        if(this->head==NULL && this->trav==NULL){ /* for 1st node */

                cout<<"inside the if block"<<endl;
                this->head = new Node(data);
                this->trav = this->head->next;
        }
        else{

                this->new_node = new Node(data); /*new_node */
                cout <<"inside the else block"<<endl;

                this->trav = head;/*temp var to point to ast node */
                while(this->trav->next!=NULL)  {
                        this->trav = this->trav->next;
                }

                this->trav->next = this->new_node; /*adding at end */
                this->new_node->next = NULL; /*new_node next make it NULL */
        }
}

score 0 · Answer 3 · answered May 01 '18 at 06:57

0

You never set the next pointer in Node.

Your code also has less-than-ideal indentation, uses raw pointers in places where you could use unique_ptr, doesn't initialise variables in constructors the C++ way, uses NULL instead of nullptr, and performs undefined behaviour by falling off the bottom without returning a value in a function declared to return a value (main(), specifically).

answered May 01 '18 at 06:57

James Picone

1,509
9
18

Using unique_ptr here seems to somewhat miss the point. If the point was to solve the problem using standard library, std::list would be a proper solution. – Frax May 01 '18 at 07:25
@Frax "don't just use std::list" and "don't use the standard library at all" are different restrictions; I'd expect modern C++ code to basically not use new at all. – James Picone May 01 '18 at 07:37
These are different restriction, but usually the point of writing your own list is to learn the low-level C++, in which case writing your own memory management just makes sense. I wanted to add the writing it by hand may be sligthly faster, but probably it's not true if you use unique pointer (would be true with a shared pointer, but this one you shouldn't use, so...). And indeed, modern C++ seems to use `new` sporadically if ever. – Frax May 01 '18 at 07:54

score 0 · Answer 4 · answered May 01 '18 at 07:01

0

The problem is in your add() method.

Replace it with this

void add(int data){
 if(this->head == NULL){  /*If head is null, init it and trav node*/
  cout<<"inside the if block"<<endl;
  this->head = new Node(data); /*init head*/
  this->trav = this->head; /*point to head of list*/
} else{
  cout <<"inside the else block"<<endl;
  this->trav->next = new Node(data); /* add new elem to next of trav*/
  this->trav = this->trav->next; /*move trav to next node i.e. reset */
}
}

answered May 01 '18 at 07:01

roottraveller

7,942
7
60
65

FYI, before you downvote, please add a comment with reason. – roottraveller May 01 '18 at 07:03
Not my downvote, but: (1) we look for answers showing some reasoning behind the code. Just pasting the solution without an explanation is usually considered a low-quality answer, (2) this is the 3rd answer in the row and arms to add nothing to the previous ones. – Frax May 01 '18 at 07:18

What is wrong in below linked list program in cpp?

4 Answers4