Datové struktury hrají klíčovou roli ve světě programování. Pomáhají nám organizovat naše data způsobem, který lze efektivně využít.
V tomto tutoriálu se seznámíme s jednoduše propojeným a dvojitě propojeným seznamem.
Propojený seznam je lineární datová struktura. Neukládá data do souvislých paměťových míst, jako jsou pole. A každý propojený prvek se nazývá uzel a jsou spojeny pomocí ukazatelů. První uzel v propojeném seznamu se nazývá hlava.
Velikost propojeného seznamu je dynamická. Můžeme tedy mít libovolný počet uzlů, pokud není v zařízení k dispozici úložiště.
Existují dva typy propojených seznamů. Podívejme se na podrobný tutoriál o nich jeden po druhém.
Table of Contents
#1. Jednotlivě propojený seznam
Jednotlivě propojený seznam obsahuje jeden ukazatel připojený k dalšímu uzlu v propojeném seznamu. Musíme uložit data a ukazatel pro každý uzel v propojeném seznamu.
Poslední uzel v propojeném seznamu obsahuje null jako další ukazatel představující konec propojeného seznamu.
Níže můžete vidět ilustraci odkazu.
Nyní plně rozumíme jednoduše propojenému seznamu. Podívejme se na kroky k jeho implementaci v Pythonu.
Implementace jednoduše propojeného seznamu
1. Prvním krokem je vytvoření uzlu pro propojený seznam.
Jak ji vytvořit?
V Pythonu můžeme snadno vytvořit uzel pomocí třídy. Třída obsahuje data a ukazatel na další uzel.
Podívejte se na kód uzlu.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Pomocí výše uvedené třídy můžeme vytvořit uzel s libovolným typem dat. Uvidíme za chvíli.
Nyní máme uzel u sebe. Dále musíme vytvořit propojený seznam s více uzly. Vytvořme další třídu pro propojený seznam.
2. Vytvořte třídu nazvanou LinkedList s hlavičkou inicializovanou na None. Viz kód níže.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Máme s sebou třídy Node a LinkedList. Jak vložíme nový uzel do propojeného seznamu? Jednoduchou odpovědí může být použití metody ve třídě LinkedList. Jo, to by bylo hezké. Pojďme napsat metodu pro vložení nového uzlu do propojeného seznamu.
Chcete-li vložit nový uzel do propojeného seznamu, musíme provést určité kroky.
Pojďme se na ně podívat.
- Zkontrolujte, zda je hlava prázdná nebo ne.
- Pokud je hlava prázdná, přiřaďte nový uzel hlavě.
- Pokud záhlaví není prázdné, získejte poslední uzel propojeného seznamu.
- Přiřaďte nový uzel poslednímu uzel dalšímu ukazateli.
Podívejme se na kód pro vložení nového uzlu do propojeného seznamu.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
Hurá! dokončili jsme metodu vložení nového uzlu do propojeného seznamu. Jak můžeme přistupovat k datům uzlů z propojeného seznamu?
Abychom získali přístup k datům z propojeného seznamu, musíme iterovat propojeným pomocí dalšího ukazatele, jak to děláme, abychom získali poslední uzel v metodě vkládání. Pojďme napsat metodu uvnitř třídy LinkedList pro tisk všech dat uzlů v propojeném seznamu.
4. Podle níže uvedených kroků vytiskněte všechna data uzlů v propojeném seznamu.
- Inicializujte proměnnou s hlavou.
- Napište smyčku, která se opakuje, dokud nedosáhneme konce propojeného seznamu.
- Vytiskněte data uzlu.
- Posuňte další ukazatel
Podívejme se na kód.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
Fuj! dokončili jsme vytvoření propojeného s potřebnými metodami. Pojďme otestovat propojený seznam vytvořením instance s některými daty.
Uzel můžeme vytvořit pomocí kódu Node(1). Podívejme se na úplný kód implementace propojeného seznamu spolu s ukázkovým použitím.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## printing the linked list
linked_list.display()
Spusťte výše uvedený program a získejte následující výsledek.
1->2->3->4->5->6->7->Null
To je pro propojený seznam vše. Nyní víte, jak implementovat jednoduše propojený seznam. Dvojitě propojený seznam můžete snadno implementovat se znalostí jednoduše propojeného seznamu. Pojďme se ponořit do další části tutoriálu.
#2. Dvojitě propojený seznam
Dvojitě propojený seznam obsahuje dva ukazatele připojené k předchozímu uzlu a dalšímu uzlu v propojeném seznamu. Musíme uložit data a dva ukazatele pro každý uzel v propojeném seznamu.
Předchozí ukazatel prvního uzlu je nulový a další ukazatel posledního uzlu je nulový pro reprezentaci konce propojeného seznamu na obou stranách.
Níže můžete vidět ilustraci odkazu.
Dvojitě propojený seznam má také při implementaci podobné kroky jako jednoduše propojený seznam. Opět vysvětlování stejných věcí pro vás bude nuda. Projděte si kód v každém kroku a velmi rychle jej pochopíte. Pojďme.
Implementace dvojitě propojeného seznamu
1. Vytvoření uzlu pro dvojitě propojený seznam s ukazatelem předchozího uzlu, daty a ukazatelem dalšího uzlu.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Dvojitě propojená třída seznamu.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Metoda pro vložení nového uzlu do dvojitě propojeného seznamu.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Metoda zobrazení dat dvojitě propojeného seznamu.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Viděli jsme kód dvojitě propojeného seznamu. A neexistuje žádný kód pro použití třídy dvojitě propojeného seznamu. To je pro tebe. Použijte třídu dvojitě propojeného seznamu podobnou jednoduše propojenému seznamu. Bavte se 🙂
Závěr
Na základě propojených seznamů můžete najít mnoho problémů. Musíte však znát základní implementaci propojeného, které jste se naučili v tomto tutoriálu. Doufám, že se vám učení nového konceptu líbilo.
Veselé kódování 🙂