33

Can you think of any specific reason why deletion is usually significantly harder to implement than insertion for many (most?) data structures?

Quick example: linked lists. Insertion is trivial, but deletion has a few special cases that make it significantly harder. Self-balancing binary search trees such as AVL and Red-black are classic examples of painful delete implementation.

I would like to say it has to do with the way most people think: it is easier for us to define things constructively, which leads nicely to easy insertions.

Improve this question
13
  • 4
    What about pop, extract-min?
    – coredump
    Oct 27, 2015 at 17:27
  • 5
    "Harder to implement" is more a matter of psychology (cognition and the strengths & weaknesses of the human mind) than of programming (properties of data structures & algorithms).
    – outis
    Oct 27, 2015 at 17:32
  • 1
    As I think coredump alluded to, stacks should be at least as easy to delete as add (for an array-backed stack, popping is just a pointer decrement [1] whereas pushing could require a whole array copy if you hit the maxsize of the array). Also there are some use cases where it is assumed that insertions will be frequent and deletions less so but it would be a very magical data structure where the number of deletions exceeds insertions. [1] You should probably also null the now invisible reference to the popped object to avoid memory leaks, which I remember because Liskov's textbook didn't
    – Foon
    Oct 27, 2015 at 20:21
  • 44
    "Waiter, could you please add more mayo to this sandwich?" "Sure, no problem, sir." "Could you also remove all of the mustard?" "Uh......"
    – cobaltduck
    Oct 27, 2015 at 20:38
  • 3
    Why is subtraction more complicated than addition? Division (or prime factorization) more complicated than multiplication? Roots more complicated than exponentiation?
    – mu is too short
    Oct 28, 2015 at 3:23

5 Answers 5

Reset to default
68

It's more than just a state of mind; there are physical (i.e. digital) reasons why deletion is harder.

When you delete, you leave a hole where something used to be. The technical term for the resulting entropy is "fragmentation." In a linked list, this requires you to "patch around" the removed node and deallocate the memory it is using. In binary trees, it causes unbalancing of the tree. In memory systems, it causes memory to go unused for awhile if newly-allocated blocks are larger than the blocks left behind by deletion.

In short, insertion is easier because you get to choose where you are going to insert. Deletion is harder because you can't predict in advance which item is going to get deleted.

