10 Python-Datenstrukturen [Erklärt mit Beispielen]

Möchten Sie Ihre Programmiertools um Datenstrukturen erweitern? Machen Sie noch heute die ersten Schritte, indem Sie sich mit Datenstrukturen in Python vertraut machen.

Wenn Sie eine neue Programmiersprache lernen, ist es wichtig, die grundlegenden Datentypen und die eingebauten Datenstrukturen zu verstehen, die die Sprache unterstützt. In diesem Leitfaden zu Datenstrukturen in Python werden wir die folgenden Punkte behandeln:

• Vorteile von Datenstrukturen 
• eingebaute Datenstrukturen in Python, wie Listen, Tupel, Wörterbücher und Mengen
• Implementierungen von abstrakten Datentypen wie Stapel und Warteschlangen.

Fangen wir an!

Warum sind Datenstrukturen hilfreich?

Bevor wir auf die verschiedenen Datenstrukturen eingehen, wollen wir sehen, wie die Verwendung von Datenstrukturen hilfreich sein kann:

• Effiziente Datenverarbeitung: Durch die Wahl der richtigen Datenstruktur lassen sich Daten effektiver verarbeiten. Wenn Sie zum Beispiel eine Sammlung von Elementen desselben Datentyps speichern müssen - mit konstanten Nachschlagezeiten und enger Kopplung - können Sie ein Array wählen.
• Bessere Speicherverwaltung: In größeren Projekten kann für die Speicherung derselben Daten eine Datenstruktur speichereffizienter sein als eine andere. In Python zum Beispiel können sowohl Listen als auch Tupel verwendet werden, um Datensammlungen desselben oder verschiedener Datentypen zu speichern. Wenn Sie jedoch wissen, dass Sie die Sammlung nicht ändern müssen, können Sie ein Tupel wählen, das relativ weniger Speicherplatz benötigt als eine Liste.
• Besser organisierter Code: Durch die Verwendung der richtigen Datenstruktur für eine bestimmte Funktion wird Ihr Code übersichtlicher. Andere Entwickler, die Ihren Code lesen, werden erwarten, dass Sie je nach dem gewünschten Verhalten bestimmte Datenstrukturen verwenden. Ein Beispiel: Wenn Sie eine Schlüssel-Wert-Zuordnung mit konstanten Such- und Einfügezeiten benötigen, können Sie die Daten in einem Wörterbuch speichern.

Verzeichnisse

Wenn es darum geht, dynamische Arrays in Python zu erstellen - sei es in Programmierinterviews oder in allgemeinen Anwendungsfällen - sind Listen die bevorzugten Datenstrukturen.

Python-Listen sind Container-Datentypen, die veränderbar und dynamisch sind. Sie können also Elemente einer Liste an Ort und Stelle hinzufügen oder entfernen, ohne eine Kopie erstellen zu müssen.

Bei der Verwendung von Python-Listen:

• Die Indizierung in der Liste und der Zugriff auf ein Element bei einem bestimmten Index ist eine Operation mit konstanter Zeit.
• Das Hinzufügen eines Elements an das Ende der Liste ist eine Operation mit konstanter Zeit.
•  Das Einfügen eines Elements bei einem bestimmten Index ist eine Operation mit linearer Zeit.

Es gibt eine Reihe von Listenmethoden, die uns helfen, allgemeine Aufgaben effizient auszuführen. Der folgende Codeschnipsel zeigt, wie diese Operationen an einer Beispielliste durchgeführt werden:

>>> nums = [5,4,3,2]

>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]

>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]

>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]

Python-Listen unterstützen auch Slicing und Mitgliedschaftstests mit der in Operator:

>>> nums[1:4]
[5, 4, 3]

>>> 3 in nums
True

Die Listendatenstruktur ist nicht nur flexibel und einfach, sondern ermöglicht auch die Speicherung von Elementen unterschiedlicher Datentypen. Python verfügt auch über eine spezielle Array-Datenstruktur für die effiziente Speicherung von Elementen desselben Datentyps. Wir werden später in diesem Handbuch mehr darüber erfahren.

Tupel

