Zusammengesetzte Datenstrukturen

Zur Verwaltung von mehreren zusammengehörigen Daten als Einheit werden sog. Datenstrukturen verwendet. Python bietet 4 wichtige built-in Datenstrukturen zur Verwendung. Diese Datenstrukturen sind u.a. über syntaktische Konstrukte stark in die Programmiersprache integriert. Die Datenstrukturen sind list, tuple, set und dictionary. All diese Datenstrukturen sind fundamental unterschiedlich aufgebaut und verfügen deshalb über unterschiedliche Vor- und Nachteile.

Ein wichtiges Unterscheidungsmerkmal einer Datenstruktur ist die Veränderbarkeit. Die Veränderbarkeit bestimmt, ob die Datenstruktur nach dem Initialisieren noch verändert werden kann. Es wird also zwischen veränderlichen (mutable) und unveränderlichen (immutable) Datenstrukturen unterschieden.

List

Als Liste wird eine sequentiell geordnete Menge von Elementen verstanden. Jedes Element ist dabei über einen Index identifiziert. In anderen Programmiersprachen wird diese Datenstruktur auch als Array bezeichnet. Syntaktisch werden Listen über die Zeichen [ und ] definiert. Eine Liste ist veränderlich (mutable) und kann Elemente beliebigen Datentyps aufnehmen. Die Länge der Liste ist dynamisch und es können jederzeit Elemente hinzugefügt, geändert oder entfernt werden.

Definition einer Liste

Im folgenden wird eine Liste mit 4 Elementen definiert. Das letzte Element der Liste ist wiederum eine Liste, dies ermöglicht das Erzeugen mehrdimensionaler Listen. Mit der Funktion len kann die Länge der Liste abgefragt werden.

my_list = ['a', 'b', 3, ['sub', 'list']]
print(len(my_list))  # 4

Zugriff auf Listenelemente

Der Zugriff auf einzelne Listenelemente geschieht über den Index. Der Index beginnt dabei bei 0 und endet mit n-1 (n als Länge der Liste). Der Zugriff über den Index kann sowohl lesend als auch schreibend geschehen. Syntaktisch werden ebenfalls die Zeichen [ und ] genutzt.

my_list = ['a', 'b', 3, ['sub', 'list']]

print(my_list[1])  # 'b'
my_list[1] = 2
print(my_list[1])  # 2

Slicing mit Listen

Ähnlich zum Slicing mit Strings kann dieses Verfahren auch für Listen angewendet werden. Mit Slicing können Teillisten aus einer Liste abgefragt werden.

Die generelle Syntax für Slicing ist [start:end:step]. start ist dabei als inklusiver Index und end als exklusiver Index in der Ergebnisliste zu betrachten. Ein Index kann dabei als positive oder negative Ganzzahl angegeben werden. Positive Werte werden von links nach rechts und negative Werte von rechts nach links gelesen. Mit step wird die Schrittweite angegeben. step kann als positive oder negative Ganzzahl angegeben werden. Positive Werte werden vorwärts und negative Werte rückwerts gelesen.

Fehlerhafte Slicingangaben

Eine Slicing Angabe welche keinen Sinn macht, oder außerhalb der Grenzen der Liste definiert ist, erzeugt keinen Fehler. Eine fehlerhafte Slicingangabe gibt eine leere Liste zurück.

Operationen mit Listen

Für Listen sind unterschiedliche Elementaroperationen (zB Einfügen, Löschen, ...) definiert. Operationen können mittels dem Dot-Operator und dem entsprechenden Funktionsnamne direkt auf der Liste ausgeführt werden. Für die Liste ['a', 'b', 'c'] sind im Folgenden einige wichtige Elementaroperationen aufgeführt.

Neues Element am Ende hinzufügen

data = ['a', 'b', 'c']
data.append('x')  # ['a', 'b', 'c', 'x']

Element am Ende entfernen

data = ['a', 'b', 'c']
data.pop()  # ['a', 'b']

Definiertes Element entfernen

data = ['a', 'b', 'c']
data.remove('c')  # ['a', 'b']

Element am Index einfügen

data = ['a', 'b', 'c']
data.insert(1,'y')  #  ['a', 'y', 'b', 'c']

Liste leeren

data = ['a', 'b', 'c']
data.clear()  # []

Grundlegende Datenstrukturen

