deutsch     english    français     Print

 

3.9 LISTS

 

 

INTRODUCTION

 

Sometimes you have to store values that belong together, but their exact number is not known during the creation of the program. Because of this, you will need a data structure where you can store multiple values. The structure should be flexible enough to take the order of the added values into account. It is obvious in this case to use a sequence of simple containers, which you have already heard about, namely a list. Here you will find out in detail how to work with lists.

A list with 5 elements

A list consists of individual elements arranged one after the other. In contrast to an unstructured set of elements, there is a first and a last element, and all the other elements except the last have a successor.

Lists (and similar containers) are enormously important for programming. The operations possible with lists are very descriptive. The most important are:

Adding elements (at the end, at the beginning, somewhere in between)

Reading elements

Changing elements

Removing elements
Iterating all elements

Sorting elements

Searching for elements

In Python you can store any data in lists, not only numbers. The individual elements can even have a different type and you can, for example, store numbers and letters in the same list.

PROGRAMMING CONCEPTS: Container, list, predecessor, successor, reference variable

 

 

GRADE LIST

 

You can interpret a list as a variable. It thus has a name and a value, namely its elements. You create it with a pair of square brackets, e.g. li = [1, 2, 3] generates a list with the elements 1, 2 and 3. A list can also be empty. You can define an empty list with li = [].

Grade books, where you enter the grades for a particular school subject, are a typical use of lists, let's say biology grades. At the beginning of the semester you have an empty list, which is expressed in Python as bioGrades = []. Writing in grades is then equivalent to adding list items. In Python you use the command append(), so for a score of 5 it looks like this: bioGrades.append(5).

You can view the list at any time with a print command, just simply write print bioGrades.
If you want to calculate your grade point average, you have to run through the list. You can do this easily and elegantly with a for loop, because

for grade in bioGrades:

copies every list value in order to the variable grade, and you can then use this in the loop body.

bioGrades = []
bioGrades.append(5.5)
print bioGrades
bioGrades.append(5)
print bioGrades
bioGrades.append(5.5)
print bioGrades
bioGrades.append(6)
print bioGrades
count = 0
for note in bioGrades:
    count += note
print "Average: " + str(count / len(bioGrades))
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

Using the method append() you can add new elements to the end of the list.

The built-in function len() returns the current length of the list. Note the interesting trick with the variable sum, with which you can create the sum to then calculate the average. You can also obtain the sum directly with the built-in function sum(bioGrades).

 

 

LIST WITH A FIXED NUMBER OF ELEMENTS

 

It is often already known how long a container list has to be, and that all elements have the same data type, when creating the program. In many programming languages you call such a data structure an array. The individual elements are usually accessed via their index. In Python there is no such data type with fixed length and instead you use a list.

The program defines a polygon as a list with 4 vertices (these are again defined as lists with 2 coordinates). In order to access them with indices from the start, create a list with 4 zeros polygon = [0, 0, 0, 0]. You can also use the shorthand notation polygon = [0] * 4.

After that, you copy in the 4 vertices, which replaces the zeros by point lists. With a for loop you display the polygon.
 
from gpanel import *

pA = [0, -3]
pB = [5, -3]
pC = [0, 7]
pD = [-5, 7]

makeGPanel(-10, 10, -10, 10)
line(-10, 0, 10, 0)
line(0, -10, 0, 10)

polygon = [0] * 4  # list with 4 elements, initialized with 0
polygon[0] = pA
polygon[1] = pB
polygon[2] = pC
polygon[3] = pD

for i in range(4):
    k = i + 1
    if k == 4:
        k = 0
    line(polygon[i], polygon[k])
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

If you already know the length of the list when creating the program, generate a list with the initialization values 0 and then refer to the elements using the index.

Remember that the index of the first element is 0 and the index of the last element is len(list) - 1.

 

 

INSERTING AND DELETING ELEMENTS

 

The program shows how a word processor works. The entered characters are inserted into a list of letters. It is clear that you do not know how many letters you will enter in the beginning, so a list is the ideal data structure. In addition, you see a text cursor which can be set to any position in the text with a mouse click.

When you type using a character key the letter is inserted to the right of the cursor and the list grows. When you use the backspace key the character to the left of the cursor is deleted and the list shrinks.

In order to represent everything nicely, you write the characters as text with a text color and background color in a GPanel. For this you run through the list with a list index i.
 
from gpanel import *

BS = 8
SPACE = 32
DEL = 127

def showInfo(key):
    text = "List length = " + str(len(letterList))
    if key != "":
        text += ". Last key code = " + str(ord(key))
    setStatusText(text)  
        
def updateGraphics():
    clear()
    for i in range(len(letterList)):
        text(i, 2, letterList[i], Font("Courier", Font.PLAIN, 24), 
              "blue", "light gray")
    line(cursorPos - 0.2, 1.7, cursorPos - 0.2, 2.7) 

def onMousePressed(x, y):
    setCursor(x)
    updateGraphics()