In Python sind Tupel eine weitere beliebte integrierte Datenstruktur. Sie sind wie Python-Listen, da man sie in konstanter Zeit indizieren und zerschneiden kann. Aber sie sind unveränderlichSie können sie also nicht an Ort und Stelle ändern. Der folgende Codeschnipsel erklärt das oben Gesagte anhand eines Beispiels nums Tupel:

>>> nums = (5,4,3,2)

>>> nums[0]
5

>>> nums[0:2]
(5, 4)

>>> 5 in nums
True

>>> nums[0] = 7 # not a valid operation!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Wenn Sie also eine unveränderliche Sammlung erstellen und diese effizient verarbeiten wollen, sollten Sie ein Tupel verwenden. Wenn Sie möchten, dass die Sammlung veränderbar ist, sollten Sie stattdessen eine Liste verwenden.

📋 Erfahren Sie mehr über die Gemeinsamkeiten und Unterschiede zwischen Python-Listen und Tupeln.

Arrays

Arrays sind weniger bekannte Datenstrukturen in Python. Sie ähneln den Python-Listen in Bezug auf die von ihnen unterstützten Operationen, wie z. B. Indizierung in konstanter Zeit und Einfügen eines Elements an einem bestimmten Index in linearer Zeit.

Der Hauptunterschied zwischen Listen und Arrays besteht jedoch darin, dass Arrays die Elemente einer einziger Datentyp. Daher sind sie eng gekoppelt und speichereffizienter.

Um ein Array zu erstellen, können wir die array() Konstruktor aus dem eingebauten array Modul. Die Website array() Konstruktor nimmt eine Zeichenkette auf, die den Datentyp der Elemente und die Elemente angibt. Hier erstellen wir nums_fein Array von Fließkommazahlen:

>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])

Sie können in einem Array indizieren (ähnlich wie bei Python-Listen):

>>> nums_f[0]
1.5

Arrays sind veränderbar, d.h. Sie können sie ändern:

>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])

Aber Sie können ein Element nicht so ändern, dass es eine verschiedene Datentyp:

>>> nums_f[0]='zero'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

Streicher

In Python sind Zeichenketten unveränderlich Sammlungen von Unicode-Zeichen. Im Gegensatz zu Programmiersprachen wie C verfügt Python nicht über einen eigenen Zeichendatentyp. Ein Zeichen ist also auch eine Zeichenkette der Länge eins.

Wie bereits erwähnt, ist die Zeichenfolge unveränderlich:

>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Python-Strings unterstützen String-Slicing und eine Reihe von Methoden, um sie zu formatieren. Hier sind einige Beispiele:

>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'

Denken Sie daran, dass alle oben genannten Operationen eine Kopie der Zeichenkette zurückgeben und die ursprüngliche Zeichenkette nicht verändern. Wenn Sie daran interessiert sind, sehen Sie sich den Leitfaden an Python-Programme zu String-Operationen.

Sätze

In Python, setzt sind Sammlungen von eindeutigen und hashfähigen Elementen. Sie können die üblichen Mengenoperationen wie Vereinigung, Schnittmenge und Differenz durchführen:

>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}

>>> set_1.union(set_2)
{3, 4, 5, 6, 7}

>>> set_1.intersection(set_2)
{4, 7}

>>> set_1.difference(set_2)
{3, 5}

Gruppen sind standardmäßig veränderbar, so dass Sie neue Elemente hinzufügen und sie ändern können:

>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}

📚 Lesen Mengen in Python: Eine vollständige Anleitung mit Codebeispielen

FrozenSets

Wenn Sie eine unveränderliche Menge wünschen, können Sie eine eingefrorene Menge verwenden. Sie können eine unveränderliche Menge aus vorhandenen Mengen oder anderen Iterablen erstellen.

>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})

Denn frozenset_1 eine eingefrorene Menge ist, stoßen wir auf Fehler, wenn wir versuchen, Elemente hinzuzufügen (oder sie anderweitig zu verändern):

>>> frozenset_1.add(15)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

Wörterbücher

Ein Python-Wörterbuch ist funktional ähnlich wie eine Hash-Map. Wörterbücher werden verwendet, um Schlüssel-Wert-Paare zu speichern. Die Schlüssel des Wörterbuchs sollten hashfähig sein. Das bedeutet, dass sich der Hash-Wert des Objekts nicht ändert.