Mit den Elementaroperationen einer Liste lassen sich grundlegende und häufig genutzte Datenstrukturen erzeugen. Diese Datenstrukturen können für die Realisierung von Algorithmen oder sonstigen Programmen oft nützlich eingesetzt werden.

Stack (LIFO Queue)

Ein Stack funktioniert nach dem Last In First Out Prinzip und stellt die Elementaroperationen push und pop bereit. Mit push wird ein Element auf den Stack gelegt und mit pop wird ein Element vom Stapel genommen.

Die Stack Datenstruktur verbirgt sich zum Beispiel hinter dem Zurück-Button eines Web-Browsers oder der Rückgängig machen Funktion eines Textverarbeitungsprogramms. Die Funktionen append bzw. pop der Python Liste können für die Realisierung eines Stacks verwendet werden.

data = []
data.append('a')
data.append('b')

print(data)  # ['a', 'b']

data.pop()

print(data)  # ['a']

Queue (FIFO Queue)

Eine Queue funktioniert nach dem First In First Out Prinzip und stellt die Elementaroperationen enqueue und dequeue bereit. Mit enqueue wird ein Element am Anfang der Queue eingefügt und mit dequeue wird ein Element am Ende der Queue genommen.

Die Queue Datenstruktur verbirgt sich zum Beispiel hinter der Versand-Operation bei E-Mails (Mail-Queue). Die Funktion insert bzw. pop der Python Liste können für die Realisierung eines Stacks verwendet werden.

data = []
data.insert(0, 'a')
data.insert(0, 'b')

print(data)  # ['b', 'a']

data.pop()

print(data)  # ['b']

Performantere Implementierung

Die Python Standartbibliothek bietet das Modul dequeue, welches eine performantere Implementierung der FIFO Queue darstellt als die Standard Python Liste.

Iteration durch Listen

Pythonen bieten neben dem Schlüsselwort while noch das Schlüsselwort for um Schleifen zu realisieren. Für die Iteration durch Listen eignet sich vorallem die for-Schleife. Im Vergleich zur while-Schleife benötigt die for-Schleife keine Bedingung, da die Anzahl der Schleifendurchläufe über die Länge der Liste definiert ist.

my_list = ['a','b','c']

for my_item in my_list:
    print(my_item)

Im obigen Beispiel wird die Liste my_list definiert. Mit den Schlüsselwörtern for und in wird der Schleifenkopf definiert. Dabei wird das Element der Liste in jedem Schleifendurchlauf in der Variable my_item gespeichert.

Um den Index des aktuellen Elements im Schleifendurchlauf abzufragen kann die Funktion enumerate verwendet werden:

my_list = ['a','b','c']

for idx, my_item in enumerate(my_list):
    print(str(idx) + ": " + item)

Mehrdimensionale Listen

Durch die Angaben einer Liste als Element einer Liste können mehrdimensionale Listen erzeugt werden. Je nach Anzahl der Dimensionen, können einzelne Werte über list[äußerer Index][innerer Index] abgefragt werden.

Im folgenden Beispiel soll das 2-dimensionale Spielbrett eines TicTacToe Spiel mittels einer Python Liste erzeugt werden.

data= [
    [' ','X','O'],
    ['X','O',' '],
    [' ','X',' ']
] 

game_board="    A   B   C\n"
for row in range(3):
    game_board += "  +---+---+---+\n"
    game_board += str(row+1)
    for col in range(3):
        game_board += " | " + data[row][col]
    game_board += " |\n"
game_board+="  +---+---+---+\n"

print(game_board)

Tuple

Tuple sind grundsätzlich identisch zu Listen. Im lesenden Zugriff unterscheiden sich Tuple und List nicht voneinander. Tuple sind jedoch immutable und können nach der Initialisierung nicht mehr verändert werden. Syntaktisch unterscheiden sich Tuple von Listen indem sie mit runden Klammern ( und ) initialisiert werden. Python bietet eine Kurzschreibweise (syntactic sugar) für Tuple bei der die Klammern für die Initialisierung weggelassen werden können.

Der lesende Zugriff auf die Elemente des Tuples erfolgt, ähnlich zur Liste, über eckige Klammern [ und ]. Auch die built-in Funktion len kann mit Tuple verwendet werden.

my_tuple = ('a', 'b', 1)
same_tuple = 'a', 'b', 1
print(my_tuple[1], same_tuple[1])  # 'b' 'b'
print(len(my_tuple), len(same_tuple))  # 3 3

