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;