The rule a structure promises to keep

Most structures are a layout plus a rule, and maintaining the rule is where the cost lives.

An alphabetised bookshelf is only useful while it is actually alphabetised. If you shove one book in anywhere convenient, you have not saved yourself work. You have quietly broken the shelf, and the next time you go looking for something you may walk right past it.

That is worth taking seriously, because most data structures are not just a layout. They are a layout plus a rule that is promised to be true at all times. The word for such a rule is an invariant: something that stays true before and after every operation, whatever you do to the structure.

A rule, and the price of keeping it

One word of warning first. The last lesson gave the name linked list to the scattered arrangement, and the word list on its own is used far more loosely than that, here and everywhere else, to mean any sequence of items in some order, whatever is holding them. Where the arrangement underneath actually matters, this course says packed run or scattered chain instead, so there is never any doubt. The example below is a packed run.

Take a small packed run kept in increasing order: 2, 5, 9, 14. The invariant is every item is smaller than the one after it. Now insert 7.

You cannot just put 7 on the end, because 2, 5, 9, 14, 7 breaks the rule. You have to find where 7 belongs, which is between 5 and 9, and put it there. This run was asked for with room for five numbers and only four are in it, so there is one free space on the end. Making room for the 7 means shifting 14 along first and then 9, working from the back as we did in the last lesson, so that nothing gets written over. The result is 2, 5, 7, 9, 14 and the rule holds again.

before:  [ 2][ 5][ 9][14][  ]
                    \   \
                     \   \
                      \   \      14 moves along first,
                       v   v        then 9
after:   [ 2][ 5][ 7][ 9][14]

Here is the point. That shifting is not waste and it is not a flaw in the design. It is the fee for the promise. Because the run is always sorted, you can search it by repeatedly throwing away half of what is left rather than checking every item, which is enormously faster. That halving trick is the subject of a lesson three along from here, where you will see it worked through on a sorted run much like this one, and it comes back in full detail in the section on arrays. The insertion cost buys the search saving.

Rules you will meet later

You do not need to understand these yet. They are here so that when they arrive, you recognise the shape of what is being claimed:

• A binary search tree promises that everything to the left of an item is smaller than it, and everything to the right is larger.
• A heap promises that every item is smaller than the items hanging below it, so the smallest item is always the one on top.
• A hash table promises that an item lives in the slot that a calculation on its name points to, so you can compute where to look rather than searching.