big O notation question

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.

Quote:

---

Originally Posted by EVOEx

Actually, to remove an item from a single linked list, you will have to find the *previous* item as well, to update it's 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) ;)

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).

Quote:

---

Originally Posted by EVOEx

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.

---

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.

Quote:

---

Originally Posted by iMalc

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.

---

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.

Oh certainly. I would never consider using such a technique, it was just an FYI I suppose.

Quote:

---

Originally Posted by l2u

Been wondering what is the time complexity of algorithm if we erase all elements in a linked list?

---

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).