8

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.

Improve this question
3
  • 5
    +1 for the honorable homework disclaimer. Commented Dec 11, 2009 at 5:25
  • Take a look at this, the first answer may help you understand the problem: stackoverflow.com/questions/5727/… Commented Dec 11, 2009 at 5:30
  • When you get a chance take a look at this too: stackoverflow.com/questions/599308/… -- difference between stack and heap allocation. Commented Dec 11, 2009 at 5:41

5 Answers 5

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

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.
Just nitpicking: val is not a temporary. It is an "automatic" variable, aka a stack variable. Otherwise, good answer.
Edited, to hopefully answer your comment.
Totally right, Dan. And not nitpicking. I used the wrong term there.
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.

Improve this answer

4 Comments

i totally agree. It should rather be np->data = o;
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.
@Sammy, how do you know it shouldn't be np->data = new(*o); ?
Sorry guys, I modified the struct after copying it into SO and forgot to change it other places.
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.

Improve this answer

Comments

0

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.

Improve this answer

1 Comment

Good catch. I modified the struct after copying it into SO and forgot to change it other places.
0

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)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.