Algorithms: Lists

In the previous post we learned loops: doing the same work over and over while a condition holds. At the end we summed the numbers 1 to 10 — but did you notice those numbers were generated in sequence (n ← n + 1)? There was no pile of stored numbers; we computed the next one on each pass. But what if we have specific values given to us up front? Say your five exam grades: 70, 85, 90, 60, 100. These aren’t a pattern — just a handful of values. How do we hand them to a computer?

From the variables post we know one way: put each grade in its own box. grade1 ← 70, grade2 ← 85, grade3 ← 90… Five grades, five variables, fine. But what about fifty grades? Are you going to invent fifty separate names? And if you wanted to sum them, a loop wouldn’t help either — because each box has a different name, there’s no sequence for the loop to walk. This is exactly where we get stuck. This post is about the idea that frees us: storing many values under a single name, in order. We call it a list.

Why do we need lists?

Back to our problem: you want the average of five exam grades. With separate variables it looks like this:

grade1 ← 70
grade2 ← 85
grade3 ← 90
grade4 ← 60
grade5 ← 100
average ← (grade1 + grade2 + grade3 + grade4 + grade5) / 5
PRINT average

For five grades it’s bearable. But two problems jump out. First: it doesn’t scale. With fifty grades you’d need fifty assignment lines and one enormous sum. Second — and more importantly: you can’t build a loop. Loops were meant for exactly “repeat the same work”, but here there’s no repeatable pattern; grade1, grade2, grade3 are independent names. There’s no sequence for the loop to walk over.

Yet in everyday life we always gather “many things of the same kind” under one heading:

• A shopping list: milk, bread, eggs, cheese… all on one sheet, one below the other.
• A class roster: thirty student names, in order, in one notebook.
• A playlist: hundreds of songs under one name, as track 1, track 2, and so on.

In none of these do we give everything a separate name; we make one list and look at its items in order. That is exactly what a list does on a computer.

What is a list?

Think of a list as a row of boxes lined up side by side — and the whole row carries a single name. In the variables post we pictured a variable as “one box with a label on it”; a list is a row of those boxes. Let’s put our five grades in a list:

grades ← [70, 85, 90, 60, 100]

This line is familiar: the same assignment arrow (←) that puts the value on the right into the name on the left. The only difference is that this time we put not a single number in the box, but a row of numbers inside square brackets. Now we have a single name, grades, holding five values in a definite order. Let’s see that order in a table:

The top row is each box’s position (index), the bottom row is the value in that box. Not mixing these two up is the most important point of this post — we’ll come back to it again and again. A list doesn’t have to hold numbers either; just like with variables, it can hold text:

shopping ← ["milk", "bread", "eggs"]

Same rule: one name (shopping), ordered values inside. Numbers or text, a list means “keep many things of the same kind under one roof, in order.”

Why are lists so important?

Now that you know what a list is, let’s step back and see why it matters so much. Because a list isn’t some minor topic off to the side — it’s the cornerstone quietly running under almost every piece of software you use. Consider:

As you can see, a huge part of what real programs do is holding, walking, filtering and changing “many things of the same kind” — and all of those are lists. That’s exactly why the loop from the previous post and the list in this one, put together, form the most-used pair in programming: the list holds the data, the loop works through it. Grasp this pair and you’ve solved half of how real software works.

How do we reach an element? The index

We’ve built the list; but how do we reach a single value inside it? Here is the magic of a list: each box has a position (index) number, and by naming that number you reach straight into the box you want. We write it with square brackets:

grades ← [70, 85, 90, 60, 100]
PRINT grades[1]      → 70   (the first grade)
PRINT grades[3]      → 90   (the third grade)
PRINT grades[5]      → 100  (the fifth, i.e. the last)

grades[3] reads as: “the value at position 3 of the grades list.” The number in the brackets is the position, and the answer is the value at that position. These two are entirely different things:

The real power of the index shows up here: instead of a fixed number, you can put a variable inside the brackets. If you write grades[i], it gives you the element at whatever position i is — 70 when i is 1, 60 when i is 4. Does something occur to you? If we increase i with a loop — 1, 2, 3… — we can walk the whole list in a single line. In a moment we’ll do exactly that. But first, let’s talk about that famous detail that plagues beginners.

Walking a list with a loop

Now we reach the idea at the heart of this post: a list and a loop, hand in hand. Looking at every element of a list one by one, from start to finish, is called walking (traversing) the list. The pattern: a counter starts at 1, moves up to the list’s length, and on each pass reaches the element at list[counter].

We need a small helper that asks how many elements a list has; we’ll call it length(...). length(grades) gives 5 for our five-element list. Now let’s print all the grades — the very counter loop from the loops post, except the counter now turns into a position:

grades ← [70, 85, 90, 60, 100]
i ← 1
WHILE i ≤ length(grades) DO
    PRINT grades[i]
    i ← i + 1
ENDWHILE

