开发者

Is this a deep copy and properly implemented = operator for a C++ Linked List?

I'm running into some bugs now that I'm trying to use the doubly linked list class that I made. My implementation of the = operator looks like the following:

template <typename T>
Dlist<T>& Dlist<T>::operator=(const Dlist &l)
{
    copyAll(l);
    return *this;
}

template <typename T>
void Dlist<T>::copyAll(const Dlist &l)
{
    node *copyList = new node;
    copyList = l.first;
    while(copyList){
        insertFront(copyList.first->o);
        copyList = copyList->next;
    }
    delete copyList;
}

Note that o is a pointer for the data in a node in the List.

My intent is for copyAll to be a true deep copy. Is this not the case? Is there something wrong with my class method definitions here? I'm new to linked lists so help is much appreciated!

EDIT: specifically the issue I'm having is whe开发者_JAVA技巧n I make a List and fill it, then make a new list and set it equal to the first, anytime I do something to the second list, it also alters the first list.

EDIT2: Here's the class itself. I'm not allowed to add any other member functions:

template <typename T>
class Dlist {
 public:

    // Operational methods

    bool isEmpty();
    // EFFECTS: returns true if list is empty, false otherwise

    void insertFront(T *o);
    // MODIFIES this
    // EFFECTS inserts o at the front of the list

    void insertBack(T *o);
    // MODIFIES this
    // EFFECTS inserts o at the back of the list

    T *removeFront();
    // MODIFIES this
    // EFFECTS removes and returns first object from non-empty list
    //         throws an instance of emptyList if empty

    T *removeBack();
    // MODIFIES this
    // EFFECTS removes and returns last object from non-empty list
    //         throws an instance of emptyList if empty

    // Maintenance methods
    Dlist();                                   // ctor
    Dlist(const Dlist &l);                     // copy ctor
    Dlist &operator=(const Dlist &l);          // assignment
    ~Dlist();                                  // dtor

 private:
    // A private type
    struct node {
    node   *next;
    node   *prev;
    T      *o;
    };

    node   *first; // The pointer to the 1st node (NULL if none)
    node   *last;  // The pointer to the 2nd node (NULL if none)


    void makeEmpty();
    // EFFECT: called by constructors/operator= to establish empty
    // list invariant

    void removeAll();
    // EFFECT: called by destructor/operator= to remove and destroy
    // all list elements

    void copyAll(const Dlist &l);
    // EFFECT: called by copy constructor/operator= to copy elements
    // from a source instance l to this instance
 };


Basically the difference between a shallow copy and a deep copy is whether you copy just the pointer itself or copy all the data the pointer points to. Don't forget to also invoke the base class and copy all of its members as well to avoid partial initialization if your object is derived!

Generally you want to provide a copy constructor for this purpose. The assignment operator is similar to copying but assignment is actually done on an already constructed and probably already initialized object.

As to whether you are doing it right well that depends on the implementation details of your class most of which you have not shown here. What you have shown looks incomplete.

You may want to consider using std::list until you are more familiar with C++ and data structures before attempting to implement your own version as well. It's rare to really need to reinvent the wheel nowadays other than for curiosity sake or more complete learning of underlying concepts.


You say "some bugs". It's helpful to mention what those are when asking a question.

That said, look at the first two lines of copyAll. The first line allocates a new node, the second overwrites that pointer, losing it forever. Maybe you meant copyList.first = l.first. You'll also need to construct new nodes inside the while loop.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