4 ms·

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?

tempay 7y ago
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.
rosstex 7y ago
Inserting an element at a position in the array means shifting the element at that position and every subsequent element to the right by 1. Naively, this takes linear time.
kbsletten 7y ago
Basically a linear array is packed tightly, so trying to put something in the middle, well first you have to move what's already there. Because it's packed tight, you end up having to move everything to the right one space from the right back to where you're creating a hole. Then you can put what you want in the middle. Sometimes you get lucky and you're adding something far to the right and don't need to shuffle many items first, but sometimes you need to put it on the very left and reshuffle the whole thing. You'll never have to shuffle anything twice, but is possible to end up shuffling everything once so we say it's O(N) which means never takes a crazy multiple of the number of items.
kmbriedis 7y ago
Are you a software developer? No judging, just curious
- jwandborg 7y ago
  I made useful stuff in high level languages for years before I dug deeper to discover that it was sometimes useful to worry about the characteristics of my sequences of things.
- jason0597 7y ago
  Turns out it was a misunderstanding on my part. I interpreted the word "insert" as "replace" and I was wondering why replacing an element in a linear array would be an expensive operation. And no, I am not a software developer, I'm a chemical engineering student. Though I've done a bit of work on Nintendo 3DS hacking by writing tools for various exploits, and also bit of STM32 tinkering (https://github.com/jason0597 https://github.com/jason0597)

tempay 7y ago

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.

rosstex 7y ago

Inserting an element at a position in the array means shifting the element at that position and every subsequent element to the right by 1. Naively, this takes linear time.

kbsletten 7y ago

Basically a linear array is packed tightly, so trying to put something in the middle, well first you have to move what's already there. Because it's packed tight, you end up having to move everything to the right one space from the right back to where you're creating a hole. Then you can put what you want in the middle. Sometimes you get lucky and you're adding something far to the right and don't need to shuffle many items first, but sometimes you need to put it on the very left and reshuffle the whole thing. You'll never have to shuffle anything twice, but is possible to end up shuffling everything once so we say it's O(N) which means never takes a crazy multiple of the number of items.

kmbriedis 7y ago

Are you a software developer? No judging, just curious

jwandborg 7y ago
I made useful stuff in high level languages for years before I dug deeper to discover that it was sometimes useful to worry about the characteristics of my sequences of things.
jason0597 7y ago
Turns out it was a misunderstanding on my part. I interpreted the word "insert" as "replace" and I was wondering why replacing an element in a linear array would be an expensive operation. And no, I am not a software developer, I'm a chemical engineering student. Though I've done a bit of work on Nintendo 3DS hacking by writing tools for various exploits, and also bit of STM32 tinkering (https://github.com/jason0597 https://github.com/jason0597)