I'm learning about linked lists and am trying to understand why the "new" operator is used when inserting a node in the linked list. Specifically I am wondering why the following implementation of insertAtEnd results in an infinite loop when calling display() after two or more insertAtEnd calls.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node() {
data = 0;
next = NULL;
}
Node(int x) {
data = x;
next = NULL;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = NULL;
}
// insert a node at the end of the linked list
void insertAtEnd(int x) {
Node newNode = Node(x);
Node* current = head;
// if LL is empty
if (head == NULL) {
head = &newNode;
}
// if LL is non-empty
else {
while (current->next != NULL) {
current = current->next;
}
current->next = &newNode;
}
}
// print out the contents of the linked list
void display() {
Node* current = head;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
LinkedList llist;
llist.insertAtEnd(1);
llist.insertAtEnd(2);
llist.insertAtEnd(3);
llist.display();
return 0;
}
// output shows 3 3 3 3 3 3 3 3 3 3 3 3 3 3 .....
I know that using the new operator would fix the issue,
// insert a node at the end of the linked list
void insertAtEnd(int x) {
Node* newNode = new Node(x);
Node* current = head;
// if LL is empty
if (head == NULL) {
head = newNode;
}
// if LL is non-empty
else {
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
but I'm having difficulty understanding why using new here works and why the previous insertAtEnd, which doesn't use new, doesn't work.
My understanding is if new is used, additional memory is dynamically allocated on the heap (different memory location) each time I call insertAtEnd. If new isn't used, then insertAtEnd creates a node object on the stack each time its called, which is in the same memory location, causing the values inserted to overwrite the previously inserted values. But I'm not sure why the output is 3 3 3 3 3... rather than 1 2 3 or just 3 if using the insertAtEnd implementation without new.
Note that after leaving a function (e.g., llist.insertAtEnd), the stack area will be reused by later function calls (e.g., llist.display), thus possibly overwriting previously used values. Also, different compilers may used different orderings of values on the stack. As such, the behavior will depend on things like which compiler you're using, so it's UB (Undefined Behavior).
Nonetheless, here's what is basically happening in your case. During each call to insertAtEnd, the constructor is invoked for your newNode object on the stack, so data is set to x (i.e., 1, 2 or 3), and next is set to NULL. After the function ends, since you have not created a Node destructor, the default one is invoked instead, with it not doing anything in your case, so the values of data and next are left unchanged.
Also, during the first call, the value of head is NULL, so head is assigned to point at your newNode object on the stack. For the second and third calls, since head is not NULL, it will check current, i.e., head, which is pointing to newNode. Since the constructor set that to NULL, the line current->next = &newNode; sets it to point to newNode. In other words, at that point, newNode.next is pointing to itself.
Since this is not changed on exit, this is what is left being used, i.e., the next pointer is pointing to its own object. Also, on the third call, the value of newNode.data is 3. Thus, llist.display(); goes into an infinite loop (since current->next always points back to itself, it will never be NULL), repeatedly outputting the value of 3.
The reason new works properly instead is that, on each call to llist.insertAtEnd, a different area of memory is used for the Node object, so the issues mentioned above don't apply then.