Linked List insertion isn't working in for/while loop-CodePudding

I am learning DSA, and was trying to implement linked list but the insertion function that i wrote is not working in a for or while loop, its not the same when i call that function outside the loop, it works that way. I am not able to figure it out, please someone help me.

#include <iostream>

class Node {

public:
  int data;
  Node *next;

  Node(int &num) {
    this->data = num;
    next = NULL;
  }
};

class LinkedList {

  Node *head = NULL;

public:
  void insert(int num) {
    Node *tmp;
    if (head == NULL) {
      head = new Node(num);
      tmp = head;
    } else {
      tmp->next = new Node(num);
      tmp = tmp->next;
    }
  }

  void printList() {
    Node *tmp = head;
    while (tmp) {
      std::cout << tmp->data << "  ";
      tmp = tmp->next;
    }
    std::cout << std::endl;
  }

  void reverseList() {
    Node *curr = head, *prev = NULL, *nextNode;
    while (curr) {
      nextNode = curr->next;
      curr->next = prev;
      prev = curr;
      curr = nextNode;
    }
    head = prev;
  }
};

int main() {
  LinkedList list1;
  // This is not working
  int num;
  while (num != -1) {
    std::cin >> num;
    list1.insert(num);
  }

  // This is working
  // list1.insert(1);
  // list1.insert(2);
  // list1.insert(3);
  // list1.insert(4);
  // list1.insert(5);

  list1.printList();
  list1.reverseList();
  list1.printList();

  return 0;
}

I expect this after insertion

Edit: although @Roberto Montalti solved this for me, but before that I tried passing incrementing value using a for loop which worked but as soon as I pull that cin out it crashes. can someone tell me what's happening under the hood?

for (int i = 1; i <= 10; i  )
{
    list1.insert(i);
}

CodePudding user response：

When inserting the nth item (1st excluded) tmp is a null pointer, i don't understand what you are doing there, you are assigning to next of some memory then you make that pointer point to another location, losing the pointer next you assigned before, you must keep track of the last item if you want optimal insertion. This way you are only assigning to some *tmp then going out of scope loses all your data... The best way is to just keep a pointer to the last inserted item, no need to use *tmp.

class LinkedList
{
   Node *head = NULL;
   Node *tail = NULL;

public:
    void insert(int num)
    {
        if (head == NULL)
        {
            head = new Node(num);
            tail = head;
        }
        else
        {
            tail->next = new Node(num);
            tail = tail->next;
        }
    }
...
}

CodePudding user response：

You need to loop until you reach the end of the list and then add the new node after that. Like this.

void insert(int num) {
    Node *tmp = head;
    if (head == NULL) {
        head = new Node(num);
    }
    else {
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = new Node(num);
    }
  }

CodePudding user response：

first of all you need to define a node for each of the tail and head of the list as follows

Node *h;
Node *t;

you may also separate the Node from the LinkedList class so you can modify easily

class Node{
public:
    int data;
    Node *next;
    Node(int data, Node* next);
    ~Node();
};
Node::Node(int data, Node* next)
{
    this->data= data;
    this->next= next;
}
Node::~Node(){}
}

after that you can try to add these functions to your LinkedList class so it can deal with other special cases such empty list or full, etc..

void addToHead(int data){
Node *x = new Node(data,h);
    h=x;
    if(t==NULL){
        t=x;
    }


void addToTail(int data){
Node *x = new Node(data,NULL);
    if(isEmpty()){
        h=t=x;
    }
    else
    {
        t->next=x;
        t=x;
    }
}

now for the insert function try this after you implemented the Node class and the other functions,

void insert(int v){
if(h==nullptr){addToHead(v); return;}
if(h->data>=v) {addToHead(v);return;}
if(t->data<=v) {addToTail(v); return;}
// In this case there is at least two nodes
Node *k=h->next;
Node *p=h;

while(k != nullptr){
if(k->data >v){
Node *z =new Node(v,k);
p->next=z;
return;
}
p=k;
k=k->next;
}

}

the idea of making all of this is not lose the pointer when it goes through elements in the Linked List so you don't end up with a run time error.

I hope this can be useful to you.

CodePudding user response：

There was an issue with your insert function. Read about segmentation fault here https://www.geeksforgeeks.org/core-dump-segmentation-fault-c-cpp/#:~:text=Core Dump/Segmentation fault is,is known as core dump.

for a quick workaround you can use this

using namespace std;
#include <iostream>
    class Node
    {
    public:
        int data;
        Node *next;
        Node(int num)
        {
            this->data = num;
            next = NULL;
        }
    };
    
    class LinkedList
    {
    Node *head = NULL;
    
    public:
        void insert(int num)
        {
            Node *tmp= new Node(num);
            tmp->next=head;
            head=tmp;
        }
        void printList()
        {
            Node *tmp = head;
            while (tmp)
            {
                std::cout << tmp->data << "  ";
                tmp = tmp->next;
            }
            std::cout << std::endl;
        }
        void reverseList()
        {
            Node *curr = head, *prev = NULL, *nextNode;
            while (curr)
            {
                nextNode = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nextNode;
            }
            head = prev;
        }
    };
    
    int main()
    {
        LinkedList list1;
        // This is not working
        int num,i=0,n;
        cout<<"Type the value of n";
        cin>>n;
        while (i<n)
        {
            cin >> num;
            cout<<num<<" "<<&num<<endl;
            list1.insert(num);
            i  ;
        }

    
        list1.printList();
        list1.reverseList();
        list1.printList();
    
        return 0;
    }