Chapter 6: Array, List, Dictionary

Array

Provides convenient structure for storing data items of the same data type
Allows for easy reading of data into memory, & efficient accessing of data for processing
Useful when a:
Data list must be processed more than once
Large number of related summing or counting variables are needed

One-Dimensional Array

Only one subscript needed to specify the desired element
A variable of a simple data type consists of a single memory cell that can hold only one value at a time
A variable of a structured data type consists of a collection of memory cells
Array consists of a collection of memory cells for storing a list of values that are all of the same data type (e.g. list of integers / real no.s / characters / boolean values). The entire list is given a name
Each element of an array has a subscript or index
To specify an individual element of an array, give name of both array & subscript
E.g. for an array called scores

scores[4] ← 86 # assign value 86 to the memory cell scores[4] OUTPUT scores[6] # outputs contents of the memory cell scores[6]

// program drill
BEGIN
DECLARE x: ARRAY[1:4] of INTEGER
x[1] ← 83
x[2] ← 59
x[3] ← 88
x[4] ← 72
OUTPUT x[4]
OUTPUT x[2]
OUTPUT x[2+1]
OUTPUT x[2]+1
END
E.g. for
x[1] | x[2] | x[3] | x[4]
83 | 59 | 88 | 72
OUTPUT:
72
59
88
60
Note array index out of range: here, if 4 elements were assumed, i.e. x[1:4], should not access/assign values to x[5] ⇒ bad for computer memory as array ranges from x[1] to x[4]

In programming languages where static arrays are used, a declaration of the array requires the data-type & no. of elements you want in the array ⇒ so memory cells are set aside for the array declared
Using a loop to read (access, write) values into the array

# to assign 83, 50, 88, and 72 interactively to the array x using a for loop
FOR i ← 1 TO 4
OUTPUT “Enter Element:”
INPUT x[i]
ENDFOR

Important use of arrays: process a data list more than once

# E.g. Program reads in list of up to 25 non-negative numbers. User inputs 41, 68, 32, 74, 55, -999. Program will print the numbers in their original order then in reverse order.
BEGIN
DECLARE numbs: ARRAY[1:25] of INTEGER
DECLARE count: INTEGER
DECLARE num: INTEGER
count ← 0        // keeps track of no. of input integers
// read up to 25 non-negative integers into array numbs
OUTPUT “enter non-negative integer:”
INPUT num
WHILE (num >= 0) AND (count < 25)
count ← count + 1
numbs[count] ← num
OUTPUT “enter non-negative integer:”
INPUT num
ENDWHILE
IF (count > 0)
// prints original order
OUTPUT “original order: ”
FOR i ← 1 TO count
OUTPUT numbs[i]
ENDFOR
// prints reverse order
OUTPUT “reverse order: ”
FOR i ← count TO 1 STEP -1
OUTPUT numbs[i]
ENDFOR
ENDIF
END
# OUTPUT:
original order: 41 68 32 74 55
Reverse order: 55 74 32 68 41
# NOTE
numbs array was declared to hold up to 25 integers. In the while loop that reads values into numbs array, count is used as the array subscript. Note: final value of count by the end of while loop is the no. of array cells actually used
In the for loop that takes a second look at the array, count is the upper limit of the loop, not a subscript
May assume that array index starts from 0, i.e. numbs[0:24]. In this case, the pseudocode above, would need to be updated accordingly

Array of Counting Variables

Arrays useful when tallying a number of related quantities
Use array index to directly increment the appropriate count instead of performing a tedious multiway selection

Q: input 1-4 to vote for candidate 1, 2, 3, or 4; -999 ends the list; count votes
E.g. of input: 1 3 1 4 2 1 2 3
E.g. of output:
CANDIDATE       NO. OF VOTES
         1                            17
         2                            38
         3                            24
         4                            32
Use voteCnts to keep track of votes for each of the 4 candidates, e.g.
voteCnts
[1] | 17
[2] | 38
[3] | 24
[4] | 32
At the start of the program, the 4 memory boxes of voteCnts should be initialized to 0.

