Singly Linked List in C++ is not reading more than 2 nodes

Question

Below is a simple program for insertion in a linked list, however, whenever I run the program, it reads only two input values for the list and stops further execution. Why is that? I am unable to catch the issue.

/**** Defining structure of node *****/
class Node{
    public:
        int data;
        Node* next;     
        Node(int val){
            data = val;
            next = NULL;
        }
};

/**** Inserting node at the end ****/
Node* insertAtEnd(Node* &head, int val){
    Node* n = new Node(val);
    if(head == NULL){
        head = n;
    }
    Node* tmp = head;
    while(tmp->next != NULL){
        tmp = tmp->next;
    }
    tmp->next = n;
    return tmp;
}

/**** Menu ****/
int menu(){
    int ch;
    cout<<"1. Insert node"<<endl;
    cout<<"Enter your choice: ";
    cin>>ch;
    cout<<endl;
    return(ch);
}

/**** Driver Code ****/
int main(){
    Node* head = NULL; int n, data;
    switch(menu()){
        case 1:
            cout<<"\nEnter number of nodes you want to enter: ";
            cin>>n;
            for(int i = 0; i<n; i++){
                cout<<"Enter data: ";
                cin>>data;
                insertAtEnd(head, data);
            }
            break;
        default:
            cout<<"Wrong Choice";
    }
}

It appears that your InsertAtEndFunction does not correctly handle the case when head is NULL. You are ending up with a list where head->next == head. — Sven Nilsson, May 27 '21 at 16:21
People need to stop teaching C-style linked lists when C++ is the language. — sweenish, May 27 '21 at 16:23
You should maintain a pointer to the last node in the list. This would make inserting at the end of the list a lot more efficient. — Thomas Matthews, May 27 '21 at 16:32
@SvenNilsson yeah, I should have added return after head = n; thanks a lot — Manya Sharma, May 27 '21 at 16:35
Also check whether you need to return `temp` or `head` inside insertAtEnd function — Rohith V, May 27 '21 at 18:36
@ManyaSharma It would be better to re-write `insertAtEnd()` to eliminate the `if` block completely, eg: `Node* insertAtEnd(Node* &head, int val){ Node** n = &head; while (*n) { n = &((*n)->next); } *n = new Node(val); return *n; }` Even better, if you do what ThomasMathews suggested and maintain a separate `tail` pointer, then you don't have to hunt for the end of the list each time. — Remy Lebeau, May 27 '21 at 18:43

score 0 · Accepted Answer · answered May 28 '21 at 02:42

0

The insertAtEnd needs an early return with the first node, or it will ran into a infinite loop.

  Node* insertAtEnd(int val) {
    Node* n = new Node(val);
    if (head == NULL) {
      head = n;
      return head;
    }
    Node* tmp = head;
    while (tmp->next != NULL) {
      tmp = tmp->next;
    }
    tmp->next = n;
    return tmp;
  }

Your code is mostly c-style and hasn't dealt with memory deallocation, so memory is leaked.

I have added on list class to make it more naturally in C++, add use destructor to free the dynamic memory.

struct List {
  Node* head = nullptr;

  Node* insertAtEnd(int val) {
    Node* n = new Node(val);
    if (head == NULL) {
      head = n;
      return head;
    }
    Node* tmp = head;
    while (tmp->next != NULL) {
      tmp = tmp->next;
    }
    tmp->next = n;
    return tmp;
  }
  ~List() {
    while (head) {
      auto tmp = head->next;
      delete head;
      head = tmp;
    }
  }
};

Online demo

answered May 28 '21 at 02:42

prehistoricpenguin

6,130
3
25
42

Using a destructor is really new to me, I'll definitely try this one. Also never in entire semester our professor mentioned 'auto' keyword, I'll also check upon this one. Thanks:) – Manya Sharma May 29 '21 at 14:07
@ManyaSharma You need a modern c++ text book,https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list – prehistoricpenguin May 29 '21 at 15:01
@prehistoricoenguin it solved my problem! Thanks a lot! – Manya Sharma Jun 03 '21 at 04:10
@ManyaSharma Please read this https://stackoverflow.com/help/someone-answers – prehistoricpenguin Jun 03 '21 at 05:04

score 0 · Answer 2 · answered May 28 '21 at 03:21

In function add Node at the end of List, i think you should pass by value the pointer "Node* head" NOT pass by reference "Node*& head" . I actually coded like that and my code runned correctly without any bug. You can refer my code below

Node* addtail(Node* head, int value) {   //  
    Node* p;
    Node* temp = new Node;
    temp->data = value;
    temp->next = NULL;
    if (head == NULL) {                  // if head empty => head = temp instantly 
        head = temp;
    }
    else {
        p = head;
        while (p->next != NULL) {         
            p = p->next;
        }
        p->next = temp;
    }
    return head;
}

Singly Linked List in C++ is not reading more than 2 nodes

2 Answers2