Please note that any code on this page is pseudocode, meaning it won't work in any actual programming language.
Control structures are integral parts of programs as they allow us to set the 'flow' of the program. There are a few types of control structures: sequencial, conditional, and iterative (looping). These basically govern which statements will be executed and in what order, allowing us to implement many more algorithms. To implement an algorithm means to take the central idea of the algorithm, such as summing up a list of numbers, and write code which performs that algorithm.
Sequential execution of code is the normal, vanilla default for how code is executed. If we have several statements in a row, they will be executed from top to bottom and left to right, barring the introduction of other control structures. In the example below, statements will be executed in order according to their numbers.
statement 1statement 2statement 3statement 4When programming, it's best to think of the computer like a person literally reading your program. A person would have one instruction in their head at a time, and would move to the next instruction depending on the placement of your control structures. Similarly, program execution moves through your program one statement at a time, directed by the control structures.
Conditionals are useful control structures which allow us to create branches, which basically say "If thing X is true, do thing Y."
Unsurprisingly, the main conditional structure is called the if conditional, which takes the form of a block.
The block of code starts at the if keyword and goes all the way to the closing brace (or curly-brace, if you prefer that).
A keyword is a special word which cannot be used as a variable name because it tells the computer to do something specific where it appears.
In this case, when the computer runs across the word if it knows we are about to use a conditional.
If we tried to do int if = 10;, we would get an error.
An if statement looks something like this:
IF (some condition):{ do this}
In the code above, if the expression some condition evaluates to True, the statement do this is run.
If the expression evaluates to False, the statement inside the block is not executed, and the entire if block is skipped.
A slightly more upgraded conditional is the else if conditional.
This has to follow an if conditional, and forms chains of linked conditionals.
It basically does what it says:
if the original if statement fails (meaning the condition was not met), the computer will check if the else if condition is true, and if so, will 'go into' that block.
'Go into' is programmer speak for execution moving into a specific code block or section of code.
If neither condition passes, both blocks will be skipped, similar to the single if block above; if the first condition passes, the whole else if block will be skipped, and its condition will not even be evaluated.
This is because it is an else if: it only can happen if the first possibility doesn't.
IF (condition A):{ do a}ELSE IF (condition B):{ do b}
In this case, if condition A is met, do a is executed.
If condition A is not met, but condition B is, do b will b executed.
If neither condition A nor condition B are met, the whole block will be skipped.
We can actually string as many else if blocks together as we want, forming long conditional chains.
Here's an example with three else if blocks:
IF (condition A):{ do a}ELSE IF (condition B):{ do b}ELSE IF (condition C){ do c}ELSE IF(condition D){ do d}
This is actually why we call an if statement a branch: in this block, one statement (and only one) will be executed, and the different possibilities stick out like branches from a tree.
If any condition is met, the corresponding statement is executed, and then execution drops down to past the last else if block, even if multiple conditions are true.
If condition A and B are true, but C and D are false, only do a will actually be executed.
The computer won't even check to see if conditions B, C, and D are true or not.
This is why the order matters when you are programming.
If none of the conditions is met, nothing inside the chain runs (is executed) and execution moves down below the last else if.
Finally, there is one more conditional, the humble else block.
It functions much as the else if block from above, in that it has to follow an if or else if statement.
It also only executes if all conditional statements linked to it above don't execute. Once you put an else, you cannot link any more conditionals below it.
IF (condition A):{ do a}ELSE{ do b}
It's quite self-explanatory: if A is true, do a; if A is not true, do b.
If A is true, b will not happen, because b only happens if A is not true.
Please note that in this case, unlike an if or else if chain, where no statement is guaranteed to be executed, either statement a or statement b will be executed.
We may not know ahead of time which one it will be, but we are guaranteed that one of them will run.
We can also use the else block in conjunction with the else if block:
IF (condition A):{ do a}ELSE IF (condition B):{ do b}ELSE IF (condition C){ do c}ELSE{ do d}
In this chain, one statement will run, unlike the chain made up only of else if blocks, where there is a possibility of no statement in the chain running.
Either a, b, or c will be executed, depending on which is the first true condition out of conditions A, B, or C.
If none of those conditions are true, d will run.
The chain-like nature of else if blocks means that an if followed by two else if blocks can be very different from three if blocks:
IF A:{ do a}ELSE IF B:{ do b}ELSE IF C:{ do c}IF A:{ do a}IF B:{ do b}IF C:{ do c}In the first code snippet, which is a single conditional chain made of three blocks, only one of a, b, and c will run, or none of them will run.
In the second code snippet, which is three independent conditional blocks, execution doesn't drop to the end of the chain when a statement is run because there is no chain. There is a possibility of a, b, and c running, because the only thing determining whether a statement runs is its associated conditional. Just because A is true and a runs doesn't mean B won't be true, causing b to run. a and b could run, or a and c, or b and c, or just a, just b, just c, or all three. If A, B, and C all turn out to be false, none of a, b, or c could run.
The last programming structure is the iterative structure, which essentially involves running the same code multiple times.
Different programming languages have various syntaxes and structures to do this, but almost all of them have while loops, so we'll focus on those.
A while loop is very similar to an if conditional: it has a condition (which should be an expression which evaluates to true or false) and a body (a set of statements to be run).
However, the difference is that where an if conditional only runs the block once, a while loops runs the block of code indefinitely, only stopping if the condition becomes false.
Here's an example of a basic while loop:
WHILE (condition):{ do this}To understand it a little better, we need to look at a real example:
int i = 0;WHILE (i < 10):{ i = i++;}
If this is the first real segment of code you've seen, don't worry: we'll break it down.
The first statement tells the computer that we are going to create a variable called i.
This variable will be an int type variable and will have the value of 0.
Now, we come to a while loop, where our condition says that the code inside the while loop will be executed if the variable i is less than 10.
Finally, the code inside the while loop sets the value of the variable i to whatever i is, plus one (remember that the increment operator (++) increases its operand's value by one).
This last bit may be confusing for you, especially if you look at it from a math-tinted lense: in math, statements of equality must be true.
However, this is computer science now, and we aren't making a statement of equality (that would be ==): we are assigning a variable to a value.
When the computer does this, it first evaluates whatever expression is on the right, and then sets the variable on the left to that expression.
We can then see that i++ evaluates to i + 1, so the whole statement sets the value of i to whatever i was, plus one.
So what does this code actually do? For beginning CS students, it is normally very helpful to create a table:
| loop # | val i |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7 |
| 8 | 8 |
| 9 | 9 |
| 10 | 10 |
On the left hand side we have the number of completed loops, while on the right hand side, we have the value of i.
The 0th loop is the state of our variable before the loop starts.
As you can see, each time the loop runs, i is incremented by one.
After the 10th iteration, the value of i equals ten, which makes our condition i < 10 false.
This will cause the loop to end and program execution will move on.
So this code doesn't actually do anything, per se, because it just runs 10 times and then program execution moves beyond the loop. However, we could easily modify this code to do something by putting some additional statements in the block:
int i = 0;WHILE (i < 10):{ i = i++; do something; do something else;}Now that we've learned about variables, data, datastructures, and control structures, we can put them together to traverse an array. Traversing an array refers to using a loop to do something to all of the values in an array in order. To do this, let's think back to the last example array we had:
int i = 0;WHILE (i < 10):{ i = i++;}
We noticed that each loop iteration, i becomes greater by one.
Since array index values also increase by one for each sequential value, let's see if we can use this to our advantage to sum up the values in an integer array.
If you wanted to find the sum of a list of numbers, for example the numbers 1, 2, 3, 4, and 5, what would you do?
I'd bet you'd first create a type of running tally in your mind, which starts at 0, and then you add all of the numbers to it one by one.
Let's do something similar:
integerArray = [1, 2, 3, 4, 5]int i = 0;int sum = 0;WHILE i < 5:{ sum = sum + integerArray[i]; i = i + 1;}
Since datastructures are variables, we can create them like we create normal integer variables, listing the values in a bracketed list separated by commas.
When we refer to datastructure values, we normally do it using bracket notation, like this: datastructureName[key].
If the datastructure is an array, the key will be an integer. If the datastructure is a dictionary, the key will be a string.
In this case, integerArray is our array, containing the values 1, 2, 3, 4, 5, and integerArray[i] refers to the value at the ith index of the array.
We can see clearly that we start the loop with a variable i and a variable sum, both equal to 0.
We can also see that the loop will only run when i is less than 5, and each loop, i is increased by one; thus, the loop will run five times.
i functions as the index pointer, which allows us to select each array value in order, while sum functions as our tally.
Let's construct a table of values and think about what this is doing:
| Loop # | i |
integerArray[i] |
sum |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 1 | 1 | 2 | 1 |
| 2 | 2 | 3 | 3 |
| 3 | 3 | 4 | 6 |
| 4 | 4 | 5 | 10 |
| 5 | 5 | N/A | 15 |
Our columns are the loop number, the value of i, the value of integerArray[i], and the value of sum.
When the loop number is 0 it represents the state of the variables before the loop starts.
When the loop number is 5 it represents the state of the variables after the loop ends.
Any number in between is the state of the variables after that number loop.
During the first iteration of the loop, integerArray[i] is equal to integerArray[0] which equals 1.
During the second iteration, integerArray[i] is equal to integerArray[1] which equals 2.
This continues until the last (fifth) iteration, when i equals 4, so integerArray[i] is equal to integerArray[4] which equals 5.
The value of i increases from 0 to 4 over the course of the iterations, and the indicies of the integerArray array also span the numbers from 0 to 4, so we can sequencially select all of the values in the array.
If we take the value of sum and the value of integerArray[i] and add them, we get the sum for the next loop iteration.
Doing this for all values of i (and thus all values in integerArray) allows us to sum up all of the numbers.
I feel like right now it's important to stress that the code above isn't real code you could run in Java or Python or probably any other language, and that doesn't matter. Sure, the code is decently close to the syntax for those languages, but the real value here is understanding the idea of traversing an array using a loop, summing the values as you go. If we think back to how we would mentally do the calculation, we can construct a chart of what we'd do:
| tally | number to add |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 3 | 3 |
| 6 | 4 |
| 10 | 5 |
| 15 | N/A |
It's basically the same chart; the only difference is that the number to add was stored in a list of numbers in a computer, and we needed a counter number (i) to keep track of which list item to add next.
Let's try it again but with different values in the array:
integerArray = [4, 6, 8, 9, 10]int i = 0;int sum = 0;WHILE i < 5:{ sum = sum + integerArray[i]; i = i + 1;}| Loop # | i |
integerArray[i] |
sum |
|---|---|---|---|
| 0 | 0 | 4 | 0 |
| 1 | 1 | 6 | 4 |
| 2 | 2 | 8 | 10 |
| 3 | 3 | 9 | 18 |
| 4 | 4 | 10 | 27 |
| 5 | 5 | N/A | 37 |
I'd like to stress again that the implementation (the actual code) isn't important, but the concept is what we're after. It's the same as if you tried to add the numbers 4, 6, 8, 9, and 10 in your head: you'd keep a running tally and add them all in sequence.
The next logical thing to do is traverse the array backwards, because, honestly, why not?
To do this, let's think about what our i values must do: we want to start at the largest array index and go all the way back down to index 0, so our i should do the same thing.
Let's try that last example again, but adding backwards:
integerArray = [4, 6, 8, 9, 10]int i = 4;int sum = 0;WHILE i >= 0:{ sum = sum + integerArray[i]; i = i - 1;}| Loop # | i |
integerArray[i] |
sum |
|---|---|---|---|
| 0 | 4 | 10 | 0 |
| 1 | 3 | 9 | 10 |
| 2 | 2 | 8 | 19 |
| 3 | 1 | 6 | 27 |
| 4 | 0 | 4 | 33 |
| 5 | -1 | N/A | 37 |
And now, sideways! But what happened there?
i started at 4 and went down to 0, so the index number started at 4 and went down to 0.
This meant we accessed the array values backwards, starting at the last one and going to the first one.
Our summation didn't change, though.
Going backwards is actually vital in some applications: consider what happens if you traverse forwards and delete an item.
Then your array is one item shorter, and the "next" item which you need to access is in the same spot as the one you just deleted.
If you increase your i by one, you will completely skip that item, which is no good.
However, if you traverse backwards, you avoid that issue.
The last thing I want to mention is what happens when you try to access an array value which doesn't exist. Say we have the code segment from the beginning of this section:
integerArray = [1, 2, 3, 4, 5]int i = 0;int sum = 0;WHILE i < 5:{ sum = sum + integerArray[i]; i = i + 1;}Now, let's change the condition to the following:
integerArray = [1, 2, 3, 4, 5]int i = 0;int sum = 0;WHILE i < 6:{ sum = sum + integerArray[i]; i = i + 1;}
What will happen is that there will be six loop iterations rather than five loop iterations, because i can vary from 0 to 5 rather than 0 to 4, as before.
This means that on the last iteration, the statement sum = sum + integerArray[i] will throw an error, which means we gave the computer an invalid instruction.
If we look at our table for this particular loop, we might be able to divine why we got an error:
| Loop # | i |
integerArray[i] |
sum |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 1 | 1 | 2 | 1 |
| 2 | 2 | 3 | 3 |
| 3 | 3 | 4 | 6 |
| 4 | 4 | 5 | 10 |
| 5 | 5 | N/A | 15 |
| 6 | 6 | N/A | 15 |
Our code told the computer to add the value of sum, which was 15, to the value of integerArray[5].
The problem is that integerArray[5] doesn't exist, because the array only has five elements at array indicies 0 to 4.
Thus, our code would throw an IndexOutOfBoundsError, which happens if we try to access any invalid index (anything less than 0 or more than the length of the array minus one).
I know that loops are hard, and thinking about them can make your brain hurt.
However, take some consolation in the knowledge that like all difficult things, if you do lots of practice, it'll become much easier.
Additionally, if you know that a loop is traversing an array - a huge hint will be if there is a variable like our i which happens to go through all of the index values -
you can generally use heuristics to intuit what the loop is doing, rather than having to chart out the whole thing.
We learned that:
- There are three control structures: sequence, conditional, and iterative.
- There are three conditional types: if, else if, and else.
- A while loop acts like a repeating if statement.
- Traversing an array means to use a loop to do something to every element in an array, in order.
- If we want to sum the contents of an array, we need to create a variable to store a running tally, and then add each array element sequentially.
- Sometimes, we might want to traverse backwards to avoid issues stemming from changing the amount of items in the array.
- If we try to access an element which does not exist, we will get an IndexOutOfBoundsError
Next, please check out the Procedural Programming page.