Double Linked Lists in C++

Question

NOTE: THIS IS FOR HOMEWORK SO PLEASE DO NOT INCLUDE BLOCKS OF CODE IN YOUR ANSWERS

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

 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.

Answer 3

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.

Answer 4

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.

Answer 5

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)