Sie können mit Hilfe von Schlüsseln auf die Werte zugreifen, neue Elemente einfügen und vorhandene Elemente in konstanter Zeit entfernen. Es gibt Wörterbuchmethoden um diese Operationen durchzuführen.

>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}

>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}

>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}

OrderedDict

Obwohl ein Python-Wörterbuch eine Schlüssel-Wert-Zuordnung bietet, ist es von Natur aus eine ungeordnete Datenstruktur. Seit Python 3.7 wird die Reihenfolge des Einfügens von Elementen beibehalten. Sie können dies jedoch explizit machen, indem Sie OrderedDict aus dem Modul Sammlungen.

Wie gezeigt, ist ein OrderedDict behält die Reihenfolge der Schlüssel bei:

>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])

Standarddiktat

Bei der Arbeit mit Python-Wörterbüchern treten häufig Schlüsselfehler auf. Immer, wenn Sie versuchen, auf einen Schlüssel zuzugreifen, der dem Wörterbuch nicht hinzugefügt wurde, wird eine KeyError-Ausnahme ausgelöst.

Aber mit defaultdict aus dem Modul Sammlungenkönnen Sie diesen Fall nativ behandeln. Wenn wir versuchen, auf einen Schlüssel zuzugreifen, der nicht im Wörterbuch vorhanden ist, wird der Schlüssel hinzugefügt und mit den von der Standardfabrik angegebenen Standardwerten initialisiert.

>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0

Stapel

Stack ist ein Last-in-first-out (LIFO) Datenstruktur. Wir können die folgenden Operationen auf einem Stapel durchführen:

• Fügen Sie Elemente oben auf dem Stapel hinzu: drücken. Betrieb 
• Entfernen Sie Elemente vom oberen Ende des Stapels: pop Betrieb 

Ein Beispiel zur Veranschaulichung der Funktionsweise von Stack-Push- und Pop-Operationen:

Implementierung eines Stapels mit Hilfe einer Liste

In Python können wir die Stack-Datenstruktur mit einer Python-Liste implementieren.

Der folgende Codeschnipsel zeigt, wie man das Verhalten eines Stacks mit einer Python-Liste emulieren kann:

>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9

Implementierung eines Stapels mit einer Deque

Eine andere Methode zur Implementierung eines Stacks ist die Verwendung von deque aus dem Modul collections. Deque steht für "double-ended queue" und unterstützt das Hinzufügen und Entfernen von Elementen an beiden Enden.

Um den Stapel zu emulieren, können wir:

• Anhängen an das Ende der Deque mit append()und 
• das letzte hinzugefügte Element mit pop().

>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9

Warteschlangen

Warteschlange ist eine First-in-First-out (FIFO) Datenstruktur. Die Elemente werden am Ende der Warteschlange hinzugefügt und am Anfang der Warteschlange (Kopfende der Warteschlange) wieder entfernt (siehe Abbildung):

Wir können die Datenstruktur der Warteschlange mit einer Deque implementieren:

• Elemente an das Ende der Warteschlange anfügen mit append()
• verwenden Sie die popleft() Methode, um ein Element vom Anfang der Warteschlange zu entfernen

>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4

Haufen

In diesem Abschnitt werden wir binäre Heaps besprechen. Wir konzentrieren uns auf Min-Heaps.

Ein Min-Heap ist ein vollständiger Binärbaum. Lassen Sie uns aufschlüsseln, was ein vollständiger Binärbaum bedeutet:

• A Binärbaum ist eine Baumdatenstruktur, bei der jeder Knoten höchstens zwei Kindknoten hat, so dass jeder Knoten kleiner als sein Kind ist.
• Der Begriff vollständig bedeutet, dass der Baum vollständig ausgefüllt ist, mit Ausnahme vielleicht der letzten Ebene. Wenn die letzte Ebene teilweise gefüllt ist, wird sie von links nach rechts gefüllt.

Denn jeder Knoten hat höchstens zwei Kindknoten. Und außerdem die Eigenschaft erfüllt, dass er kleiner ist als sein Kind, ist die Wurzel ist die minimales Element in einem Minhaufen.

Hier ist ein Beispiel für einen Min-Haufen:

