What it costs to add and remove an item

Insertion and deletion flip the comparison the other way, and the pointers charge rent in memory.

The last lesson stored the same five numbers, 7, 3, 11, 5 and 2, in two ways, and asked one question of each: how do you reach the item in a given position? The packed run won that comfortably. Now we ask the other two questions, adding an item and removing one, and the answer comes out the other way round.

packed:    [ 7][ 3][11][ 5][ 2][  ]
           at addresses 200, 204, 208, 212, 216 and 220

scattered: at 200: [  7  | next is at 880 ]
           at 880: [  3  | next is at 512 ]
           at 512: [ 11  | next is at 344 ]
           at 344: [  5  | next is at 700 ]
           at 700: [  2  | nothing after   ]

Putting a number in

So far the packed arrangement looks better. Ask about insertion and it flips. Suppose you want to put the number 9 between 3 and 11, so the sequence becomes 7, 3, 9, 11, 5, 2.

Remember that this run has room for six numbers and only five are in it, so there is one free space on the end, the one at address 220. That free space is where the shifting has to end up. What there is not is a gap in the middle: every space between the insertion point and the end already holds something. To make room you have to move 11, 5 and 2 each one place further along, working from the back so that nothing gets written over, and only then put 9 into the space that has opened up. Three numbers moved to insert one. If the run held a thousand numbers and you inserted near the front, you would move nearly a thousand.

before:  [ 7][ 3][11][ 5][ 2][  ]
                    \   \   \
                     \   \   \
                      \   \   \      each one moves
                       v   v   v     one place right
after:   [ 7][ 3][ 9][11][ 5][ 2]

In the scattered arrangement, nothing moves at all. Put the 9 in any free spot, say address 640. Set 9's pointer to 512, where 11 already lives. Then change 3's pointer from 512 to 640. Two pointers rewritten, and every other number sits exactly where it was. There is a catch, though, and it is the same one as before. To change 3's pointer you have to be standing at the 3, and the only way to reach the 3 is to start at 200 and follow the chain. The rewriting is two steps. The arriving is not.

before:   [7] --> [3] ------------> [11] --> [5] --> [2]

                        .--> [9] --.
after:    [7] --> [3] --'           '--> [11] --> [5] --> [2]

changed: 3's pointer now says 9, and 9's pointer says 11.

And deleting

Deletion is insertion run backwards, and it splits the same way. Go back to the packed run holding 7, 3, 11, 5 and 2, and take out the 3, which sits at index 1.

You cannot simply blank it and leave a hole. The whole reason the packed run is fast is that the item at index 3 sits exactly three items along from the start, and a hole in the middle would make that false for everything after it. So the hole has to be closed: 11 moves one place left into where 3 was, then 5 moves left, then 2 moves left. Three numbers moved to delete one, which is the same bill as the insertion.

before:  [ 7][ 3][11][ 5][ 2][  ]
                  /   /   /
                 /   /   /
                /   /   /            each one moves
               v   v   v             one place left
after:   [ 7][11][ 5][ 2][  ][  ]

In the scattered arrangement nothing moves again. The 3 lives at address 880 and the 11 lives at 512. To remove the 3 you change 7's pointer from 880 to 512, so the chain now runs straight past it, and then release the boxes at 880 for someone else to use.

before:   at 200: [  7  | next is at 880 ]
          at 880: [  3  | next is at 512 ]
          at 512: [ 11  | next is at 344 ]

after:    at 200: [  7  | next is at 512 ]
          at 512: [ 11  | next is at 344 ]

changed: 7's pointer now says 512, and the boxes at 880 are released.

That catch again. Rewriting that pointer is one step, but you had to be standing at the 7 to do it, because the 7 is the only thing holding the address you need to change. Getting there means following the chain from the beginning. The rewriting is cheap. The finding is not.

The pointers are not free

Everything so far has been counted in time, in moves and jumps. Memory is a cost too, and the scattered arrangement quietly spends a lot of it.

Count the boxes. In the packed run, five numbers at four boxes each is twenty boxes, and there is nothing else to store. In the scattered version each number also carries an address beside it, and an address is itself a number that has to be stored somewhere: four boxes on many machines, eight on a modern one. Taking four, each item now needs eight boxes rather than four, so five numbers cost forty boxes against the packed run's twenty. Twice the memory, for exactly the same five numbers, and three times if the addresses are eight boxes each.

That ratio is worst when the items are small, as ours are. If each item were a paragraph of text rather than one small number, the address beside it would be a rounding error. This is a large part of why the packed arrangement is the default choice for collections of small things.