Listen



Listen ändern

Listen sind Listen, auch Einkaufslisten In diesem Kapitel wollen wir weitere Aspekte von Listen behandeln. Im Wesentlichen geht es darum Elemente anzuhängen, einzufügen und zu löschen.

Eine Liste kann man als einen Stapelspeicher (englisch: stack) ansehen. In der Informatik bezeichnet ein Stapelspeicher (oder Stapel) -- manchmal auch Kellerspeicher (Keller) genannt -- eine Datenstruktur mit minimal zwei Operationen: eine, mit der man Daten auf den Stapel legen kann, und eine, um das oberste Element des Stapels wegzunehmen. Stellen Sie sich das wie einen Stapel noch zu lesender Bücher vor. Sie wollen die Bücher des Stapels von oben nach unten durchlesen. Kaufen Sie zwischendurch ein neues Buch, kommt es oben drauf und ist damit das nächste Buch, was gelesen werden "muss". In den Programmiersprachen werden hierfür meistens die folgenden Operationen zur Verfügung gestellt:



pop und append

>>> l = [42,98,77]
>>> l.append(103)
>>> l
[42, 98, 77, 103]
>>> x = l.pop()
>>> x
103
>>> l.pop()
77
>>>
Man kommt schnell in die Situation, dass man mehr als ein Element an eine Liste anhängen will. So möchte man beispielsweise die Elemente einer Liste anhängen. Versucht man dies mit append, erlebt man eine unangenehme Überraschung:
>>> l = [42,98,77]
>>> l2 = [8,69]
>>> l.append(l2)
>>> l
[42, 98, 77, [8, 69]]
>>> 
Eigentlich hatten wir dieses Ergebnis "erwartet":
[42, 98, 77, 8, 69]



extend

Für diese Fälle gibt es die extend Methode für Listen. Sie dient dazu, an eine Liste mehrere Elemente anzuhängen:

>>> l = [42,98,77]
>>> l2 = [8,69]
>>> l.extend(l2)
>>> l
[42, 98, 77, 8, 69]
>>> 
Das Argument von extend muss ein iterierbares Objekt sein. So kann man extend beispielsweise auch auf Tupel und Strings anwenden:
>>> l = [42,98,77]
>>> l.extend("hello")
>>> l
[42, 98, 77, 'h', 'e', 'l', 'l', 'o']
>>> 
>>> l = [42,98,77]
>>> l.extend((3,4,5))
>>> l
[42, 98, 77, 3, 4, 5]
>>> 



Der '+'-Operator als Alternative zu append

Außer append gibt es noch weitere Möglichkeiten, Elemente an eine Liste anzuhängen. So kann man beispielsweise ein oder mehrere Elemente mit dem "+"-Operator an eine Liste anhängen:
>>> L = [3,4]
>>> L = L + [42]
>>> L
[3, 4, 42]
Was das Laufzeitverhalten betrifft, ist bei diesem Weg höchste Vorsicht geboten, wie wir im Folgenden sehen werden. Eine weitere Möglichkeit besteht in der Verwendung der erweiterten Zuweisung (englisch: augmented assignment, compound assignment):
>>> L = [3,4]
>>> L += [42]
>>> L
[3, 4, 42]
Logisch gesehen sind beide Vorgehensweisen gleichwertig, d.h. sie liefern die gleichen Ergebnisse. Im Folgenden wollen wir uns das Laufzeitverhalten dieser beiden und der append-Methode im Vergleich anschauen. Wir messen die Laufzeit mittels des time-Modules, auf das wir hier nicht weiter eingehen wollen. Für das Verständnis des Programmes genügt es zu wissen, dass time.time() eine Floatzahl zurückliefert, die die Zeit in Sekunden seit ,,The Epoch''1 darstellt. Mit time.time() - start_time berechnen wir also die Zeit in Sekunden, die nötig war die for-Schleifen zu berechnen.
import time

n= 100000

start_time = time.time()
l = []
for i in range(n):
    l = l + [i * 2]
