Double Linked Lists in C++

Question

I have an assignment that requires us to implement a doubly linked list class. For some reason they defined the node struct as follows:

struct node {
  node   *next;
  node   *prev;
  T      *o;
};

It seems to me that it would be a lot easier to write the class if the struct member 'data' were not a pointer. Needless to say I can't change it so I'm going to have to just work around it. I tried implementing the method that adds an element to the beginning of the list as follows:

template <typename T>
void Dlist<T>::insertFront(T *o) {
    node *np = new node;
    T val = *o;

    np->o = &val;
    np->prev = NULL;
    np->next = first;

    if (!isEmpty()) {
        first->prev = np;
    } else {
        last = np;
    }
    first = np;
}

While using ddd to debug I realized that everything works fine the first time you insert a number but the second time around everything gets screwed up since as soon as you set 'val' to the new element it "overwrites" the first one since the memory address of val was used. I tried doing other things like instead of just having the 'val' variable doing the following:

T *valp = new T;
T val;
valp = &val;
val = *o;

np->o = valp

This didn't seem to work either. I think this is because it's pretty much just a more complicated form of what I did above just with an additional memory leak :)

Any ideas/pointers in the right direction would be great.

Take a look at this, the first answer may help you understand the problem: http://stackoverflow.com/questions/5727/what-are-the-barriers-to-understanding-pointers-and-what-can-be-done-to-overcome — Dan, Dec 11 '09 at 05:30
When you get a chance take a look at this too: http://stackoverflow.com/questions/599308/proper-stack-and-heap-usage-in-c -- difference between stack and heap allocation. — Dan, Dec 11 '09 at 05:41

Drew Dormann · Accepted Answer · 2009-12-12T14:47:00.547

6

the T val you create is an automatic variable. Your mistake is storing the address to that stack variable.

You should be using new to allocate space on the heap, as you suspect, but your data pointer needs to point directly to the address returned by new.

Your mistake in your latest attempt is here:

valp = &val;

You are changing valp to point somewhere else (the address of val), when you are likely trying to copy val's data, not its address.

The data passed to your function should be copied to the new memory where valp points.

edited Dec 12 '09 at 14:47

answered Dec 11 '09 at 05:11

Drew Dormann

59,987
13
123
180

Ahh. That makes sense as to why I was getting values back -1074723840 when I was trying to read the values. That helps although I guess I'm still not quite sure how to go about fixing this? Can you give me any keywords that might help me in my search? Thanks. – Ian Burris Dec 11 '09 at 05:14
1

Just nitpicking: val is not a temporary. It is an "automatic" variable, aka a stack variable. Otherwise, good answer. – Dan Dec 11 '09 at 05:17
Edited, to hopefully answer your comment. – Drew Dormann Dec 11 '09 at 05:20
Totally right, Dan. And not nitpicking. I used the wrong term there. – Drew Dormann Dec 11 '09 at 05:37

Wyzard · Answer 2 · 2009-12-11T05:47:25.770

4

I don't think you should be doing this:

T val = *o;

Since the o member in the node structure is a pointer, and the parameter to insertFront is also a pointer, your instructor probably intends for you to take the pointer you're given and store it in the list, not make a copy of the object and store a pointer to that. Just store the o pointer passed into insertFront as the o member of the node and you should be OK.

edited Dec 11 '09 at 05:47

answered Dec 11 '09 at 05:15

Wyzard

33,849
3
67
87

1

i totally agree. It should rather be `np->data = o;` – Samrat Patil Dec 11 '09 at 05:17
Not necessarily. There should be some comments explaining whether the T* passed in is dynamically allocated or not and whether the DList is supposed to take ownership of it or whether it is supposed to make a copy. If you don't know the answers to those questions you can't possibly implement it correctly except by luck. – Dan Dec 11 '09 at 05:21
1

@Sammy, how do you know it shouldn't be `np->data = new(*o);` ? – Dan Dec 11 '09 at 05:22
Sorry guys, I modified the struct after copying it into SO and forgot to change it other places. – Ian Burris Dec 11 '09 at 05:32

score 0 · Answer 3 · answered Dec 11 '09 at 05:13

0

 T val = *o;

    np->o = &val;

This part is suspicious. The hint is that the memory allocated on stack in a function will not be available once the function goes out of scope.

answered Dec 11 '09 at 05:13

aJ.

34,624
22
86
128

score 0 · Answer 4 · answered Dec 11 '09 at 05:17

Your code doesn't fit your definition of node -- in node you're defining a data member, but in your code you're using o instead.

In any case, you're going to have to do two dynamic allocations to add each node -- one for the node itself, and one for the data object it's going to point to. When you allocate that data object, you might as well assign the return value from new directly to the pointer in your node. Then you'll need to copy the data object whose pointer was passed into the data object you just allocated, that the pointer in the node is pointing at.

Good catch. I modified the struct after copying it into SO and forgot to change it other places. — Ian Burris, Dec 11 '09 at 05:30

xtofl · Answer 5 · 2009-12-11T06:59:03.843

You think the pointer payload is inconvenient. But maybe the list is meant to be used to create a link on top of existing objects, like in:

struct A { int i; };
A as[10] = { 1,2,3,4,5,6,7,8,9,10 };

LinkedList primes_in_my_data;
insertFront( primes_in_my_data, &as[1] );
insertFront( primes_in_my_data, &as[2] );
insertFront( primes_in_my_data, &as[3] );
insertFront( primes_in_my_data, &as[5] );
insertFront( primes_in_my_data, &as[7] );

// now I have a linked list of primes, and caused no extra memory allocation
// (except for the list overhead)

Double Linked Lists in C++

5 Answers5