Cannot Insert Item into Linked List

Question

void LinkedList::insert(int num, int pos) {
  Node *newNode = new Node;
  newNode->data = num;
  newNode->next = NULL;
  if(pos == 0) {
    newNode->next = head;
    head = newNode;
  }
  else {
    Node *temp = head;
    for (int i = 1; i < pos-1; ++i) {
      if (temp != NULL) {
        temp = temp->next;
      }
    }
    if (temp != NULL) {
      newNode->next = temp->next;
      temp->next = newNode;
    }
    else {
      cout << " The previous node is full.";
    }
  }
}

This is my insert function. The code that runs in main.cpp is:

// adding through insert
    nums.insert(1, 0);
    nums.insert(5, 4);
    nums.insert(3, 7);

And the output is:

List after append: 
8   6   7   8   0   9

List after inserting: 
1   8   6   5   7   8

As you can see, something is getting overwritten, or the end of the list just gets cut off. I have searched the internet for hours to no avail. The output needs to increase the length of the list and not overwrite anything. Any help would be appreciated.

The exact code as shown, running *only* what is demonstrated in your 'main.cpp', should produce two declarations of "The previous node is full." and a single node '1' in the list printout. So, how about we update this question with a proper [mcve] that actually produces the output you're claiming. — WhozCraig, Apr 21 '22 at 21:45
@dman773 What does this message cout << " The previous node is full."; mean?! I think that if the position exceeds the size of the list then a new node should be appended to the end of the list. — Vlad from Moscow, Apr 21 '22 at 21:47
Adding an item to a singly linked list is ludicrously easy if you abstract away the difference between `head` and `next` with a pointer to a pointer. [Here's a trick from WhozCraig](https://stackoverflow.com/a/22122095/4581301) showing how to remove an item from a list that you can steal ideas from. — user4581301, Apr 21 '22 at 21:54
@user4581301 lols. I remember updating that :-) Anyway for the OP, that same nuance adapted to the OPs code [is here](https://pastebin.com/q2mekUaV), including the odd announcement of "full" (whatever that means) on positional overreach. — WhozCraig, Apr 21 '22 at 22:00
@dman773 The code shown does not produce the output shown ([demo](https://ideone.com/aSOunC)). The output I get is: `List after inserting: 1 8 6 5 7 8 3 0 9`, which is still not correct, but is not what you claim. The output is `1 8 6 7 5 8 0 3 9` after fixing the broken loop in `insert()` as [Vlad suggested](https://stackoverflow.com/a/71961294/65863) ([demo](https://ideone.com/BuIsLx)), or as WhozCraig suggested ([demo](https://ideone.com/WUL0V9)). — Remy Lebeau, Apr 21 '22 at 22:28

Vlad from Moscow · Answer 1 · 2022-04-21T21:59:58.067

The problem is this for loop

for (int i = 1; i < pos-1; ++i) {
  if (temp != NULL) {
    temp = temp->next;
  }
}

Let's assume that pos is equal to 2. In this case the loop will not iterate and temp will be equal to head. So the new node will be inserted before the second mode instead to be inserted before the third node.

You need to write

for (int i = 1; temp != nullptr && i < pos; ++i) {
    temp = temp->next;
}

Also instead of writing this message

 cout << " The previous node is full.";

(it is the caller of the function should decide whether to output a message) I would declare the function like

bool LinkedList::insert(int num, int pos) {

and return either true or false dependent on whether a node was inserted.

Cannot Insert Item into Linked List

1 Answers1