Adding a name to a list is simple until the list must stay in order. An insert method adds an element to a container while preserving that container’s rules. The same operation can therefore require very different work in different data structures. section 3.3 section 7.10
At the interface level, insert describes what the caller can do, not how the element is stored. A bag’s insert(x) adds one element without promising insertion order; duplicates are allowed. A priority queue’s insert adds an element that will later compete to be returned according to priority. A dictionary’s insert adds a value associated with a key. section 7.10 section 10.3 section 12.3
Implementation depends on what must remain true after insertion:
- A dynamic array appends at its current size. If its underlying array is full, it first creates one with twice the capacity and copies the existing elements. That resize takes O(n) time and extra space; insertion without a resize takes constant time. section 5.16
- A sorted array must place the value without breaking sorted order. Its entries should be changed through methods such as insert rather than by direct assignment. section 3.3
- A sorted linked list used as a priority queue scans for the right position. A heap offers a different tradeoff: both insert and top take O(log(n)) time, rather than making one of those operations linear. section 10.5 section 10.12
- A binary search tree follows the path where the value belongs, then attaches a new node. With this duplicate-handling rule, an equal value takes the left branch. Insertion takes O(h) time, where h is the tree’s height. section 11.10
Finding a tree position
To insert another 6 when the root holds 6, go left and continue until there is a place for a new node. To insert a new largest value, 11, follow the path to the far right. In both cases, insertion resembles a search that ends at a missing child. section 11.10
def insert(self, value):
if self._size >= self._capacity:
self._double_size()
self._array[self._size] = value #1
self._size += 1
#1 When it gets here, we are sure that self._size < len(self._array).
The Python dynamic-array implementation checks capacity, grows the underlying array if needed, writes the new value at the current size, and increments that size. section 5.16
