Implementing doubly linked list where Data is stored on the Heap?

Question

Im trying to implement a doubly linked list where the nodes are stored on the stack but the data of the nodes on the heap. You can add a new node with data to the list with push() and remove the last element with pop().

I have problems with the push() method.

#include <iostream>

using namespace std;

struct Data {
    string name;
    int age;
};

struct Node {
    struct Node *next;
    struct Node *previous;   
    struct Data *d;         
};

struct Node *first;
struct Node *last;

void init() {
    first = last = NULL;
}


void push(Data d) { 
    Node *temp;

    if(first == NULL){
        first = new Node();
        first->d = malloc(sizeof(struct Data *));
        first->next = NULL;
        first->previous = NULL;
        last = first;
    } else if(last->next == NULL) {
        last->next = new Node();
        temp = last;
        last = last->next;
        last->previous = temp;
        last->d = first->d = malloc(sizeof(struct Data *));
    }
}


int main(int argc, char *argv[]) {
    init();

    Data d;

    d.name = "Name1";
    d.age = 19;
    push(d);

    d.name = "Name2";
    d.age = 24;
    push(d);

    d.name = "Name3";
    d.age = 25;
    push(d);

    d.name = "Name4";
    d.age = 18;
    push(d);

    d.name = "Name6";
    d.age = 20;
    push(d);    
}

I get always the following Error:

Untitled.cpp:29:12: error: assigning to 'struct Data *' from incompatible type 'void *'
                first->d = malloc(sizeof(struct Data *));
                         ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Untitled.cpp:38:22: error: assigning to 'struct Data *' from incompatible type 'void *'
                last->d = first->d = malloc(sizeof(struct Data *));
                                   ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2 errors generated.

Why do I get the following error? How to fix it? What Im doing wrong?

`std::string` ist C++ and not C. C is not C++. Why are you using `malloc` and not `new`? If every `Node` has a `Data` why are you using dynamic allocation? — Simon Kraemer, May 03 '17 at 13:02
You should not be using `malloc` and friends in C++. C++ has `new` and `delete` for dynamic memory allocation. Better yet it has `std::list` that you can use and not even worry about building your own. — NathanOliver, May 03 '17 at 13:02
http://en.cppreference.com/w/cpp/container/list "It is usually implemented as a doubly-linked list." — Ceros, May 03 '17 at 13:04
So, you're allocating a pretty weird amount of memory for `d`, but aren't actually storing anything there... — ForceBru, May 03 '17 at 13:05
And let's tack on the fact that you claim the Nodes are stored on the stack, but all dynamic memory allocation is from the heap. — Phil M, May 03 '17 at 13:10

score 5 · Answer 1 · edited May 23 '17 at 11:54

5

Advice: do not use malloc, use new and delete to deal with the heap in C++. Even stronger advice: never mix new/delete with malloc/free. The error comes from the fact C++ needs a cast from void*

first->d = (struct Data*)malloc(sizeof(struct Data *));
                                                   ^ this is also wrong (read more later)

Other suggestions: learn about smart pointers and possibly containers. They'll save you a lot of headaches while letting you concentrate on the algorithms.

Algorithmically speaking your (I suppose incomplete) code will probably not do what you want: you're allocating space for a pointer (something the Node object already has), so you'll end up with a pointer pointing to space for another pointer (?). This is probably what you meant in the first place

first->d = new Data(d);

I'm leaving fixing the rest as an exercise.

edited May 23 '17 at 11:54

Community

1
1

answered May 03 '17 at 13:04

Marco A.

43,032
26
132
246

`sizeof(struct Data *)` should also be changed to `sizeof(struct Data)`. – Simon Kraemer May 03 '17 at 13:13
If you're going to show him how to correctly use `malloc`, show him how to explicitly call the constructor? – Phil M May 03 '17 at 13:14
2

They also need to call the constructor as `malloc` does not call the constructor. – NathanOliver May 03 '17 at 13:15

score -2 · Answer 2 · edited Apr 02 '20 at 14:42

-2

You need to cast the result of malloc() to the desired type.

hint - there's also something wrong with the size of your malloc

edited Apr 02 '20 at 14:42

Ðаn

10,934
11
59
95

answered May 03 '17 at 13:04

Erix

7,059
2
35
61

2

`malloc` itself is wrong here as it will not call `Data`'s constructor. – NathanOliver May 03 '17 at 13:07
2

@NathanOliver just because it doesn't call the constructor doesnt make it wrong. there is nothing wrong with malloc in c++ – Erix May 03 '17 at 13:08

Implementing doubly linked list where Data is stored on the Heap?

2 Answers2