0

I'm having trouble figuring out how to implement a copy constructor for doubly linked lists. The code I have so far is incorrect, I believe, because I lose track of the header node, but I'm not sure how to rectify this. Any help would be much appreciated!

DoublyLinkedList.h

#include <cstdlib>
#include <iostream>
using namespace std;
class DoublyLinkedList; // class declaration

// list node
class DListNode {
private: 
    int obj;
    DListNode *prev, *next;
    friend class DoublyLinkedList;
public:
    DListNode(int e = 0, DListNode *p = NULL, DListNode *n = NULL)
        : obj(e), prev(p), next(n) {}

    int getElem() const { return obj; }
    DListNode * getNext() const { return next; }
    DListNode * getPrev() const { return prev; }
};

// doubly linked list
class DoublyLinkedList {
protected: 
    DListNode header, trailer;
public:
    DoublyLinkedList() : header(0), trailer(0) // constructor
        { header.next = &trailer; trailer.prev = &header; }
    DoublyLinkedList(const DoublyLinkedList& dll); // copy constructor
    ~DoublyLinkedList(); // destructor
    DoublyLinkedList& operator=(const DoublyLinkedList& dll); // assignment operator


    DListNode *getFirst() const { return header.next; } // return the pointer to the first node
    const DListNode *getAfterLast() const { return &trailer; }  // return the pointer to the trailer
    bool isEmpty() const { return header.next == &trailer; } // return if the list is empty
    int first() const; // return the first object
    int last() const; // return the last object

    void insertFirst(int newobj); // insert to the first of the list
    int removeFirst(); // remove the first node
    void insertLast(int newobj); // insert to the last of the list
    int removeLast(); // remove the last node

};

// output operator
ostream& operator<<(ostream& out, const DoublyLinkedList& dll);

DoublyLinkedList.cpp - Copy Constructor

// copy constructor
DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList& dll)
{
  // Initialize the list
  header = 0;
  trailer = 0;
  header.next = &trailer; 
  trailer.prev = &header;

  // Copy from dll
    DListNode* head = new DListNode;
    head->prev = dll.header.prev;
    head->obj = dll.header.obj;
    head->next = dll.header.next;

    DListNode* tail = new DListNode;
    tail->prev = dll.trailer.prev;
    tail->obj = dll.trailer.obj;
    tail->next = dll.trailer.next;

    DListNode* curr = new DListNode;
    curr->prev = head;

    while(curr != tail) {

        DListNode* n = new DListNode;
        curr->next = n;
        n = curr->prev->next;
        curr = curr->next;
    }

    curr = tail;
}
1
  • Also, that constructor always does a new DListNode at least three times. But if dll is empty, it should in fact use dynamic storage zero times. Commented Feb 26, 2014 at 2:23

1 Answer 1

1

Rather than writing specific code to copy the list in dll using the internal structure, why not just loop through the list in dll as you normally would (using dll.getFirst() and dll.getAfterLast()) and just call insertLast with each value.

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

3 Comments

Wouldn't that just give me a shallow copy, not a deep copy?
You would be copying every value from one list to the other, so it would be a deep copy.
@user2555471 - Wouldn't that just give me a shallow copy...? Why would you say that? Forget about copy constructor for a moment, what if I wrote a standalone function that just starts out with an empty list, and then in a loop copies each item from a populated list to the empty list by calling insertLast()? Are you saying you had doubts it will create my new list correctly? Then if you had these doubts, then you better fix your insertLast() function, as you don't trust it to do its job correctly.

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.