Think of adding a number to a row that must stay in order: you cannot always put it at the end. `insert` adds an element while preserving the collection’s rules. Those rules differ across sorted arrays, unsorted lists, heaps, and binary search trees (BSTs). section 3.4 section 6.7 section 10.17 section 11.10
Make room for 3
To insert 3 into the sorted array [1, 2, 4, 5, 6], move 6, 5, and 4 one place to the right, working backward. Then put 3 after 2. The result is [1, 2, 3, 4, 5, 6]. Working backward keeps the values you still need to move from being overwritten. section 3.4
Where should a new element go?
- In a dynamic array used for appending, put it after the last element. If capacity is full, first create an array with twice the capacity and copy the existing elements. That resize takes O(n) time and extra space; an insertion without resizing takes O(1) time. section 5.16
- In an unsorted singly linked list, adding at the back requires finding the tail, an O(n) traversal. Adding at the front instead makes the new node the head and links it to the old head. section 6.7
- In a heap, append the element, then bubble it toward the root while its priority exceeds its parent’s. For example, a new bug report with priority 9 may move upward more than once. section 10.17
- In a BST, follow comparisons as though searching for the new value. Attach a node at the first suitable missing child; this implementation sends duplicates left. Insertion takes O(h) time for tree height h. section 11.10
def insert(self, value):
if self._size >= self._max_size:
raise ValueError(f'The array is already full, maximum size: {self._max_size}')
for i in range(self._size, 0, -1):
if self._array[i-1] <= value: #1
self._array[i] = value
self._size += 1
return
else:
self._array[i] = self._array[i-1]
self._array[0] = value #2
self._size += 1
#1 Found the spot in the middle of the array
#2 If it gets here, the right spot is at the beginning of the array.
The sorted-array method shows the backward scan in Python: it shifts larger values right, writes the new value when it finds its place, and rejects insertion if the array is full. section 3.4
The practical tradeoff is how much work placement requires. Arrays may need to move entries or resize; a linked list can add at its head without searching for a position; heaps and BSTs follow their own ordering rules. section 3.4 section 5.16 section 6.7 section 10.17