Draft pseudocode:
Initialize voteCnts to 0s
Use a loop to read in and process each of the votes, e.g. vote of 3 will increase voteCnts[3] by 1
Use a for loop to print final values for each of the memory boxes of voteCnts
Processing a single vote:
INPUT vote reads in a vote from the user. The variable vote will have the value 1, 2, 3, or 4
The value of vote (1, 2, 3, or 4) gives the subscript for the element of voteCnts that should be increased by 1
To count votes: voteCnts[vote] ← voteCnts[vote] + 1

// program voting
// processes the votes and prints each candidate’s tally
BEGIN
CONSTANT VOTERANGE = 4
DECLARE vote: INTEGER
DECLARE voteCnts: ARRAY [1:VOTERANGE] of INTEGER
// initialize voteCnts to 0
FOR i ← 1 TO VOTERANGE
voteCnts[i] ← 0
ENDFOR
// process votes by reading in individual vote and updating
// appropriate counter
OUTPUT “enter vote or -999 to end:”
INPUT vote
WHILE (vote <> -999)
IF (vote >= 1) AND (vote <= 4)
voteCnts[vote] ← voteCnts[vote] + 1
ELSE
OUTPUT “Invalid vote”
ENDIF
OUTPUT “enter vote or -999 to end:”
INPUT vote
ENDWHILE
// prints the number of votes for each candidate
OUTPUT “CANDIDATE       ”, “NO. OF VOTES”
FOR i ← 1 TO VOTERANGE
OUTPUT i, voteCnts[i]
ENDFOR
END

Parallel array

Q: Suppose we have a list consisting of names and their respective grades:
Jones
92
Johnson
88
Cohen
92
Write pseudocode to read above data, find highest grade achieved, and print names of everyone who earned it (might be 1 or more people), e.g.
Highest grade 92
Achieved by:
Jones
Cohen
Note: list of scores will have to be processed twice.
First pass determines what highest score is
Second pass prints names of those who share it
⇒ program uses parallel arrays names and scores
In the parallel arrays, a given student’s name and score will be contained in memory boxes with the same subscript
I.e. the element scores[i] will contain score of student whose name is in name[i]
Names | scores
[1] | Jones | [1] | 92
[2] | Johnson | [2] | 88
[3] | Cohen | [3] | 92

// program HighScorers
// prints names of students with highest score
BEGIN
             CONSTANT MAXSIZE = 40
             DECLARE size, maxScore, score: INTEGER
             DECLARE name: STRING
 
             DECLARE names: ARRAY[1:MAXSIZE] of STRING
             DECLARE scores: ARRAY[1:MAXSIZE] of INTEGER
 
             size <— 0     // keeps track of no. of valid names
             // read all data into parallel arrays
             // using input “xxx” for name to end input
             OUTPUT ”enter name or xxx to end input”
             INPUT name
 
             WHILE (name <> “xxx”) and (size < MAXSIZE)
                          OUTPUT “enter score of student:”
                          INPUT score
 
                          size <— size + 1
                          names[size] <— name
                          scores[size] <— score
 
                          OUTPUT “enter name or xxx to end input:”
                          INPUT name
             ENDWHILE
 
             IF (size > 0)
                          // find highest score
                          maxScore <— scores[1]
                          FOR i <— 2 TO size
                                     IF (scores[i] > maxScore)
                                             maxScore <— scores[i]
                                     ENDIF
                          ENDFOR
                          OUTPUT “Highest grade: ”, maxScore
 
                          // prints names of those achieving highest score
                          OUTPUT “Achieved by: ”
                          FOR i <— 1 TO size
                                      IF (scores[i] = maxScore)
                                              OUTPUT names[i]
                                      ENDIF
                          ENDFOR
             ENDIF
END

Two-Dimensional Array (i.e. matrix)

2 subscripts (a row subscript and a column subscript) needed to specify an element in a matrix
Data being processed can be organised as a table with several rows and columns

