Ways of laying data out

Laying things out in a run is not the only way. You can also put them wherever there is room and give each one an arrow saying "next is over there". That is a list (a linked list).

What plays the part of the arrow is a pointer, a value recording where the next element is. So one element of a list holds two things: somewhere for the value and somewhere for the pointer to the next. The pointer of the last element carries the mark for "no next". One with only a single arrow is a singly linked list; one that also has an arrow back is a doubly linked list.

Here the decisive difference from an array appears. A list has no index, so if you want the third element you follow arrows three times from the front. Unlike an array, where a calculation gives the location, you cannot reach your destination without passing through everything before it. The hundredth means a hundred steps. So lookups are slower with a list.

This property comes up as "cannot be accessed randomly" or "elements are followed in order from the front, so the time needed is proportional to the number of elements". They all say the same thing.

Is an array better in every way, then? Not quite. The difference reverses when you insert in the middle.

An array is laid out with no gaps, so squeezing one into the middle means shifting everything after it along by one. Deleting is the same: the gap is closed by pulling the rest forward. The more elements there are, the heavier it gets.

A list shifts nothing. You just rewire a few arrows. Point the previous element "next" at the new one, and point the new one "next" at the rest. Done.

What is more, the effort is the same however many elements there are. In the middle of a thousand or in the middle of ten, it is a handful of arrows.

Let us tidy this up. Array if you mostly read, list if you mostly add and remove. That is all.

• Array … fast lookups / heavy insertion and deletion / space taken up front for the maximum count
• List … slow lookups / light insertion and deletion / extra space for the pointers

That last line is the other weakness of an array. Space for the maximum length is reserved in advance, so even with only three items in it the room stays set aside. Some of it goes unused.

The list side has its own pitfall. In a singly linked list, deleting the last element takes more than a pointer to the last element. The element one before, which becomes the last afterwards, has to be rewritten — and finding that one before means walking from the front.

From here we look at layouts with a rule about the order things go in and out. The first is the stack.

With a stack, the last thing in is the first thing out. Think of a pile of books: you put one on top and you take from the top. This property is LIFO (last in, first out).

There are only two operation names. Piling on is push and taking off is pop. push and pop on a JavaScript array behave exactly this way.

What to watch is that pop always takes from the very top. You cannot pull something out of the middle.

A stack comes into its own when you have to come back from wherever you went.

The classic case is calling functions. Say function A calls B and B calls C. When C ends you return to B, and when B ends you return to A. You return first to the place called last, which fits exactly: pile the return addresses and the working data on a stack and it comes out right.

The other is evaluating expressions. In something like (1 + 2) x 3, you put an intermediate result aside, finish another calculation, then take it back and use it. What you put down is needed in reverse order, so a stack suits this too.

Conversely, if you want them out in the order they went in, a stack cannot do it, and if you want to change or insert something in the middle, that is a job for an array or a list.

The second is the queue. Here the first thing in is the first thing out, exactly like a queue at a till. This property is FIFO (first in, first out).

Unlike a stack, the point is that the way in and the way out are different ends. In at the back, out at the front.

The operation names are enqueue for putting in (written ENQ or enq in the exam) and dequeue for taking out (DEQ or deq).

Around you, waiting turns for printing and queues of jobs to be handled in order are queues. The property of no cutting in is exactly what makes it fair.

The exam often puts a stack and a queue side by side and moves things back and forth. It can be solved from the text alone, so this is one not to drop.

There is one knack: write the contents on paper and rewrite them after every operation. Do it in your head and you will mix something up.

When you write, keeping the orientation fixed matters. Decide that for the stack the right-hand end is the top (the next one out) and for the queue the left-hand end is the front (the next one out), and never change it.

Also, do not miss where the value you took out is going. Something nested like enq(pop()) is two moves: first pull from the stack, then put that value into the queue.

There are also layouts that branch rather than run in a line. Those are trees.

Learn four words.

• Node … each individual point. Data goes in it
• Root … the topmost node, which has no parent
• Leaf … a node with no children, the end of the road
• Edge … the line joining node to node

The up-and-down relation is called parent and child. The number of levels counted from the root is the depth. Counting the root as depth 0 is usual, and the number of levels down to the deepest leaf is the height of the tree.

A tree suits hierarchical relationships. Folders inside folders form a tree too.

A tree that limits children to at most two is a binary tree. With only a left child and a right child, its shape is easy to read and easy to work with.

A binary tree that is filled in with no gaps, from the top and from the left, is a complete binary tree. With no holes in the middle, its strength is that it drops straight into an array.

Once it is in an array, the parent-child relation comes out of a calculation. Numbering from 1, the children of index i are 2i and 2i+1, and the parent is i divided by two, rounded down. So a tree can be represented with no pointers at all.

By the way, the node-parent relation can also be expressed by putting the parent number into an array. At the root position you put 0 as the mark for "no parent". In this form, a node that nothing points at as a parent is a leaf.

Add a rule about where values go to a binary tree and you get a shape that is easy to search.

A binary search tree is one where, at every node, the left child and all its descendants are smaller than it, and the right child and all its descendants are larger. So you compare against the root and go down — "smaller, go left; larger, go right" — heading straight for the value you want.

What matters is that the condition holds for the whole subtree, not just your own children. If the level right below is in order but it breaks at the grandchildren, it is not a binary search tree.

The other shape is the heap, a tree that fixes only the parent-child comparison: "the parent is greater than (or less than) the child" for every parent and child. The point is that no order is fixed between siblings. So the root always holds the largest (or smallest) value, which suits wanting to take out the biggest one over and over.

Last is the layout that settles the location by calculation.

A hash table puts the key behind the value through a hash function and uses the number that comes out as the location (the index) directly. A common one is "the remainder of the key divided by some number".

The good part is that the location is known without walking and without searching. It is only a pass through a function, so however big the table gets the effort is the same. That is the difference from an approach whose cost is proportional to the size of the table.

There is one problem, though. Different keys can produce the same location. That is a collision, and keys landing on the same location are synonyms.

Collisions are not something you stop happening; they are something you prepare for as inevitable. There are far more possible keys than there are values the hash function can produce, so there is no avoiding it. You provide an escape: shift to the next free location, or hang a list off that location.