Imagine taking a name off a list. Finding it is only the first step: the remaining entries still need to fit together. A delete method removes an element, but the work depends on how the collection stores its elements. section 3.5 section 6.9
For arrays, decide whether the caller supplies a value or an index:
- In a sorted array, delete by value can call search to find the index, then shift every later element one position left and reduce the size. If search returns None, the Python implementation raises ValueError. section 3.5
- A dynamic array can find the value, perform the same shift, then shrink its backing array if it is no more than one-quarter full. With duplicates, this version removes the first occurrence. Search and shifting make its worst-case running time O(n), even without resizing. section 5.18
- If insertion order need not be preserved, a delete-by-index algorithm can avoid shifting the remaining elements. That changes the operation’s behavior, so choose it to suit the application. section 5.18
To remove an element from a sorted array, first we find its index, and then we shift all the elements to its right, overwriting the deleted element.
The sorted-array diagram shows why removing an element requires shifting the entries to its right. section 3.5
Linked lists do not shift elements. Deletion bypasses the target node by changing links. In a singly linked list, traversal must keep track of the previous node: finding the target alone does not give access to its predecessor. Deleting the head needs a head update; deleting the last node can require a tail update. A doubly linked list can use its predecessor links after searching, but search still makes deletion O(n). section 6.9 section 6.19
A binary search tree first finds the value and its parent. A leaf can be disconnected; a node with one child can be replaced by that child. A node with two children needs a separate replacement procedure, and deleting the root needs special handling. The complete method follows a path from the root toward a leaf and takes at most O(h) steps, where h is the tree height. section 11.11 section 11.12
A dictionary’s delete interface may instead accept a key, a full value, or a reference to that value. Check the interface before calling delete: what identifies an element is part of the method’s contract. section 12.3