You know the three parts from loops: initialization (i ← 1), condition (i ≤ length(grades)), and progression (i ← i + 1). The only new thing is grades[i] in the loop body — “whatever pass we’re on, the grade at that position.” Let’s see the same idea as a flowchart too; almost identical to the loop diagram from the previous post, only the boxes’ contents changed:

flowchart TD
    A([Start]) --> B["grades ← [70, 85, 90, 60, 100]"]
    B --> C["i ← 1"]
    C --> D{"i ≤ length(grades)?"}
    D -- Yes --> E["PRINT grades[i]"]
    E --> F["i ← i + 1"]
    F --> D
    D -- No --> G([Done])

That loop-back arrow (F to D) is, again, the heart of the loop. Now let’s walk the loop on paper — with the trace table you know from the variables and loops posts:

When i becomes 6 the condition turns false and the loop stops politely, right at the end of the list. Notice: the counter i both counts the passes and points to the position — walking a list is where these two come together. That’s exactly why a loop and a list get along so well.

Accumulating with a list: sum and average

Once you can walk a list, we can do real work with it. Recall the accumulation pattern from the loops post: set up an accumulator before the loop, add to it on each pass, get a single result at the end. Now we apply exactly the same pattern to a list — let’s find the average of the five grades:

grades ← [70, 85, 90, 60, 100]
total ← 0
i ← 1
WHILE i ≤ length(grades) DO
    total ← total + grades[i]
    i ← i + 1
ENDWHILE
average ← total / length(grades)
PRINT average

Here there are two variables, and just like in loops their roles are separate: i is the counter driving the position, total is the accumulator where the result builds up. On each pass total grows by the current grade: 0 → 70 → 155 → 245 → 305 → 405. When the loop ends total is 405; dividing it by the number of elements (5) gives an average of 81.

Finding the highest and the lowest

In the loops post we said “summing, counting, finding the maximum… all are variants of the same accumulation pattern.” Now that we have a list in hand, we can actually do that “find the maximum”: let’s find the highest grade.

The idea is simple and very human: hold a piece of paper, and write the first grade on it for now. Then, as you walk the list, whenever a grade is bigger than the one on your paper, update it. When you reach the end, the highest grade is left on the paper:

grades ← [70, 85, 90, 60, 100]
highest ← grades[1]
i ← 2
WHILE i ≤ length(grades) DO
    IF grades[i] > highest THEN
        highest ← grades[i]
    ENDIF
    i ← i + 1
ENDWHILE
PRINT highest

Did you notice all three structures working together in this example: we walk the list with a loop, compare with a conditional on each pass (conditionals), and write the result to an accumulator. All the pieces of the series — variable, condition, loop, list — meet here in one small program. Walk it on paper: highest goes 70 → 85 → 90 → 90 → 100; it doesn’t change when it hits 60 (since 60 isn’t greater than 90), and stops at 100.

Searching a list: is it there, where?

Another common job: finding out whether a value is in the list. Is a name on the roster? Is that item in the cart? For this too we walk the list and compare each element with what we’re looking for. To hold the result we use a yes/no flag — recall the true/false (boolean) values from the variables post:

names  ← ["Ada", "Ali", "Zeynep", "Can"]
target ← "Zeynep"
found  ← false
i ← 1
WHILE i ≤ length(names) DO
    IF names[i] = target THEN
        found ← true
    ENDIF
    i ← i + 1
ENDWHILE
PRINT found

The logic: we assume the flag is false from the start (“haven’t found it yet”). As we walk the list, if we hit what we’re looking for, we flip the flag to true. When the loop ends the flag tells us whether that value is in the list. If you want to know not just whether but at what position, put a position next to the flag: add position ← i inside the IF block — when the loop ends, position holds the index of the element you were looking for.

Changing a list: add, fix, remove

So far our lists have stayed as they were built. But real lists live: you add something new to a shopping list, you fix a grade, you take an item out of the cart. There are three basic operations — call them a list’s “daily life.”

Fixing an element is easy — pick the position and assign a new value to it. This is the same assignment from variables, except the target is now a box of the list:

grades ← [70, 85, 90, 60, 100]
grades[4] ← 75          (the fourth grade is now 75, not 60)
PRINT grades[4]         → 75

To add an element to the end of a list we’ll say APPEND: it attaches a new value to the end, and the list grows by one box:

shopping ← ["milk", "bread", "eggs"]
APPEND "cheese" TO shopping
PRINT length(shopping)   → 4   (the list now has four elements)

To remove an element we’ll say REMOVE: it takes the value out of the list, and the list shrinks by one box:

shopping ← ["milk", "bread", "eggs", "cheese"]
REMOVE "bread" FROM shopping
PRINT length(shopping)   → 3   ("bread" is gone; list: milk, eggs, cheese)

Notice that a list’s length can change — an important property that sets a list apart from a single variable. Adding a song to a playlist, removing a student from a roster, fixing a grade… each is one of these three operations.

Building a list from empty

