Hello,
Been wondering what is the time complexity of algorithm if we erase all elements in a linked list?
Also what is the big O notation (complexity) difference betwen erasing element in a single and doubly linked list?
How can we calculate that?
Thanks in advance!
The complexity of the algorithm depends on what algorithm you use.
There should not be a complexity difference between erasing element in a single and a doubly linked list, since erasing an element in a singly-linked list is two operations, which is O(1), and erasing an element in a doubly-linked list is three operations, which is O(1). (I'm not counting "finding the element to be deleted" as part of this, but that's identical in both cases anyway.)
Actually, to remove an item from a single linked list, you will have to find the *previous* item as well, to update its pointer. The complexity of this is O(n). So deleting something is O(n) in a single linked list, and O(1) in a doubly linked list.
Clearly, erasing the next node in a singly linked list is in O(1)Originally Posted by EVOEx
Of course, once we consider "finding the element to be deleted", in all cases erasing an arbitrary node from a linked list is in O(n).
Look up a C++ Reference and learn How To Ask Questions The Smart Way
Ah but there are ways around that to make it O(1) again. You simply copy the next item over the current item and then free the next item instead. You also keep a sentinel node after the end of the list to make it possible to delete the last node.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
But that comes with a different price. You lose iterator stability. One of the nice things about linked lists is that a pointer to an element stays valid no matter how you manipulate the list, as long as you don't erase that specific element.
But with your variant of erase, you also invalidate pointers to the next element.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Oh certainly. I would never consider using such a technique, it was just an FYI I suppose.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
The question requires a more specific context to answer. Do the elements of the list require destruction? If not, the complexity is O(1) because you can simply forget the list. This leaks memory, but you haven't specified whether that's acceptable or not. The point is, big-O discussions are usually theoretical, and theoretically, we could have a machine with infinite memory and so forgetting the list is an acceptable solution.
On a realistic system you are going to have to at least delete the memory of each node, which requires visiting each node, and this is O(n). If you have to destruct the nodes, again, you have to visit each of them and it is O(n).
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
