Linked List adding node issue

[dhayden]

Why would calling the add() function inside the copy constructor cause it to run "O(n²) times"?

It basically means that the execution time is proportional to n² where n is the size of the list that you're copying. So if your list has 100 items, copying it takes approximately 10,000*k (where k is some constant). If your list has 1000 items, it takes 1,000,000*k, and so forth.

The reason is that your add() method goes through the entire list to find the end, where it inserts the new item. For the first item, it there's nothing to go through. For the second item, there is 1 item to pass. For the third there are 2, for the 4th, 3, etc.

So the time to insert N items proportional to 0+1+2+...+N-2 + N-1. Adding those numbers up it's N*(N-1)/2 = 1/2 (N²-N).

[JRManx]

Ah, so that refers to the time that it takes...? But if there's a faster way to do it, please, tell me. It's been a long time since I did any of this and the textbook I have doesn't give any other way.

[seeplus]

See dhayden's previous code (or mine just before that). Another way, as mentioned before, is to also have a tail pointer. If you just have a head pointer, then usually you would just add/remove at the head (ie a stack). If you have a head/tail pointer then you can easily add/remove at the head or add at the tail. This matters if you are using a list with thousands of elements. The overhead of traversing the list can be enormous. If you want to remove at the tail, then consider using a double-linked list.

[JRManx]

But either way you still have to traverse through the list nodes to get to wherever you want to add one, if you wanted to add one in the middle, say. Right? Or not...?

Anyway, thanks! Both of them worked, although I will say that yours, seeplus was a bit easier to understand regarding variable names. But they both worked great!

seeplus, dhayden, mbozzi– thanks guys!
max

[dhayden]

But either way you still have to traverse through the list nodes to get to wherever you want to add one.

Yes. it's one of the trade-offs of a linked list. It's extremely fast at adding/deleting when you already have a pointer to the place of insertion/deletion, but not very fast at getting to random spots.

One of the best things you can do when studying computer science and to learn the different types of data structures and which ones are good at which operations. 80% of writing fast code is just choosing the right data structure.