1. ## 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

// add values to dest list

destList.Append(4);
destList.Append(5);

// dest list isn't empty.....

destList = srcList;```

2. Originally Posted by sethjackson
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. 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.

4. Originally Posted by cpjust
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. Originally Posted by anon
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. Originally Posted by sethjackson
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)
O(n) + O(m) = O(n + m)

7. Originally Posted by cpjust
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)
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. Originally Posted by sethjackson
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. Originally Posted by sethjackson
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.

10. Originally Posted by anon
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.

Originally Posted by anon
Copy constructor and destructor of temp would both be linear in your case, swap should have O(1) complexity.