Lists

Even though memory was a limited resource in computers, Newell and Simon chose to “waste” almost half of it by organizing the memory into lists where each register contained the address of its successor in a list. For example, consider the list structure

(6, (“Bob”, “Sally”), 8, (7, -1000)).

It would be represented in a segment of computer memory that looks like this:

This table depicts the actual memory registers. The ones with 00 at their left are to be interpreted as a list element where the two following numbers are addresses of other registers. The small sections on the left end of the register, tell us the type of the register, i.e. how bits in the register should be interpreted: number (10), characters (01), or list element (00). The lists are linked together by putting addresses in their rightmost part of the register, using 0 to mark the end of the list. The long middle part of list elements are addresses of list elements, which may be lists themselves. Note that two of the registers (107 and 114) are unused at the moment. They are linked in a free space list for later use.

Since the addresses are arbitrary, programmers think of this structure as the picture below where we use arrows to show how the addresses link up the structure.