Programs organize their data at increasing levels of granularity, and this section climbs through those levels. A single value has a type. Values gather into collections, which are found by position in an array or by key in a map. Then comes a change in viewpoint: stacks and queues are defined by how they behave and can be built on simpler structures, and a linked list shows that the same sequence of values can be stored in a very different way. At the top, classes bundle data with behavior into a type of your own. Two questions apply across all of these levels, namely where a name can be used and which structure fits a job, and the section closes with them. The notation here was introduced under "From Python to typed pseudocode," which has further examples and tables.

Single values and their types#

Everything starts with primitive types, the basic kinds of value. A bool is TRUE or FALSE, in capitals. An int is a whole number. A float is a decimal number treated as having infinite precision, so you can ignore rounding effects such as Python's 0.30000000000000004. A char is a single character in double quotes. A typed variable declares its type at its first assignment, as in int x = 5, and is reassigned without one, as in x = 6. Repeating the type redeclares the variable, leaving it out on the first assignment is an error, and a value of the wrong type should produce an error, so x = "seven" fails where Python would allow it. Types also govern arithmetic: int and float don't combine, so multiplying int total by float rate is a mismatch. Declared types help the reader as well, since a mismatch between an argument and a parameter is visible on the page, as when a float is passed where a signature requires an int. Two int values divide to a rounded int, so 175 / 3 is 58.

A String takes the first step up in granularity, since it is an ordered sequence of char values, in double quotes. .len gives its number of characters and has no parentheses, because it is an attribute. .sub(start, stop) gives a part of the string, counting from 0 and including the stop index, so "They went.".sub(0, 3) is "They", and .sub(0, 0) is one character. concat() joins strings, because + is for numbers only. Remember to pass a variable's name without quotes: concat("Hello, ", name) uses the value, and concat("Hello, ", "name") uses the word.

Collections by position and by key#

Strings hold only characters, and arrays extend the same idea of numbered positions to any one type. An array holds values of one type accessed by a zero-based int index, so [1, "two", 3.0] can't be an int[], unlike a Python list. In a two-dimensional array, values are accessed by row and then column, with both indexes starting at 0.

01 int[] nums = [2, 3, 4]
02 int[][] grid = [[1, 2, 3], [4, 5, 6]]
03 output(nums[0])
04 output(grid[1, 2])
05 output(grid.size)

>>> 2
>>> 6
>>> [2,3]

As line 05 shows, an array's .size returns a pair, [rows, columns]. A one-dimensional array has one row, so nums.size is [1, 3], and its length is nums.size[1]. Its last index is one less than that, and using an index that doesn't exist produces ERROR. This is why a loop that reads v[i + 1] has to stop one position early. Fixing one index and moving the other gives you a whole row or column, so g[r, 1], with r looping, walks down the second column.

Arrays can also change size through their methods. .append() adds to the end. .insert(i, x) adds at an index that already exists, shifting later values up, and doesn't replace anything. .del(i) removes the value at an index, shifting later values down by one. .search(x) returns the position of the first match as a [row, column] pair, or NULL if there is no match. These shifts are a common source of bugs. If a forward loop deletes at i and then adds 1 to i, the value that just moved into position i gets skipped, so [0, 0, 5] keeps one of its zeros after a loop meant to remove them all.

An array is a good fit when you know the position you want, but often you know something else about the value, such as a person's name. An associative array, or map, stores unique keys with values, accessed by key. It declares the key type and then the value type, and all keys share one type, as do all values, so a map from strings to strings can't also hold the number 17 as a value.

01 String String{} book = {"title": "Emma", "author": "Austen"}
02 book{"year"} = "1815"
03 output(book{"title"})
04 output(book.size)

>>> "Emma"
>>> 3

Assigning to a new key adds a pair, as on line 02, and assigning to an existing key replaces its value. Reading a key that doesn't exist is an error, so a program that counts how often each title appears has to treat a title's first appearance separately, setting its count to 1 in one branch and adding 1 in the other. A map's .size is a single int, unlike an array's pair. .remove(key) deletes a pair, and .search(value) returns an array of the matching keys, since several keys can share a value.

Stacks and queues: structures defined by behavior#

Arrays and maps are described by how they store and find values. Stacks and queues are described by the rules for adding and removing, which makes each an abstract data type: a specification of behavior that can be implemented in more than one way. This is the interface and implementation distinction from 0002.e, applied to data.

A stack is last in, first out (LIFO), with items added and removed at the same end, like a pile of plates. It fits wherever the most recent thing must be dealt with first. Undo reverses the latest change, and a browser's Back button returns to the latest page. Function calls work this way too: if a() calls b() and b() calls c(), then c() finishes first, which is why the structure holding pending calls is called the call stack. Checking balanced parentheses also uses a stack, pushing each ( and popping on each ), so a ) that arrives when the stack is empty signals a problem. With an array, append pushes, and deleting the last index pops:

01 String[] pages = ["home", "news"]
02 pages.append("sports")
03 pages.del(pages.size[1] - 1)
04 output(pages[pages.size[1] - 1])

