I'm creating my first linked list and I have found something weird, in my main function whenever I call printf() the start pointer which points to the first node in my linked list shows that the data is garbage and the next pointer is a very random address, unlike if I didn't use printf() it seems good and all nodes are created and all good!
#include <iostream>
int node_counter = 0;
struct node
{
int data;
node* next;
};
node* start;
void creat_ll()
{
node n1;
start = &n1;
n1.data = 0;
n1.next = NULL;
node_counter ;
}
void insertNode(int x)
{
node* ptr = start;
while (ptr->next != NULL)
{
ptr = ptr ->next;
}
node* temp = ptr;
ptr = new(node);
ptr->data = x;
ptr->next = NULL;
printf("node number: %d\n",x);
temp->next = ptr;
node_counter ;
}
int main()
{
creat_ll();
insertNode(10);
insertNode(20);
// printf("number of nodes = %d \n", node_counter);
insertNode(30);
printf("test\n");
printf("number of nodes = %d \n", node_counter);
insertNode(40);
insertNode(50);
insertNode(60);
insertNode(70);
printf("number of nodes = %d \n", node_counter);
}
CodePudding user response：
As people mentioned in the comments, the problem is not related to printf(), but to dangling pointers. In the local scope of creat_ll(), you've created a variable node n1 (allocated on the stack) and then assigned the address of n1 to start, which has global scope. Once the creat_ll() function exits, everything in the scope of creat_ll() is gone, including n1. So in main(), start points to deleted data.
This, of course, would be solved if you allocate all your variables on the heap (i.e. use keywords new and delete). On the heap, you can create or delete variables from anywhere and they'll stick around until you delete them (or until your program exits). If you allocate n1 on the heap, the memory survives even after create_ll() exits. However, with this, you take on the responsibility of managing the underlying memory yourself, meaning that once you're done with your list, something has to go back and delete all the nodes; otherwise, the nodes stick around and you end up with a memory leak.
Cherno has a great video on object lifetime that you can find here: https://youtu.be/iNuTwvD6ciI. At 4:30, he shows an example that is nearly identical to yours.
So a better overall implementation is to create a class that handles all of this. We should be able to create a linked list, add nodes to it (allocate memory), remove nodes from it (delete memory), and, once we're done with it, delete all memory associated with the linked list.
Below is an example implementation. I'll leave the implementation of the remove() method to you.
#include <cstdio>
struct node
{
int data;
node* next;
};
class LinkedList
{
public:
LinkedList() = default;
// Add x to the end of the list.
void push_back(const int value)
{
if (root == nullptr)
{
root = new node{ };
root->data = value;
root->next = nullptr;
}
else
{
node* ptr { root };
while (ptr->next != nullptr)
{
ptr = ptr->next;
}
node* const newNode { new node{ } };
newNode->data = value;
newNode->next = nullptr;
ptr->next = newNode;
}
size;
}
// Remove the first occurrence of x.
void remove(const int value)
{
// left as an exercise
}
void printList() const
{
std::printf("Number of nodes: %lu\n", size);
const node* ptr { root };
while (ptr != nullptr)
{
std::printf("%d ", ptr->data);
ptr = ptr->next;
}
std::printf("\n");
}
~LinkedList()
{
const node* ptr { root };
while (ptr != nullptr)
{
const node* const next { ptr->next };
delete ptr;
ptr = next;
}
size = 0;
}
private:
node* root { nullptr };
std::size_t size { 0 };
};
int main()
{
LinkedList ll { LinkedList{ } };
ll.push_back(10);
ll.push_back(20);
ll.printList();
ll.push_back(30);
ll.push_back(40);
ll.printList();
}
Output:
Number of nodes: 2
10 20
Number of nodes: 4
10 20 30 40
EDIT: Here is a minimal example of memory getting overridden due to the stack getting popped. Note that this behavior is undefined, so depending on the compiler you're using, you may see some output or get a segfault. I'm using gcc and I get the output shown below.
#include <iostream>
#include <string>
std::string* s;
void createString()
{
std::string local_string = "This string is about to get popped out of the stack.";
s = &local_string;
std::cout << *s << std::endl;
}
int main()
{
createString();
std::cout << *s << std::endl;
return 0;
}
Output 1
This string is about to get popped out of the stack.
0D8Vbout to get popped out of the stack.
Output 2
This string is about to get popped out of the stack.
Ubout to get popped out of the stack.
Output 3
This string is about to get popped out of the stack.
tUbout to get popped out of the stack.