0

My background: I didn't read too much about memory allocation through stack and heap, but stack allocation it's 'casually' said to be faster. I think that when you create an object with new keyword you are using somehow heap allocation, I don't expect it when I just do A a;.

Problem: I'm trying to implement a linked list in C++ with the possibility to insert an element in any position nth. For this I implemented a flag, that would help control the position, but when i use this declaration the data in my head pointer changes. I reduced the original code, but the following resumes the problem:

#include <iostream>
struct node {
    int data;
    node* next;
    node* prev;
    node(int dat) { data = dat; next = nullptr; prev = nullptr; }
    
};
struct Linked_list {
    node* head;
    node* tail;
    Linked_list(int data) {
        node init(data);
        head = &init;
        tail = &init;
    }
    void insert() {
        node* iterator = head;
        std::cout << head->data;
        int flag = 0; 
//prints -858993460 if we declare the flag. 
//If flag declaration doesn't exist prints 12;
    }
};
int main()
{
    Linked_list A(12);
    A.insert();
}

Why is this happening? I really need to implement it dinamically?

  • 2
    `-858993460` means uninitialized memory. Its 0xcccccccc here: [https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations](https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations) – drescherjm Nov 08 '21 at 01:30
  • 1
    `head = &init;` is a bug. You can't store the address of a local variable past the function it is defined in and use it later. The lifetime of init ended in the constructor. The pointer you store is no longer valid when the constructor ends. – drescherjm Nov 08 '21 at 01:32
  • I totally forgot it was a local variable... So the 12 it printed was the remainder in that memory, but it already could be rearranged and it is what happened due to the flag declaration, resulting in lost of the value, right? –  Nov 08 '21 at 01:38
  • 1
    It's undefined behavior to dereference your `head` or `tail` because of the dangling pointer. With undefined behavior anything can happen. – drescherjm Nov 08 '21 at 01:41
  • 1
    To fix this you will have to dynamically allocate your nodes. – drescherjm Nov 08 '21 at 01:43
  • 1
    *"it's 'casually' said to be faster."* -- another casual saying is that it's better to be correct than fast... ;) – JaMiT Nov 08 '21 at 03:37
  • 1
    You can implement such a list on the stack if you have a fixed number of nodes allocated in an array that is part of your class. When you need a node and there are free ones available you can get a pointer to the node from the list of nodes that are available and not used using `&` . You will have to track which nodes are used and what nodes are not. This answer describes the allocation from the stack part: [https://stackoverflow.com/a/64745517/487892](https://stackoverflow.com/a/64745517/487892) – drescherjm Nov 08 '21 at 13:41

0 Answers0