Mit der for-Schleife kann auch durch die Elemente des Tuples iteriert werden:

for my_item in my_tuple:
    print(my_item)

Mutability von Tuple Elementen

Tuple können mutable Elemente (zB List, Set, ...) enthalten. Mutable Elemente eines Tuples können geändert werden. Falls ein Tupel mutable Elemente enthält, kann es nicht mehr als Schlüssel in einem Dictionary verwendet werden. Im folgenden Beispiel wird das mittels einem Tuple demonstriert, welches eine Liste als Element enthält:

tuple = ('blub', ['b', 'a'])
tuple[1][0] = 'c'

Set

Sets orientieren sich konzeptionell an mathematischen Mengen und sind diesen sehr ähnlich. Ein Set ist eine ungeordnete und eindeutige (keine Kopien) Menge von Elementen. Sets werden mit geschweiften Klammern { und } initialisiert und können Elemente beliebigen Datentyps enthalten. Elemente des Sets besitzen keinen Index. Die Länge von Sets sind dynamisch und es können jederzeit Elemente hinzugefügt und entfernt werden (mutable).

Die Operationen mit Sets orientieren sich an den Mengenoperationen der Mathematik: Vereinigung, Durchschnitt, Differenz, symmetrische Differenz.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)  # Vereinigung: {1, 2, 3, 4, 5, 6}
print(A & B)  # Durchschnitt: {3, 4} 
print(A - B)  # Differenz: {1, 2}
print(B - A)  # Differenz: {5, 6}
print(A ^ B)  # Symmetrische Differenz: {1, 2, 5, 6}

Dictionary

Ein Dictionaries ist eine Datenstruktur, welche Schlüssel-Wert-Paare als Elemente hält. Jedes Element wird dabei über einen selbstgewählten und eindeutigen Schlüssel identifiziert. Die Länge eines Dictionary ist dynamisch und es können jederzeit Elemente entfernt oder hinzugefügt werden (mutable).

Dictionaries werden, ähnlich zu Sets, mit geschweiften Klammern { und } definiert. Für die Angabe der Schlüssel-Wert-Paare als Elemente wird der Doppelpunkt : als Trennzeichen verwendet. Der Zugriff auf die Werte (lesend/schreibend) im Dictionary wird über die eckigen Klammern [ und ] und der Angabe des zugehörigen Schlüssels durchgeführt.

Im folgenden Beispiel wird ein Dictionary der Länge 3 erzeugt. Es werden die Schlüssel 'one', 'two' und 3 verwendet. Als Werte werden die Zahl 123, die Zeichenkette '2' und die Liste ['a','b'] definiert.

my_dict = { 'one' : 123, 'two' : '2', 3 : ['a','b'] }

print(my_dict['one'])  # 123
print(my_dict[3][0])   # 'a'

my_dict['one'] = 'changed'

print(my_dict['one'])  # 'changed'

Eine Zuweisung über einen Schlüssel der noch nicht im Dictionary existiert, führt dazu, dass ein neues Element mit dem Schlüssel angelegt wird. Das Dictionary wird dabei erweitert und auch die Länge erhöht. Im folgenden Beispiel wird ein neuer Schlüssel 'new' angelegt:

my_dict = { 'one' : 123, 'two' : '2', 3 : ['a','b'] }

print(len(my_dict))  # 3

my_dict['new'] = 'hello'

print(len(my_dict))  # 4

Die Elemente eines Dictionary bestehen aus 2 Teilen, dem Schlüssel und dem zugehörigen Wert. Es bestehen grundsätzlich 2 Möglichkeiten um durch ein Dictionary zu iterieren:

• Per Default verläuft die Iteration des Dictionary mit der for-Schleife über den Schlüssel. Der zugehörige Wert kann dann über den Zugriff über die eckigen Klammern durchgeführt werden.
• Durch die Nutzung der Funktion items() kann für jede Iteration das Tupel aus Schlüssel und Wert genutzt werden.

Beide Formen der Iteration sind im folgenden Beispiel demonstriert:

names = { 'Peter' : 25, 'Hilde' : 31, 'Bruno' : 45 }
for key in names:
    print("Name: " + key + ", Alter: " + str(names[key]))

for key, value in names.items():
    print("Name: " + key + ", Alter: " + str(value))

# print 2x
# Name: Peter, Alter: 25
# Name: Hilde, Alter: 31
# Name: Bruno, Alter: 45