News for hackers. Stuff that matters.
Re:Show HN: Array with Constant Time Access and Fast Inserti... by tempay on Wednesday September 04, 2019 @03:05AM (#20874677)
You have to move the data to make space for the new value (or fill the space for deletion). Imagine you have an array of 5 numbers:

    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.

There are no comments on this comment yet.