In Python wird die heapq Modul hilft uns, Heaps zu konstruieren und Operationen auf dem Heap durchzuführen. Importieren wir die benötigten Funktionen aus heapq:

>>> from heapq import heapify, heappush, heappop

Wenn Sie eine Liste oder eine andere Iterable haben, können Sie einen Heap daraus konstruieren, indem Sie heapify():

>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)

Sie können das erste Element indizieren, um zu prüfen, ob es das Mindestelement ist:

>>> nums[0]
3

Wenn Sie nun ein Element in den Heap einfügen, werden die Knoten so umgeordnet, dass sie die Eigenschaft min heap erfüllen.

>>> heappush(nums,1)

Da wir 1 eingefügt haben (1 < 3), sehen wir, dass nums[0] gibt 1 zurück, das nun das kleinste Element (und der Wurzelknoten) ist.

>>> nums[0]
1

Sie können Elemente aus dem Min-Heap entfernen, indem Sie die heappop() Funktion wie gezeigt:

>>> while nums:
...     print(heappop(nums))
...

# Output
1
3
7
8
9
10
11
12

Max Heaps in Python

Da Sie nun über Min-Heaps Bescheid wissen, können Sie erraten, wie wir einen Max-Heap implementieren können?

Nun, wir können eine Min-Heap-Implementierung in einen Max-Heap umwandeln, indem wir jede Zahl mit -1 multiplizieren. Negierte Zahlen, die in einem Min Heap angeordnet sind, entsprechen den ursprünglichen Zahlen, die in einem Max Heap angeordnet sind.

In der Python-Implementierung können wir die Elemente mit -1 multiplizieren, wenn wir ein Element zum Heap hinzufügen, indem wir heappush():

>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)

Der Wurzelknoten - multipliziert mit -1 - wird das maximale Element sein. 

>>> -1*maxHeap[0]
7

Wenn Sie die Elemente aus dem Heap entfernen, verwenden Sie heappop() und multiplizieren Sie mit -1, um den ursprünglichen Wert zu erhalten:

>>> while maxHeap:
...     print(-1*heappop(maxHeap))
...

# Output
7
5
2

Vorrangige Warteschlangen

Zum Abschluss der Diskussion lernen wir die Datenstruktur der Prioritätswarteschlange in Python kennen.

Das wissen wir: In einer Warteschlange werden die Elemente in der gleichen Reihenfolge entfernt, in der sie die Warteschlange betreten. Aber eine Priorität Warteschlange bedient Elemente nach Priorität - sehr nützlich für Anwendungen wie die Zeitplanung. Es wird also zu jedem Zeitpunkt das Element mit der höchsten Priorität zurückgegeben.

Wir können Schlüssel verwenden, um die Priorität zu definieren. Hier werden wir numerische Gewichte für die Schlüssel verwenden.

Implementierung von Prioritätswarteschlangen mit Heapq

Hier ist die Implementierung der Prioritätswarteschlange mit heapq und Python-Liste:

>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1,'read'))
>>> heappush(pq,(3,'code'))
>>> while pq:
...     print(heappop(pq))
...

Wenn Elemente entfernt werden, bedient die Warteschlange das Element mit der höchsten Priorität (1,'read') zuerst, gefolgt von (2,'write') und dann (3,'code').

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Implementierung von Prioritätswarteschlangen mit PriorityQueue

Um eine Prioritätswarteschlange zu implementieren, können wir auch die PriorityQueue Klasse aus der Warteschlange Modul. Auch dieses verwendet intern den Heap.

Hier ist die äquivalente Implementierung der Prioritätswarteschlange mit PriorityQueue:

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
...     print(pq.get())
...

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Resümee

In diesem Lernprogramm haben Sie die verschiedenen eingebauten Datenstrukturen in Python kennengelernt. Wir haben auch die verschiedenen Operationen besprochen, die von diesen Datenstrukturen unterstützt werden - und die eingebauten Methoden, um das Gleiche zu tun. 

Anschließend wurden andere Datenstrukturen wie Stapel, Warteschlangen und Prioritäts-Warteschlangen sowie deren Python-Implementierung mithilfe der Funktionen des Collections-Moduls besprochen.

Als nächstes sehen Sie sich die Liste der anfängerfreundliche Python-Projekte.