Q: Assuming array index starts from 1 and sales is an array containing five-day sales figures for 18 employees. 1st row gives the week’s sales figures for salesperson 1, 2nd row for salesperson 2, etc.
sales
1 | 2 | 3 | 4 | 5
1 | 25 | 31 | 29 | 40 | 30
2 | 41 | 39 | 38 | 42 | 33
3 | 48 | 58 | 62 | 47 | 40
… | …
18 | 30 | 30 | 32 | 34 | 28
To access a particular cell from this array, specify name of array, then row and column of cell. E.g. OUTPUT sales[2,3] for 38 (row 2, column 3); sales[2,4] <— 0 to reassign content at row 2, column 4 to 0 (i.e. 42 changes to 0)
Suppose array sales stores 5-day figure for up to 30 salesperson
Write program fragment that will use contents of sales to output a table giving each individual salesperson’s weekly total:
Salesperson | 5-day total
1 | 155
2 | 193
.. | …
18 | 154
Assume no. of salesperson is stored by the variable size

CONSTANT MAXSIZE = 30
CONSTANT WEEK = 5
DECLARE sales [1:MAXSIZE, 1:WEEK] of INTEGER
// print table heading
OUTPUT “Salesperson               5-day total”
FOR salesPerson <— 1 TO size
             // find salesperson’s weekly total
             sum <— 0
             FOR day <— 1 TO 5
                      sum <— sum + sales[salesperson, day]
             ENDFOR
             OUTPUT salesperson, sum
ENDFOR

Initiating arrays in Python

To initiate a 1D array, assign default values or strings as its content
E.g. score = [0] * 10 initiated an array score of size 10, and each cell has an initial value of 0
E.g. name [‘’] * 10 initiated an array name of size 10, and each cell has an initial empty string
Index always starts with 0 (diff from pseudocode)
2D array requires a for loop
E.g. To initiate an array of size 3x4

row = 3
col = 4
score = [0]*row
for i in range(row):
             score[i] = [0]*col
# score is [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

row_no = 10
col_no = 10
res = []
for i in range(row_no):
row = []
for j in range(col_no):
        row.append(randint(0,1)) # row contains 10 random numbers of 0 / 1
    res.append(row)
print(res)

Lists = sequence of data values (items or elements)

E.g. recipe (list of instructions), text document (list of lines), words in a dictionary
Each item in a list has a unique index that specifies its position (from 0 to length-1)

List literals and basic operators

Including e.g. [[5,9], [541,78]]
When an element is an expression, its value is included in the list

>>> x = 2
>>> [x, math.sqrt(x)]
[2, 1.4142135623730951]

Operator or function	What it does
L[<an integer expression>]	Subscript used to access an element at the given index position
L[<start>:<end+1>]	Slices for a sublist. Returns a new list.
L + L	List concatenation. Returns a new list consisting of elements of the 2 operands.
`print(L)`	Prints the literal representation of the list Note: print([1, 2, 3, 4]) is different from print(“1, 2, 3, 4”)
len(L)	Returns the no. of elements in the list
list(range(<upper>))	Returns a list containing the integers in the range 0 through upper-1
==, !=, <, >, <=, >=	Compares the elements at the corresponding positions in the operand list. Return True if all results are true, or False otherwise
`for <variable> in L:` <statement>	Iterates through list, binding the variable to each element
<any value> in L	Returns True if the value is in the list or False otherwise E.g. 0 in [1, 2, 3] returns False

List of integers can be built using range

>>> first = [1, 2, 3, 4]
>>> second = list(range(1,5))
>>> first == second
True
>>> first[2:4]
[3, 4]

Replacing elements in a list

A list is mutable:
Elements can be inserted, removed, or replaced
The list itself maintains its identity, but its state (its length and contents) can change
Use subscript operator to replace an element. Subscript is used to reference the target of the assignment, which is not the list but an element’s position within it
E.g.

>>> first[3] = 0
>>> first
[1, 2, 3, 0]

E.g.

>>> numbers = list(range(6))         // [0, 1, 2, 3, 4, 5]
>>> numbers[0:3] = [11, 12, 13]
>>> numbers
[11, 12, 13, 3, 4, 5]

Can also use list to assign values to multiple items, e.g.