So far our lists were born with ready-made values. But most of the time a list starts empty and fills up pass by pass as the program runs — just like filling an empty shopping cart as you walk the aisles. An empty list is created with [] (no boxes inside, length is 0), then it grows inside a loop with APPEND. This is one of the most-used patterns in real software: filtering a bunch of things and collecting only the ones you want.

Let’s do an example: from the numbers 1 to 20, collect only the even ones into a list. We tell even from odd with MOD from the conditionals post (n MOD 2 = 0), count from 1 to 20 with a loop, and append the fitting ones to the empty list:

evens ← []
n ← 1
WHILE n ≤ 20 DO
    IF n MOD 2 = 0 THEN
        APPEND n TO evens
    ENDIF
    n ← n + 1
ENDWHILE
PRINT evens        → [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

This is an upgrade of the “1–10 even numbers” example from the pseudocode and loops posts: there we printed the evens, here we collect them into a list — so we can later count them, sum them, or walk them again.

Two lists side by side: parallel lists

Often we want to hold not one piece of information but related ones: each student has both a name and a grade. A simple way is to keep two separate lists and let the same position map to the same student. This is called parallel lists: names[i] and grades[i], for the same i, describe the same person.

names  ← ["Ada", "Can", "Zeynep"]
grades ← [90, 70, 85]
i ← 1
WHILE i ≤ length(names) DO
    PRINT names[i] + ": " + grades[i]
    i ← i + 1
ENDWHILE

Here + joins two pieces of text (the text concatenation from the variables post). The output is, in order, Ada: 90, Can: 70, Zeynep: 85. With a single i we walk both lists together, because we lined them up in the same order.

A list inside a list: grids and tables

Our lists so far were a single row — one row of boxes. But the world is often two-dimensional: a chessboard, a bingo card, a spreadsheet, a game map, a cinema seating plan… all are rows and columns. The way to represent this is surprisingly simple: a list whose elements are themselves lists. That is, a list inside a list.

grid ← [[1, 2, 3],
        [4, 5, 6]]

grid has two elements, and each one is a row (itself a list): grid[1] is [1, 2, 3], the first row. To reach a single cell you need two positions: first the row, then the column. grid[1][2] is “the second element of the first row,” i.e. 2; grid[2][3] is 6. Let’s look at it as a table:

To walk a two-dimensional list you need a two-dimensional walk: a nested loop. Recall the nested loop from the loops post — each time the outer loop takes a pass, the inner loop runs fully from start to finish. That’s exactly the pattern we need here: the outer loop walks the rows, the inner loop walks that row’s columns:

row ← 1
WHILE row ≤ length(grid) DO
    col ← 1
    WHILE col ≤ length(grid[row]) DO
        PRINT grid[row][col]
        col ← col + 1
    ENDWHILE
    row ← row + 1
ENDWHILE

Note: the outer length(grid) gives how many rows there are (2), while the inner length(grid[row]) gives how many columns are in that row (3). Walk it on paper and it prints 1, 2, 3, 4, 5, 6 in order — the first row start to finish, then the second. Remember the multiplication-table example from the loops post? That nested loop was really practice for walking over a two-dimensional list.

Text is a list too: characters

Here’s that lovely connection we promised. In the variables post we met text (name ← "Ada") as a value type. In fact, a piece of text is, behind the scenes, a list of letters (characters). So everything you’ve learned about lists — position, length, walking — applies directly to text:

word ← "hello"
PRINT word[1]            → "h"   (the first letter)
PRINT word[4]            → "l"   (the fourth letter)
PRINT length(word)       → 5     (five letters)

You can walk text letter by letter just like a list. For example, let’s count how many times a particular letter appears in a word — conditional and accumulation together:

word ← "banana"
count ← 0
i ← 1
WHILE i ≤ length(word) DO
    IF word[i] = "a" THEN
        count ← count + 1
    ENDIF
    i ← i + 1
ENDWHILE
PRINT count              → 3

Common mistakes

Try it yourself

Pen and paper are enough. For each exercise, first write the pseudocode (don’t forget how to walk a list: counter, length condition, list[i]), then draw a trace table and run a few passes by hand.

Exercise 1 — Print a list backwards (easy)

You have the list numbers ← [3, 8, 1, 9, 4]. Print the elements from last to first: 4, 9, 1, 8, 3.

Exercise 2 — Count who passed (medium)

A class’s grades: grades ← [45, 70, 30, 88, 55, 90, 40]. A grade of 50 or above counts as a pass. Find how many passed and print it.

Exercise 3 — Collect only the evens (medium)

From the list numbers ← [7, 4, 11, 2, 9, 8, 5], collect only the even numbers, keeping their order, into a new list, and print that new list.

Exercise 4 — Who got the highest grade? (parallel lists)

Two parallel lists: names ← ["Ada", "Can", "Zeynep", "Ali"] and grades ← [72, 95, 88, 95]. Find the highest grade and the name of the student who got it.

Exercise 5 — Sum of the grid (mini project)

A two-dimensional list: grid ← [[5, 3, 8], [1, 9, 2], [7, 4, 6]]. Find the sum of all the numbers in the grid and print it.

Summary