The four things you ever do to a collection

Access, search, insert and delete: the questions to ask about every structure in this course.

Go back to the bookshelf for a moment. Whatever you do to it, you are doing one of a very small number of things. You take the book in a particular position. You hunt for a book by its title. You add a book. You remove a book. That is more or less the complete list, and the same four cover almost everything a program does to a collection of data.

• Access. Fetch the item in a position you already know. Give me the twelfth book.
• Search. Find an item by what it is, when you do not know where it is. Where is the book called Dracula?
• Insert. Add a new item, sometimes anywhere, sometimes in a particular place.
• Delete. Take an item out.

Access and search are not the same thing

This is the distinction people slide past, and it causes real confusion later, so it is worth pinning down now. Access starts from a position. Search starts from a value. They are completely different jobs.

If someone asks you for the twelfth book on the shelf, you do not need to know anything about books. You count twelve places along and take what is there. It does not matter whether the shelf holds twenty books or twenty thousand: twelfth is twelfth.

If someone asks you for the book called Dracula, and the shelf is in no particular order, you have no shortcut. You look at the first spine, then the second, and so on until you find it or run out of shelf. On a shelf of twenty books that is quick. On a shelf of twenty thousand it is your entire morning.

Position numbers start at zero

One small piece of convention before we go further. The position of an item in a collection is called its index, and programmers number them starting from 0, not 1. (The plural of index is indices, and the word turns up constantly, so it is worth meeting it here.) So a shelf of five books has positions 0, 1, 2, 3 and 4.

index:      0       1       2       3       4
         [  7  ] [  3  ] [ 11  ] [  5  ] [  2  ]

Here is what that picture looks like written down in a real program. The language used for code in this course is Python, and there are only three ideas in it that you need right now: a collection is written as a run of values between square brackets, asking for a position is done by putting the index in square brackets after the name of the collection, and print(...) shows whatever is inside the brackets on the screen. Anything after a # is a note to the reader and is ignored by the machine.

Index 5 gets you an error rather than a value, because a five-item collection has positions 0 to 4 and nothing at 5. Asking for a position that is not there is one of the commonest mistakes in the whole subject, and it is worth having made it once on purpose.

Numbering from zero looks like an act of deliberate awkwardness, and for now you can simply accept it as a convention. There is a genuine reason for it, and it will make complete sense in the next lesson, once you have seen how a computer finds things. The short version: an index is not a count of items, it is a distance from the start. The first item is zero places from the start.

One more worth naming: traversal

Traversal means visiting every item in a collection, one after another, doing something to each. Reading every spine on the shelf is a traversal. It is not really a fifth operation so much as a repeated one, but the word comes up constantly, especially when we get to trees and graphs, so it is useful to have it now.