>>> Name, CG, Gender = [‘Ryan’, ‘S6C’, ‘M’]
>>> Name
‘Ryan’

Inserting and removing elements in a list

List method

L.append(element)

What it does

Adds element to the end of L

List method

L.extend(aList)
i.e. L.extend([…])

What it does

Adds the elements of L to the end of aList

List method

L.insert(index, element)

What it does

Inserts element at index if index is less than the length of L. Otherwise, insert element at the end of L

List method

L.pop()

What it does

Removes and returns element at the end of L

List method

L.pop(index)

What it does

Removes and returns the element at index

Note: if L.append(list), e.g.

>>> L = [1, 2, 3]
>>> L.append([1, 2])
>>> L
[1, 2, 3, [1, 2]]

Note: CANNOT L.extend(element) ⇒ TypeError: ‘int’ object is not iterable

Searching a list

in determines an element’s presence or absence, but does not return position of element
Use method index to locate an element’s position in a list
It raises an error when target element is not found

aList = [34, 45, 67]
target = 45
if target in aList:
print(aList.index(target))
else:
print(-1)

Sorting a list

A list’s elements are always ordered by position but you can impose a natural ordering on them, e.g. in alphabetical order
When the elements can be related by comparing them <, >, and ==, they can be sorted
The method sort mutates a list by arranging its elements in ascending order (aList.sort() which returns a sorted list)

Mutator methods and the value None

All functions and methods learnt previously return a value that the caller can then use to complete its work
Mutator methods (e.g. append, extend, insert, sort) usually return no value of interest to caller. Python automatically returns the special value None
E.g. after aList.sort(), print(aList) returns None

Aliasing and side effects

Due to mutable property of lists, when first and second are aliases (refers to the exact same list object): if we change any element of first, second will make the same change

>>> first = [10, 20, 30]
>>> second = first          //  first and second are aliases (refers to the exact same list object)
>>> first[1] = 99
>>> first
[10, 99, 30]
>>> second
[10, 99, 30]

To prevent aliasing, copy contents of objects, copy contents of object

>>> third = [ ]
>>> for element in first:
third.append(element)
>>> first
[10, 99, 30]
>>> third
[10, 99, 30]

Alternative:
>>> third = first[:]

VS immutable strings:

>>> first = ‘sample’
>>> second = first
>>> first += ‘s’
>>> first
‘samples’
>>> second
’sample’

Equality: object identity and structural equivalence

>>> first = [20, 30, 40]
>>> second = first
>>> third = [20, 30, 40]
>>> first == second
True
>>> first == third
True
>>> first is second
True
>>> first is third
False

Global lists (not in notes, TPE 2026 qn)

Use to ensure that functions modify the intended global variable rather than creating a new local variable
Define and initialise global variable outside the function, but access or modify it within the function
Ensures stored in global list, not a temporary local copy

Q: Write a function, task2_1() to:
Initialize a global 1-dimensional list of size 100 with value 0
Generate 100 unique random integers between 1 and 200 (inclusive)
Store each integer in the list in order at which it is generated
Output the contents of the list

from random import randint
listofInteger = [0] * 100                           # initialisation
def Task2_1():
global listOfInteger                    # using global listofInteger
n = 0
generatedRN = []
while n < 100:
rn = randint(1, 200)
if rn not in generatedRN:  # check unique
genereatedRN.append(rn)
listofInteger[n] = rn # add random no into list
n += 1
print(“Unsorted list: “)
print(listofInteger)
Task2_1()

Tuple

Resembles a list, but is immutable
It is indicated by enclosing its elements in ()

>>> fruits = (“apple”, “banana”)
>>> fruits
(‘apple’, ‘banana’)
>>> meats = (“fish”, “poultry”)
>>> food = meats + fruits
>>> food
(‘fish’, ‘poultry’, ‘apple’, ‘banana’)
>>> veggies = [“celery”, “beans”]
>>> tuple(veggies)
(‘celery’, ‘beans’)

Most operators and functions used with lists can be used in a similar way with tuples

Dictionaries

