CODEWITHSUNDEEP
c++visual-studiodoubly-linked-listdeep-copy
Jay
Jay

Reputation: 41

Confused on how to do a deep copy of a doubly Linked List?

I have been trying to implement a deep copy of a doubly linked list, but I have been having trouble with it. I have to do it different several times, but I ended up getting an address error. I just need an explanation how to do it properly.

List.H

class List 
{
public:
    List();
    ~List();
    List(const List& c);
    List& operator= (const List& t);
private:
    List *Next;
    List *Prev;
    Node *Head;

List.cpp

List::~List()
{
    Node* move = Head;
    while (move!=NULL)
    {
        Node *temp = move->Next;
        delete move;
        move = temp;
    }
}

List::List(const List& c)
{
    name = c.name;
    if (c.Head == NULL) {
        Head = NULL;
    }
    else {
        Head = new Node(*c.Head);
        Node* Current = Head;
        Node* ObjHead = c.Head;
        Node* CurrentObj = ObjHead;

        while (Current->Next!=NULL) {
            Current->Next = new Node (CurrentObj->Next->condiments);
        }
    }
}

Upvotes: 0

Views: 2143

Answers (2)

WhozCraig
WhozCraig

Reputation: 66234

Copying linked lists is about three things:

  1. Traversing the list being copied.
  2. Making copies of new nodes from the originals.
  3. For each new node from (2), tail-link it to the linked list.

The first of these is trivial, the second is fairly basic, but the third is the one that often tosses people for a loop. For your copy-ctor, one way to do it employs a pointer-to-pointer. This allows us to address each pointer in our linked list by their own addresses.

List::List(const List& c)
    : Head(nullptr)
    , name(c.name)
{
    Node *prev = nullptr;
    Node **pp = &Head;

    for (const Node *p = c.Head; p; p = p->Next)
    {
        // make a new node, storing its address at the
        // pointer obtained by dereference of `pp`. the
        // first iteration that will be the Head member.
        *pp = new Node(*p);
        (*pp)->Prev = prev;
        prev = *pp;

        // now just advance `pp` to point to the `Next`
        // member of the node we just hung on the list.
        pp = &(*pp)->Next; 
    }
    *pp = nullptr; // terminate the list.
}

This assumes you're Node class supports copy-construction (it had better). but that's all it takes. From that, you can use the copy/swap idiom to manufacture your copy-assignment operator and have a basic rule-of-three compliance list class.

Upvotes: 2

srt1104
srt1104

Reputation: 959

You can use a dummy head to begin with. Once the deep copying is done, you can set head to the next of the dummy head and delete the dummy head. You also won't have to check for if (c.Head == NULL) this way.

    Node *ptr1, *ptr2;
    head = ptr1 = new Node();
    ptr2 = c.head;
    while (ptr2)
    {
        ptr1->next = new Node(*ptr2);
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    Node *temp = head;
    head = head->next;
    delete temp;

Upvotes: 0

Related Questions