def setCursor(x):
    global cursorPos
    pos = int(x + 0.7)
    if pos <= len(letterList):    
       cursorPos = pos

makeGPanel(-1, 30, 0, 12, mousePressed = onMousePressed)

letterList = []
cursorPos = 0
addStatusBar(30)
setStatusText("Enter Text. Backspace to delete. Mouse to set cursor.")
lineWidth(3)

while True:
    delay(10)
    key = getKey()
    if key == "":
        continue
    keyCode = ord(key)
    if keyCode == BS:  # backspace
        if cursorPos > 0:
            cursorPos -= 1
            letterList.pop(cursorPos)
    elif keyCode >= SPACE and keyCode != DEL:      
        letterList.insert(cursorPos, key)
        cursorPos += 1
    updateGraphics()
    showInfo(key)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

You have already learned that you can access individual elements of a list using a list index that starts at zero. For this, you use the square brackets, i.e. letterList[i]. The index must always lay in the range of 0 and list length - 1. When you use a for in range() structure the stop value is just the length of the list.

You should never access an element that does not exist with the index. Errors with invalid index lists are one of the most common errors in programming. If you do not pay attention, you get programs that sometimes work and sometimes die.

To test which key was pressed you can use getKey(). This function returns immediately after the call and delivers either the character of the last key pressed as string or the empty string, if no key has been pressed.

 

 

ALREADY A PROFESSIONAL PROGRAM

 

You are already able to visualize a graph with your knowledge [more... Graph Drawing is a whole topic of computer science]

The task (also called "program specification") is the following:
You can create filled circles in the graphics window with a right mouse click, which are considered to be nodes of a graph, where the nodes are interconnected with lines, called edges. Go on a node with the mouse; with a left mouse press and subsequent dragging you can move it around while the graph is updated constantly. If you right click on an existing node, it will be removed.

It is wise that you solve complex tasks by first looking at a subtask that has not yet met all of the final program specifications. For example, first write a program with which you can create nodes with each click. They should already be connected with all other existing nodes, but you cannot move them yet.

It seems obvious to model the graph with a list graph in which you store the node points.
 

The nodes themselves are points with two coordinates P(x, y) that you model with a point list pointlist [x, y]. It is therefore a list, that then again contains lists as elements (but with a fixed length of 2). You accomplish joining the nodes with double for loop, but you must make sure that the nodes are only connected once.

from gpanel import *

def drawGraph():
    clear()
    for pt in graph:
        move(pt) 
        fillCircle(2)
    
    for i in range(len(graph)):
        for k in range(i, len(graph)):
            line(graph[i], graph[k])

def onMousePressed(x, y):
    pt = [x, y]
    graph.append(pt)
    drawGraph()

graph = []
makeGPanel(0, 100, 0, 100, mousePressed = onMousePressed)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

Next you are going to incorporate the dragging and deletion of nodes. For this, you will need the right mouse button. As you drag it is important to know which node is being pulled. You can remember it by its index iNode in the graph list. If no node is being pulled, iNode = -1. In the function near(x, y), using the Pythagorean theorem, you calculate the distance between point P(x,y) and all other points. Once one of the squared distances is less than 10, you abort the calculation and return the index of the node. Here you see that you can leave a function using return even in the middle of the procedure.

Everything else is fun programming work that you could also achieve yourself based on your current knowledge.

 

 
from gpanel import *

def drawGraph():
    clear()
    for i in range(len(graph)):
        move(graph[i]) 
        if i == iNode:
            setColor("red")
        else:
            setColor("green")              
        fillCircle(2)
  
    setColor("blue")
    for i in range(len(graph)):
        for k in range(i, len(graph)):
            line(graph[i], graph[k])

def onMousePressed(x, y):
    global iNode   
    if isLeftMouseButton():
        iNode = near(x, y)
    if isRightMouseButton():
        index = near(x, y)
        if index != -1:
            graph.pop(index)
            iNode = -1
        else:
            pt = [x, y]
            graph.append(pt)
    drawGraph()

def onMouseDragged(x, y):
    if isLeftMouseButton():
        if iNode == -1:
            return        
        graph[iNode] = [x, y]
        drawGraph()

def onMouseReleased(x, y):
    global iNode
    if isLeftMouseButton():
        iNode = -1
        drawGraph()

def near(x, y):
    for i in range(len(graph)):
        p = graph[i]
        d = (p[0] - x) * (p[0] - x) + (p[1] - y) * (p[1] - y)
        if  d < 10:
            return i
    return -1

graph = []
iNode = -1
makeGPanel(0, 100, 0, 100, 
              mousePressed = onMousePressed, 
              mouseDragged = onMouseDragged,
              mouseReleased = onMouseReleased)
addStatusBar(20) 
setStatusText("Right mouse button to set nodes, left button to drag")             
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

The program is fully event-driven. The main block only defines two global variables and initializes the graphics window. For each action the entire graphics window is cleared and rebuilt with the current situation of the graph.

The most important operations with lists:

 
 

li = [1, 2, 3, 4]

