How is lazy deletion advantageous/disadvantageous to a binary tree or linked list?

Question

Recently, for a data structures class, I was asked the question of how a lazy deletion (that is, a deletion that first marks the items needed to be deleted, and then at some time later deletes all the marked items) would be advantageous/disadvantageous to an array, linked list, or binary tree. Here is what I have come up with:

• This would help arrays because you would save the time that is taken to shift the array every time an index is deleted although in algorithms that need to traverse the array, there could be inefficiencies.
• This would not help linked lists because you need to traverse O(n) to mark an item to be deleted anyways.
• I'm not entirely sure about binary trees, but if it were a linked list implementation of one I would imagine it is like the linked list?

Answer 1

I think it all depends on the circumstances and the requirements. In a general sense using this method where they are marked and then deleted later they all have a lot of similar pros and cons.

Similar pros: -When marked for deletion there is no shifting of the data structures, which makes deletion much faster. -You can insert on top of a deleted item, which means no shifting for inserts either, plus insertion can be done faster since it can write over the first delete instead of looking for the end of a list

Similar cons: -Waste of space for deleted item, since they are just sitting there -Have to transverse twice to delete an item, once to mark it and once again to delete it -Many marked items for deletion will pollute the data structure making searches take longer since deleted items have to be searched over.