Thread: LinkedList operator= and deep copy

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    96

    LinkedList operator= and deep copy

    Ok so I wrote my own (doubly) linked list class.
    I want to implement the copy ctor, and operator=.

    The list we are copying to may not be empty when operator= is called, so what do we do?
    Do we clear the list?
    Or do we use the nodes we already have, and copy the data into those node's?

    The problem I see with clearing the list, is that clearing is a linear O(n), operation, and so is the copying (cloning if you will). So that would make operator= quadratic (right?).
    Quadratic is unacceptable. Copying should be linear.

    So how does the standard library do this?
    And more importantly what should I do to implement operator=?

    Copy ctor isn't a big deal because the list we are copying to is empty.


    Here is some code to demonstrate what I mean:

    Code:
        LinkedList<int> srcList;
        
        srcList.Append(1);
        srcList.Append(2);
        srcList.Append(3);
    
        // create dest list
    
        LinkedList<int> destList;
    
        // add values to dest list
    
        destList.Append(4);
        destList.Append(5);
        
        // dest list isn't empty.....
    
        destList = srcList;

  2. #2
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by sethjackson View Post
    The problem I see with clearing the list, is that clearing is a linear O(n), operation, and so is the copying (cloning if you will). So that would make operator= quadratic (right?).
    Quadratic is unacceptable. Copying should be linear.
    If you have 2 operations that are O(n), wouldn't that be: 2O(n)? I'm not a math genius, but that doesn't look quadratic to me.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you want to be clever, you may copy the data over to the existing nodes of Destination and append or remove remaining nodes as needed. Altogether you'll only traverse each array once.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by cpjust View Post
    If you have 2 operations that are O(n), wouldn't that be: 2O(n)? I'm not a math genius, but that doesn't look quadratic to me.
    http://www.perlmonks.org/?node_id=227909

    O(n * n) = O(n2) which would be quadratic.

    I don't know the superscript tag for this board LOL.

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by anon View Post
    If you want to be clever, you may copy the data over to the existing nodes of Destination and append or remove remaining nodes as needed. Altogether you'll only traverse each array once.
    Heh I thought of that actually.
    Since we traverse each list at the same time I should get linear complexity right?

    The question is does the old data get destroyed? I think so... ?

  6. #6
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by sethjackson View Post
    http://www.perlmonks.org/?node_id=227909

    O(n * n) = O(n2) which would be quadratic.

    I don't know the superscript tag for this board LOL.
    But why would you square n? You're only doing each operation once.

    From what I saw on that site:
    Remove all nodes = O(n)
    Add new nodes = O(m)
    O(n) + O(m) = O(n + m)

  7. #7
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by cpjust View Post
    But why would you square n? You're only doing each operation once.

    From what I saw on that site:
    Remove all nodes = O(n)
    Add new nodes = O(m)
    O(n) + O(m) = O(n + m)
    Clearing is a linear operation. Linear = O(n)
    Cloning the nodes is also Linear because you have to iterate through each node of the other list.

    O(N2) says that the algorithm's performance is proportional to the square of the data set size. This happens when the algorithm processes each element of a set, and that processing requires another pass through the set. The infamous Bubble Sort is O(N2).

  8. #8
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by sethjackson View Post
    Clearing is a linear operation. Linear = O(n)
    Cloning the nodes is also Linear because you have to iterate through each node of the other list.
    That would be true if you add all elements of List B to List A for each element in List A that you remove.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Quote Originally Posted by sethjackson View Post
    Heh I thought of that actually.
    Since we traverse each list at the same time I should get linear complexity right?

    The question is does the old data get destroyed? I think so... ?
    Yes, old data gets destroyed because you copy new data over it.

    And I think that is a problem. If you encounter an exception during the list assignment (for example when allocating additional nodes, or when a copy constructor throws), you'll have lost the old data and failed to copy the new data. Your list would become useless if an exception is thrown.

    If you want better exception safety, you might probably be better off using a copy constructor and fast swap:
    Code:
    void swap(Type& a, Type& b) {
        //implement fast swap
    }
    
    Type& Type::operator= (const Type& right) {
        Type temp(right);
        swap(temp, *this);
        return *this;
    }
    Copy constructor and destructor of temp would both be linear in your case, swap should have O(1) complexity.

    You can see a long discussion here.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by anon View Post
    Yes, old data gets destroyed because you copy new data over it.

    And I think that is a problem. If you encounter an exception during the list assignment (for example when allocating additional nodes, or when a copy constructor throws), you'll have lost the old data and failed to copy the new data. Your list would become useless if an exception is thrown.
    Hmm I hadn't thought of that.
    Although copy-ctor could throw if new nodes couldn't be allocated.

    I think I've read about implementing operator= in terms of copy-ctor/swap in a book I have.
    I'll have to read on it.

    Quote Originally Posted by anon View Post
    Copy constructor and destructor of temp would both be linear in your case, swap should have O(1) complexity.
    So that would be quadratic?
    Because copy-ctor is linear, and destructor is linear because you have to clear the nodes?


    BTW thanks for the link.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Linear plus linear equals linear, not quadratic.

  12. #12
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by Daved View Post
    Linear plus linear equals linear.
    Ok. Thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. template and friend class
    By black_spot1984 in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2008, 05:50 PM
  2. Deep and Shallow Copy
    By peckitt99 in forum C++ Programming
    Replies: 2
    Last Post: 05-13-2007, 07:28 AM
  3. In deep copy
    By Belzebuts in forum C Programming
    Replies: 1
    Last Post: 02-05-2006, 11:58 AM
  4. dynamic memory alloccation & returning objects
    By haditya in forum C++ Programming
    Replies: 8
    Last Post: 04-21-2005, 11:55 PM
  5. Copy constructors and operator=()
    By filler_bunny in forum C++ Programming
    Replies: 13
    Last Post: 08-25-2003, 07:43 AM