CODEWITHSUNDEEP
c++linked-list
Bob John
Bob John

Reputation: 3888

How do you perform a deep copy on a doubly-linked list?

I'm having a hard time getting around the pointers. I can imagine someone here can make conceptualizing the copy constructor much more intuitive. I understand that you can't simply assign pointers to each other (shallow copy), but I'm having a hard time actually copying the objects.

Here's a sample of my code:

class LList {
    /* stuff */

    private:
        struct node {
            node   *next;
            node   *prev;
            int    *o;
        };

        node   *first; // The pointer to the first node (NULL if none)
        node   *last;  // The pointer to the last node (NULL if none)
}

Thanks for the help!

Upvotes: 1

Views: 5570

Answers (3)

Joseph Mansfield
Joseph Mansfield

Reputation: 110728

When you are writing the copy constructor, X(const T& other), for an object, X, that contains a dynamically allocated T* p (probably a Node* in your case), you will likely end up writing a line like this:

p = new T(*other.p);

This creates a copy of the object being pointed to by the object you're copying, giving you a deep copy of that object. In your case, this would end up in a recursive deep-copying of the list.

Upvotes: 3

sje397
sje397

Reputation: 41862

Untested, but this might express part of the idea you're getting at. I'd try to use std::list instead though :) You should add a copy assignment operator and a destructor that allocates/deallocates appropriately as well. See here.

template<typename T>
struct ListNode {
    ListNode *next, *prev;
    T value;

    ListNode(const T &val): value(val), next(0), prev(0) {}

    // copy constructor
    ListNode(const ListNode &other): value(other.value) {
        if(other.next)
           append(new ListNode(*other.next));
    }

    void append(ListNode &n) {
        next = &n; n.prev = this;
    }
};

If your value is a pointer, then you'll want to copy that in the same way the next pointer member is copied above, i.e.:

    // copy constructor
    ListNode(const ListNode &other): value(new T(*other.value)) {
        if(other.next)
           append(new ListNode(*other.next));
    }

So for your example list above, you might try something like this:

class LList {
    LList(): first(0), last(0) {}

    // copy constructor
    LList(const LList &other):
        first(0),
        last(0)
    {
        if(other.first) {
          first = new node(*other.first);
          // find last item
          last = first;
          while(last->next) last = last->next;
        }
    }

    ~LList() {
       if(first) delete first;
    }

    // TODO: copy assignment operator

private:
    struct node {
        node(int val): next(0), prev(0), o(new int(val)) {}
        // copy constructor
        node(const node &other): next(0), prev(0), o(*other.o)
        {
            if(other.next) {
               next = new node(*other.next);
               next->prev = this;
            }   
        }

        ~node() {
          delete o;
          if(next) delete next;
        }
        // TODO: copy assignment operator

        node   *next;
        node   *prev;
        int    *o;
    };

    node   *first; // The pointer to the first node (NULL if none)
    node   *last;  // The pointer to the last node (NULL if none)
};

Untested but that's the idea...constructors work recursively by operating on the next item. The 'TODO' items are important, as explained by the link. You might also want to look into smart pointers - they remove the need to remember to delete things, improve exception safety and are generally a much safer option than raw pointers.

Upvotes: 1

asheeshr
asheeshr

Reputation: 4114

Creating a deep copy of a linked list is equivalent to creating a new linked list with the same data values.

So, you could

  • Traverse through your current list
  • Extracting the information from each node
  • Pass it to a new node (essentially copying everything other than the list pointers)
  • Add that to the new list (which is the deep copy).

In your case, you need to deference o, extract the data, allocate a new block, assign the data and then add that to the new node.

Upvotes: 1

Related Questions