Organises information by association, not position
Tables / association lists = data structures organised by association
Dictionary associates a set of keys with data values

Dictionary Literals

Python dictionaries are written as a sequence of key/value pairs/entries separated by commas
Enclosed in curly braces { }
Colon (:) separates a key and its value
Keys can be data of any immutable types, including other data structures
{} = empty dictionary
E.g. Phone book: {‘Sarah’:‘476-3321’, ‘Nathan’:‘351-7743’}
E.g. {‘Name’:‘Molly’, ‘Age’:18}

Adding keys and replacing a values

Use [ ] to add a new key/value pair to a dictionary

>>> info = {}
>>> info[“name”] = “Sandy”
>>> info[“occupation”] = “hacker”
>>> info
{‘name’:‘Sandy’, ‘occupation’:‘hacker’}

Use [ ] to replace a value at an existing key

>>> info[“occupation”] = “manager”
>>> info
{‘name’:‘Sandy’, ‘occupation’:‘manager’}

Accessing values

Use [ ] to obtain the value associated with a key
E.g. info[“name”] returns ‘Sandy’
If key is not present in dictionary, an error is raised
E.g. info[“job”] raises KeyError: ‘job’
If the existence of a key is uncertain, test for it using the method get
E.g. print(info.get(“job”, None)) returns None

Removing keys

To delete an entry from a dictionary, use method pop to remove its key
pop expects a key and an optional default value as arguments
E.g.

>>> print(info.pop(“job”, None))
None
>>> print(info.pop(“occupation”))
manager
>>> info
{‘name’:’Sandy’}

Traversing a dictionary

Use a for loop to print all keys and their values

for key in info:
print(key, info(key))

OR use list and dictionary methods to print all keys, values, or both

>>> grades = {90:‘A’, 80:‘B’, 70:‘C’}
>>> list(grades.keys())
[90, 80, 70]
>>> list(grades.values())
[‘A’, ‘B’, ‘C’]
>>> list(grades.items())
[(90, ‘A’), (80, ’B’), (70, ‘C’)]

Note: when print items, all entries are represented as tuples within the list

Dictionary operations	What it does
len(d)	Returns the number of entries in d
aDict[key]	To insert a new key, replace a value, or obtain a value at an existing key
d.get(key [, default])	Returns value if key exists or returns default if key does not exist. Raises an error if default is omitted and key does not exist.
d.pop(key [, default])	Removes key and returns value if key exists or returns the default if key does not exist. Raises an error if default is omitted and key does not exist.
d.clear()	Removes all keys
`for key in d:`	key is bound to each key in d in an unspecified order

list.__ ⇒ list changes, no need to assign as list = list.__ like stings

If equal lists e.g. second = first, any changes made to 1 list will also be made to the other list

⇒ should copy content instead of copy list, e.g. second = first[:] // “:” copies everything

Tuple is immutable like strings

Key of dictionary can be integer, float, string, but NOT list

Pop deletes last entry unless index specified

Note: when print items, all entries are represented as tuples within the list

Dictionary operations	What it does
len(d)	Returns the number of entries in d
aDict[key]	To insert a new key, replace a value, or obtain a value at an existing key
d.get(key [, default])	Returns value if key exists or returns default if key does not exist. Raises an error if default is omitted and key does not exist.
d.pop(key [, default])	Removes key and returns value if key exists or returns the default if key does not exist. Raises an error if default is omitted and key does not exist.
d.clear()	Removes all keys
`for key in d:`	key is bound to each key in d in an unspecified order

list.__ ⇒ list changes, no need to assign as list = list.__ like stings

If equal lists e.g. second = first, any changes made to 1 list will also be made to the other list

⇒ should copy content instead of copy list, e.g. second = first[:] // “:” copies everything

Tuple is immutable like strings

Key of dictionary can be integer, float, string, but NOT list

Pop deletes last entry unless index specified

Quartz 5

Explorer

07 Chapter 6 - Array, List, Dictionary

Chapter 6: Array, List, Dictionary

Chapter 6: Array, List, Dictionary

Graph View

Table of Contents

Backlinks