Skip to content
ExamSpine

Lesson 5.11

Trace list code and state the final contents

Part 5: Text, lists, stacks and queuesReading, about 6 min2 exercises in this lesson, in Python1 exercise in this lesson, in Java

Tracing what a list holds

By the end of this you will be able to trace code that changes the values in a list, and state exactly what the list holds when the code ends.

You already trace variables with a table: one column for each variable, and a new entry each time a line changes one. A list gets a column too. The difference is what you write in it.

One column for the whole list

When a line changes one value of a list, write the whole list again in its column, with the change made. Copy every value that did not change, in the same order. Then each entry is a picture of the list at that moment, and the last entry is the answer to "what does the list hold at the end?".

Swapping two values

marks = [4, 9, 2]
temp = marks[0]
marks[0] = marks[2]
marks[2] = temp
public static void main(String[] args) {
    int[] marks = {4, 9, 2};
    int temp = marks[0];
    marks[0] = marks[2];
    marks[2] = temp;
}
What the line doestempmarks
makes the list[4, 9, 2]
copies marks[0] into temp4
writes marks[2] at index 0[2, 9, 2]
writes temp at index 2[2, 9, 4]

The list ends as [2, 9, 4]: the first and last values have changed places.

Look at the third row. For a moment the list holds 2 twice, and the 4 is no longer in it. That is why temp keeps a copy of the 4 first. Without temp, the last line would have to read the 4 from marks[0], which by then holds 2, and the list would end as [2, 9, 2].

Python can also swap two values in one line: marks[0], marks[2] = marks[2], marks[0]. Both values on the right are read before either one is written, so nothing is lost. Java has no line like that, so in Java you swap with a third variable, as above.

Changes made inside a loop

values = [2, 5, 1, 3]
for i in range(1, len(values)):
    values[i] = values[i] + values[i - 1]
public static void main(String[] args) {
    int[] values = {2, 5, 1, 3};
    for (int i = 1; i < values.length; i++) {
        values[i] = values[i] + values[i - 1];
    }
}

Each pass adds the value before index i to the value at index i. Give the table a column for the index, a column for the value at index i - 1 that is added, and a column for the list after the change. Each row is one pass of the loop.

ivalues[i - 1]values after the change
(start)[2, 5, 1, 3]
12[2, 7, 1, 3]
27[2, 7, 8, 3]
38[2, 7, 8, 11]

The list ends as [2, 7, 8, 11].

Look at the pass where i is 2. The value at index 1 is read, and it is 7, not the 5 the list started with: the pass before had already written 7 there. Every pass reads the list as it is now, after all the changes made so far. That is why you write the whole list after each change. The value you need next is always in the row above.

A common mistake: reading values from the list as it was at the start. Here that would add 2, then 5, then 1, and give [2, 7, 6, 4], which is wrong.

Stating the final contents

When a question asks for the final contents, write every value, in order, between square brackets, as the last entry in your list column shows them. The tables here write a list in square brackets in both languages, even though a Java array is made with curly brackets. Two quick checks catch most slips:

  1. The list has as many values as it started with, unless a line added or removed one.
  2. A value at an index that no line wrote to is the same as at the start.

Now try it yourself on the questions below.

Exercise 5.11.1 · Trace itTrace: swap pass

Complete the trace table for this Python code. The line values[i], values[i + 1] = values[i + 1], values[i] swaps the two values in one step. Then answer the question below the table. [3]

Line 1: values = [3, 1, 4, 2]
Line 2: for i in range(len(values) - 1):
Line 3, indented 1 level: if values[i] > values[i + 1]:
Line 4, indented 2 levels: values[i], values[i + 1] = values[i + 1], values[i]
Line 5: print(values)

Fill in one row each time a line changes i or values, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Rowivaluesoutput
1
2
3
4
5
6
7

Exercise 5.11.2 · Trace itTrace: carry larger

Complete the trace table for this Python code. range(1, len(nums)) starts i at 1, so the loop compares each value with the one before it. Then answer the question below the table. [3]

Line 1: nums = [5, 2, 6, 1, 4]
Line 2: for i in range(1, len(nums)):
Line 3, indented 1 level: if nums[i] < nums[i - 1]:
Line 4, indented 2 levels: nums[i] = nums[i - 1]

Fill in one row each time a line changes i or nums. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes.

Rowinums
1
2
3
4
5
6
7
8

Exercise 5.11.1 · Trace itTrace: carry larger (Java)

Complete the trace table for this Java code. The loop starts i at 1, so it compares each value of the array with the one before it. Write the array in the nums column in square brackets, like [5, 2, 6, 1, 4], not in the curly brackets of the first line. Then answer the question below the table. [3]

Line 1: int[] nums = {5, 2, 6, 1, 4};
Line 2: for (int i = 1; i < nums.length; i++) {
Line 3, indented 1 level: if (nums[i] < nums[i - 1]) {
Line 4, indented 2 levels: nums[i] = nums[i - 1];
Line 5, indented 1 level: }
Line 6: }

Fill in one row each time a line changes i or nums. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes.

Rowinums
1
2
3
4
5
6
7
8
9