print(time.time() - start_time)

start_time = time.time()
l = []
for i in range(n):
    l += [i * 2]
print(time.time() - start_time)

start_time = time.time()
l = []
for i in range(n):
    l.append(i * 2)
print(time.time() - start_time)
Dieses Programm liefert "erschreckende" Ergebnisse:
26.3175041676
0.0305399894714
0.0207479000092
Der "+"-Operator ist in diesem Lauf etwa 1268-mal langsamer als die append-Methode. Die Erklärung ist einfach: Bei der append-Methode wird in jedem Schleifendurchlauf einfach ein weiteres Element an die Liste angehängt. Im ersten Fall wird in jedem Schleifendurchgang, also mit jeder Zuweisung l = l + [i * 2], die komplette Liste kopiert und dann das neue Element an die neue Liste angehängt. Anschließend muss der Speicherplatz für die alte -- nun nicht mehr benötigte -- Liste freigegeben werden. Wir können auch sehen, dass die Benutzung der erweiterten Zuweisung im zweiten Fall im Vergleich zur ersten Methode nahezu genauso schnell ist wie der Weg mit append. Allerdings ist die erweiterte Methode dennoch etwas langsamer, da bei append, das übergebene Objekt nur referenziert wird.



Entfernen eines Wertes mit remove

Mit der Methode "remove" kann man einen bestimmten Wert ohne Kenntnis des Indexes aus einer Liste entfernen.
s.remove(x)
Dieser Aufruf entfernt das erste Vorkommen des Wertes x aus der Liste s. Falls x beim Aufruf nicht in der Liste vorhanden ist, gibt es einen ValueError. Im folgenden Beispiel rufen wir dreimal die remove-Methode auf, um die Farbe "green" zu entfernen. Da die Farbe nur zweimal in der Liste "colours" ist, erhalten wir beim dritten Mal einen ValueError:
>>> colours = ["red", "green", "blue", "green", "yellow"]
>>> colours.remove("green")
>>> colours
['red', 'blue', 'green', 'yellow']
>>> colours.remove("green")
>>> colours
['red', 'blue', 'yellow']
>>> colours.remove("green")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.remove(x): x not in list
>>> 


Finden der Position eines Elementes

Mit der Methode index kann man die Position eines Elements innerhalb einer Liste ermitteln.
s.index(x[, i[, j]])
Es wird der Index für das x ermittelt. Falls der optionale Parameter i gegeben ist, beginnt die Suche erst ab dieser Position und endet bei der Position j, falls j gegeben ist. Es erfolgt eine Fehlermeldung, falls x nicht in s vorkommt.
>>> colours = ["red", "green", "blue", "green", "yellow"]
>>> colours.index("green")
1
>>> colours.index("green", 2)
3
>>> colours.index("green", 3,4)
3
>>> colours.index("black")
Traceback (most recent call last):
  File "", line 1, in 
ValueError: 'black' is not in list
>>> 


insert

Wir haben gesehen, dass wir mit append ein Element an das Ende einer Liste anhängen können. Aber es gibt keine Möglichkeit, mittels append ein Element an eine beliebige Stelle einer Liste einzufügen. Dazu gibt es die Methode "insert":
s.insert(index, object)
Ein Objekt "object" wird in die Liste "s" eingefügt. Die früheren Elemente ab der Position index werden um eins nach rechts verschoben.
>>> colours = ["red", "green", "blue", "yellow"]
>>> colours.insert(1,"black")
>>> colours
['red', 'black', 'green', 'blue', 'yellow']
>>> 
Das Verhalten der Methode "append" lässt sich sehr einfach mit "insert" simulieren:
>>> abc = ["a","b","c"]
>>> abc.insert(len(abc),"d")
>>> abc
['a', 'b', 'c', 'd']
>>> 


Anmerkungen:

1 "The Epoch" bezeichnet das Datum 1. Januar 1970 und die Uhrzeit 00:00, als Beginn der Unix Zeitzählung (ab UNIX Version 6)