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.

Answer 1

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.

Answer 2

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.