This adds "sports", removes it again, and outputs >>> "news".

A queue reverses the priority. It is first in, first out (FIFO), with items added at one end and removed from the other, like a line of people. Print jobs and help desk lines are queues, because fairness requires serving the earliest arrival first. If a print server used a stack, early jobs could wait a long time as newer ones kept going ahead of them. With an array, append joins the line, and del(0) serves the next. Someone who needs another turn can be appended again and so goes to the back.

01 String[] line = ["Ana", "Ben"]
02 line.append("Cy")
03 String served = line[0]
04 line.del(0)
05 output(line[0])

This serves "Ana" and outputs >>> "Ben".

Linked lists: a different way to hold a sequence#

Those deletions at index 0 have a cost, since every remaining value has to shift. A linked list avoids this by not keeping values side by side at all. It stores values in nodes, each holding a value and a pointer to the next node, and a doubly linked list adds a pointer to the previous node. Traversal follows pointers, moving with node = node.next until the value is NULL:

01 int count = 0
02 while (node != NULL)
03   count = count + 1
04   node = node.next
05 output(count)

The trade-off with arrays is direct. Once you have reached the right place, inserting relinks pointers without shifting values. Reading by position, however, requires walking from the start, whereas an array goes straight to a position, which is also why methods that repeatedly jump to the middle of a sorted sequence need an array. Inserting requires relinking pointers in an order that keeps the rest of the list reachable. Save a node's old next pointer first, or the rest of the list becomes unreachable: running A.next = N before N has been pointed at what followed A loses everything after A. To insert N between A and B in a doubly linked list, four pointers need setting, two on the new node and one on each neighbor:

01 N.prev = A
02 N.next = B
03 A.next = N
04 B.prev = N

Objects and classes#

So far, every structure has held values of one kind, but a student or a bank account has several attributes of different types along with things it can do. A class defines a type's attributes and methods, and an object is an instance of a class with its own attribute values, accessed using dot notation, with the object before the name, as in c.honk().¹ A class is the template, so each object has its own copy of the data.

01 Pet a = Pet("Rex")
02 Pet b = Pet("Tom")
03 a.name = "Max"
04 output(b.name)

This outputs >>> "Tom", because changing a.name doesn't change b.name. Having separate objects is different from having two names for one object, though. Assigning an object to a second variable commonly shares one object, so after Pet q = p, changing q.name also changes what p.name reports. Assigning an int copies its value, so after int b = a, changing b leaves a alone.

Across all levels: scope and choosing a structure#

Variables at every level of this section have names, and a name is usable only in part of a program. A variable's scope is the part of a program in which its name is valid, so a variable declared inside a function or block isn't available outside it. A program that calls total(a) and then outputs total's local variable s stops with an error, whatever order the lines are in. The fix that preserves a function's independence is to return the value and use it at the call, without adding a global variable. A local name can hide an outer variable of the same name, without changing it. A function's local variable is created anew on each call, so a count kept inside a function restarts each time, and it has to live outside the call or be passed in. A variable declared in a loop header may not be valid after the loop, unlike in Python.

With these structures available, choosing among them means asking how the data will be used. Choose an array for ordered access by position, a map for lookup by key, a stack for most-recent-first access, and a queue for first-come, first-served processing. A two-dimensional array or a map wouldn't express what a sign-up table needs, and a program that always adds to the end of an array and removes from index 0 is a queue, whatever it calls its variable. Needs can also call for more than one structure. A leaderboard may need both a map, to get a player's score by name, and an array, to keep names in rank order. And when you need a type with both data and behavior, such as many accounts with their own balances, a class with one object per account fits better than one number or a string holding everything.

The last design question concerns what to leave out, and it applies to objects in particular. A class generally shouldn't store what it can derive, such as area along with width and height, or age along with birth_year, because copies can become inconsistent: after a few years, a stored age is simply wrong. A method can calculate these values when they're needed, and a stored count of an array's length is better replaced by items.size[1]. The exception is a value that is costly to compute, read often, and reliably updated, where the trade of space for time can be justified.

These structures and the control structures of 0002.f are the materials of any algorithm, and so far they've all been written in one notation. The next section looks at how the same algorithm can be represented in others, including flowcharts and blocks.

• primitive types: bool, int, float, and char, the basic kinds of value
• String: an ordered sequence of char values
• array: values of one type, accessed by a zero-based int index
• two-dimensional array: values accessed by row and then column, as in grid[row, column]
• associative array (map): unique keys with values, accessed by key
• abstract data type: a specification of behavior that can be implemented in more than one way
• stack: last in, first out (LIFO), with items added and removed at the same end
• queue: first in, first out (FIFO), with items added at one end and removed from the other
• linked list: nodes that each hold a value and a pointer to the next node
• doubly linked list: a linked list whose nodes also point to the previous node
• class: a definition of a type's attributes and methods
• object: an instance of a class with its own attribute values
• scope: the part of a program in which a name is valid

Practice: practice questions for 0002.h

1. MWC1, Dice: classes, instances, randomness, and repeated runs. ↩