li = [1, "a", [7 , 5]]

li[i]

li[start:end]

li[start:end:step]

li[start:]

li[:end]

li.append(element)

li.insert(i, element)

li.extend(li2)

li.index(element)

li.pop(i)

pop()

li1 + li2

li1 += li2

li * 4

[0] * 4

len(li)

del li[i]

del li[start:end]

del li[:]

li.reverse() 

li.sort() 

x in li

x not in li

Defines a list with the numbers 1, 2, 3, 4

Defines a list with different data types

Accesses list elements with index i

Sublist with elements from start to end, without end

Sublist with elements from start to end, with the given step

Sublist with all elements starting at start

Sublist from the first element up to end, but without end

Appends element at the end

Inserts element at position i (element i slides to the right)

Appends all elements of li2 (concatenation)

Finds the first occurrence and returns its index

Removes and returns the element with index i

Removes and returns the last element

Returns the concatenation of li1 and li2 in a new list

Replaces li1 by the concatenation of li1 and li2

New list with elements of li repeated four times

Makes a new list with length of 4 (all elements number 0)

Returns the number of list elements

Removes the element with index i

Removes all elements from start to end, but without end

Removes the element with index i

Reverses the list (last element becomes the first)

Sorts the list (comparison with standard methods)

Returns True, if x is (included) in the list

Returns True, if x is not in the list

 

The notation with square brackets is called a slice operation. start and end are indices of the list. The slice operation works similarly to the parameters of range().

 

 

EXERCISES

 

1.


Input any number of grades with inputFloat("prompt", False). If you press the Cancel button, the average will be written out in the console. Note that you must use the parameter value False so that the program does not end if you click Cancel. The special value None is returned at the termination, which as usual, you can test with if.


2.

Extend the editor program above using the slice notation so that every right mouse click cuts away the beginning of the sentence, up to and including the first blank space.



3.

Each time you click, a new image of a football (football.gif) should appear at the location of the mouse cursor. All of the footballs are constantly moving back and forth on the screen. Familiarize yourself with the football example in the chapter animations. You can optimize the program by loading the football image once with img = getImage("sprites/football.gif") and passing img to the function image().


 
 

 

 

 

EXTRA MATERIAL:


 

MUTABLE AND IMMUTABLE DATA TYPES

 

In Python all data types are stored as objects, including the numeric types (integer, float, long, complex). As you know, you can access an object by its name. It is also said that the name refers to or is bound to the object. Therefore, such a variable is also called a reference variable.

A particular object can be referred to by more than one name. AN additional name is also called an alias. The following example shows how to deal with this.

A triangle is defined by the three vertex lists a, b, c. You can create an alias with the statement a_alias = a, so that a and a_alias both refer to the same list. If you alter the vertex list with the name a, the changes are obviously also visible in a_alias, since a and a_alias refer to the same list.

 


from gpanel import *

makeGPanel(-10, 10, -10, 10)

a = [0, 0]  
a_alias = a
b = [0, 5]
c = [5, 0]

fillTriangle(a, b, c)
a[0] = 1
setColor("green")
fillTriangle(a_alias, b, c)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

Since numbers are also objects, you would expect the same behavior if you used numbers as vertex coordinate. However, the following example shows a different behavior. If you change xA, the value of  xA_alias does not change.

 


from gpanel import *

makeGPanel(-10, 10, -10, 10)

xA = 0
yA = 0
xA_alias = xA
yA_alias = yA
xB = 0
yB = 5
xC = 5
yC = 0

fillTriangle(xA, yA, xB, yB, xC, yC)
xA = 1
setColor("green")
fillTriangle(xA_alias, yA_alias, xB, yB, xC, yC)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

What is the explanation for that? The reason is that numbers are immutable objects and the statement xA = 1 generates a new number. xA_alias is therefore still 0.

The difference between immutable and mutable data types can also be seen when passing parameters to functions. When an immutable object is passed, it cannot be changed inside the function. When a mutable object is delivered, the function can change the object. Such a change is called a secondary or side effect. In order to have a good programming style, you should use side effects sparingly because they can cause some annoying misconduct that is difficult to trace.

In the following example, the function translate() changes the passed vertex lists.

 


from gpanel import *

def translate(pA, pB, pC):
  pA[0] = pA[0] + 5
  pA[1] = pA[1] + 2
  pB[0] = pB[0] + 5
  pB[1] = pB[1] + 2
  pC[0] = pC[0] + 5
  pC[1] = pC[1] + 2

makeGPanel(-10, 10, -10, 10)

a = [0, 0]  
b = [0, 5]
c = [5, 0]
fillTriangle(a, b, c)
translate(a, b, c)
setColor("green")
fillTriangle(a, b, c)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

In Python all data are stored as objects, but some objects are considered to be immutable. These objects are: numerical data types, string, byte, and tuple.

All other data types are mutable. When you assign a new value to a variable of an immutable data type, a new object is created.

If mutable objects are passed to a function, the function can change the objects, while immutable objects are protected from such changes.