As someone who doesn't know much about this level of CS, can someone explain to me why inserting/deleting an element in a linear array is expensive?
1 2 3 4 5
Deleting number three requires you to do three operations: 1 2 4 4 5 # Move 4th element to the 3rd place
1 2 4 5 5 # Move 5th element to the 4th place
1 2 4 5 # Clear the 5th value
Similarly inserting a second three requires 3 operations 1 2 3 4 5 5 # Move 5th element to the 6th place
1 2 3 4 4 5 # Move 4th element to the 5th place
1 2 3 3 4 5 # Insert the second 3
This means as the array gets bigger you have to do more work to insert/delete values. If your arrays are large and need to do this often, your software will be very slow and you should use a more suitable data structure with different trade offs.