Improve this answer
4
  • 3
    Fragmentation isn't an issue where pointers & indirection come into play, for either the structure in-memory or in diagrams. In-memory, it doesn't matter where individual nodes exist due to the indirection. For lists, deleting an internal node (which is where you'd have a hole in the diagram) involves slightly fewer operations than insertion (1 pointer assignment and 1 free vs. 1 allocation and 2 pointer assignments). For trees, inserting a node can unbalance a tree just as much as deletion. It's the edge cases that cause the difficulties brito refers to, where fragmentation doesn't matter.
    – outis
    Oct 27, 2015 at 23:15
  • 12
    I disagree that insertions and deletions differ in predictability. "Patching around" a list node is exactly what happens in reverse if the same node is to be inserted instead. There is no uncertainty in either direction at any point, and in any container without intrinsic structure to its elements (e.g. a balanced binary tree, an array with a strict relationship between element offsets) there is no "hole" at all. Therefore, I'm afraid I don't know what you are talking about here.
    – sqykly
    Oct 27, 2015 at 23:19
  • 2
    Very interesting, but I'd say arguments are missed. You can organize data structures around simple/fast deletion with no problem. It's just less common, most probably less useful as well.
    – luk32
    Oct 28, 2015 at 0:21
  • @sqykly I think list was bad choice example because middle insertion and middle relation are equally difficult. One case allocates memory where the other reallocated. One opens a hole where the other seals a hole. So not all cases is delete more complex than add.
    – ydobonebi
    Oct 30, 2015 at 14:56
35

Why does it tend to be harder to delete than to insert? Data structures are designed more with insertion in mind than deletion, and rightfully so.

Consider this - in order to delete something from a data structure, it has to be there in the first place. So you need to add it first, meaning that at most you have as many deletions as you have insertions. If you optimize a data structure for insertion, you're guaranteed to get at least as much benefit as if it had been optimized for deletion.

Additionally, what use is there in sequentially deleting each element? Why not just call some function that clears it out all at once (possibly by just creating a new one)? Also, data structures are most useful when they actually contain something. So the case of having as many deletions as insertions is, in practice, not going to be very common.

When you optimize something, you want to optimize the things that it does the most and that take the most time. In normal usage, deletion of elements of a data structure happens less frequently than insertion.

Improve this answer
4
  • 4
    There is a one use-case I can imagine. A data structure which is prepared for initial insertion and then individual consumption. Of course it's a seldom case, and not very interesting algorithmically, because as you said, such an operation cannot dominate insertion asymptotically. Maybe there is some hope in fact that batch insertion can have amortized cost pretty good and be fast and simple for deletion, so it would have complicated yet practical batch insertions and simple and fast individual deletions. Certainly a very uncommon practical need.
    – luk32
    Oct 28, 2015 at 0:39
  • 1
    Ummm, I think an example could be a reverse ordered vector. You can add a batch k of elements pretty fast: reverse sort input and merge with existing vector - O(k log k + n). Then you have a structure with fairly complicated insertion but consuming top u elements is trivial and fast. Just take last u and move the end of vector. Though, if anyone ever needs such a thing, I'll be damned. I hope this at least strengthens your argument.
    – luk32
    Oct 28, 2015 at 0:51
  • Shouldn't you want to optimize for the average usage pattern rather than what you do the most of?
    – Shiv
    Oct 28, 2015 at 2:36
  • A simple FIFO work queue will typically try to be empty most of the time. A well-designed queue will be well optimized (i.e. O(1)) for both insertions and deletions (and a very good one will also support fast concurrent operations, but that's a different issue).
    – Kevin
    Oct 30, 2015 at 0:13
6

It is not harder.

With doubly linked lists, when you insert, you will be allocating memory, and then you will be linking with either the head or the previous node, and with either the tail or the next node. When you delete, you will be unlinking from exactly the same, and then freeing memory. All these operations are symmetric.

This assumes that in both cases you have the node to insert/delete. (And in the case of insertion, that you also have the node to insert before, so in a way, insertion could be thought of as slightly more complicated.) If you are trying to delete having not the node to delete, but the payload of the node, then of course you are going to have to first search the list for the payload, but that's not a shortcoming of deletion, is it?

With balanced trees, the same applies: a tree generally needs balancing immediately after an insertion and also immediately after a deletion. It is a good idea to try and have only one balancing routine, and apply it after each operation, regardless of whether it was an insertion or a deletion. If you are trying to implement an insertion which always leaves the tree balanced, and also a deletion which always leaves the tree balanced, without having the two share the same balancing routine, you are unnecessarily complicating your life.

In short, there is no reason why one should be harder than the other, and if you are finding that it is, then it is in fact possible that you are a victim of the (very human) tendency of finding it more natural to think constructively than subtractively, meaning that you might be implementing deletion in a way which is more complicated than it needs to be. But that's a human issue. From a mathematical standpoint, there is no issue.

Improve this answer
4
  • 1
    I have to disagree. AVL deletion algorithm is more complex than insertion. For certain node deletions you may have to rebalance the entire tree, which is typically done recursively but can also be done non-recursively. You do not have to do this for insertion. I am not aware of algorithm advancements where such entire-tree-rebalancing can be avoided in all cases.
    – Dennis
    Oct 27, 2015 at 22:50
  • @Dennis: it could be that AVL trees follow the exception rather than the rule.
    – outis
    Oct 27, 2015 at 23:43
  • @outis IIRC, all balanced search trees have more complicated deletion routines (than insertion).
    – Raphael
    Oct 28, 2015 at 10:56
  • What about closed hashing hash tables? Insertion is (relatively) straightforward, deletion is at least harder to conceptualize since you have to fix up all the "the thing that was supposed to be at index X is currently at index Y and we have to go find it and put it back" issues.
    – Kevin
    Oct 30, 2015 at 0:16
3

In term of run-time, looking at the data structure operations time complexity comparison on Wikipedia, note the insert and delete operations have the same complexity. The delete operation profiled there is deletion by index, where you have a reference to the structure element to be deleted; insertion is by item. The longer running time for deletion in practice is because you usually have an item to delete and not its index, so you also need a find operation. Most data structures in the table don't require an additional find for an insert because the placement position isn't dependent on the item, or the position is determined implicitly during the insertion.

As for cognitive complexity, there's an answer in the question: edge cases. Deletion may have more of them than insertion (this has yet to be established in the general case). However, at least some of these edge cases can be avoided in certain designs (e.g. have a sentinel node in a linked list).

Improve this answer
4
  • 2
    "Most data structures don't require a find for an insert." -- such as? I'd make the opposite claim, in fact. (You "find" the insertion position, which is just as expensive as finding the same element again later.)
    – Raphael
    Oct 28, 2015 at 10:57
  • @Raphael: This answer should be read in the context of the linked table of operation complexities, which don't include the find operation as part of the delete. In answer to your question, I categorized structure by common name. Of arrays, lists, trees, hash tables, stacks, queues, heaps, and sets, trees and sets require a find for an insert; the others use an index unconnected to the item (for basic stacks, queues and heaps, only 1 index is exposed, and finding isn't supported) or calculate it from the item. Graphs could go either way, depending on how they're used.
    – outis
    Oct 29, 2015 at 21:53
  • ... Tries could be considered trees; however, if classified as their own structure, whether there's a "find" during insertion is more a matter of debate, so I don't include it. Note the data structure list doesn't take interface vs implementation into account. Also, how you count depends largely on how you categorize. I'll see if I can think of a more objective statement.
    – outis
    Oct 29, 2015 at 21:54
  • I'll admit I had the dictionary/set interface in mind (as common in CS). Anyway, that table is misleading and (iirc) even wrong in several places -- Wikipedia, the pit of CS misinformation. :/
    – Raphael
    Oct 29, 2015 at 23:56
0

On top of all mentioned issues there is data referential integrity involved. For most properly build data structure like databases in SQL, Oracle referential integrity is very important.
To make sure that you do not accidentally destroy it lot of different things invented.
For example cascade on delete which not just delete what ever you attempt to delete but also triggers cleanup of related data.
This clean up database from junk data as well as keep integrity of the data intact.
For example you have tables wit parents and kinds as related records in second table.
Where parent is main table. If you do not have reinforced referential integrity in place you can delete any records in any table and later on you would not know how to get full family information because you have data in child table and nothing in parent table.
That is why referential integrity check will not let you delete record from the parent table until records from child table cleaned up.
And that is why in most data sources it is more difficult to delete data.

Improve this answer
1
  • I think the question was asking about in-memory structures like linked lists, hash tables, etc. rather than databases, but referential integrity is a major issue even with in-memory structures.
    – supercat
    Oct 28, 2015 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.