Datové struktury představují fundamentální stavební kameny v oblasti programování. Umožňují nám organizovat data tak, aby byla efektivně využitelná pro různé operace.
V tomto článku prozkoumáme dva základní typy seznamů: jednosměrně a obousměrně vázané seznamy.
Spojový seznam je lineární datová struktura, která na rozdíl od polí neukládá data do souvislé paměťové oblasti. Každý prvek seznamu, nazývaný uzel, je spojen s dalším uzlem pomocí ukazatelů. První uzel v seznamu se označuje jako hlava.
Výhodou spojového seznamu je jeho dynamická velikost. To znamená, že můžeme přidávat a odebírat uzly dle potřeby, dokud máme k dispozici volnou paměť.
Existují dva hlavní druhy spojových seznamů, které si nyní podrobněji představíme.
#1. Jednosměrně Vázaný Seznam
Jednosměrně vázaný seznam obsahuje pro každý uzel jeden ukazatel, který směřuje na následující uzel v seznamu. Každý uzel tedy musí obsahovat data a ukazatel na následující uzel.
Poslední uzel v seznamu má ukazatel nastavený na hodnotu null (prázdno), což signalizuje konec seznamu.
Níže je ilustrativní znázornění tohoto propojení.
Nyní, když rozumíme konceptu jednosměrně vázaného seznamu, podívejme se, jak ho lze implementovat v jazyce Python.
Implementace Jednosměrně Vázaného Seznamu
1. Prvním krokem je vytvoření struktury pro uzel seznamu.
Jak to udělat?
V Pythonu můžeme uzel snadno definovat pomocí třídy. Třída bude obsahovat data a ukazatel na následující uzel.
Zde je kód pro vytvoření uzlu.
class Node: def __init__(self, data): # Data uložená v uzlu self.data = data # Ukazatel na následující uzel self.next = None
Pomocí této třídy můžeme vytvářet uzly s libovolnými typy dat. Uvidíme, jak na to, za chvíli.
Nyní máme samotný uzel. Dále potřebujeme vytvořit samotný spojový seznam, který bude obsahovat více uzlů. Vytvoříme tedy novou třídu pro reprezentaci spojového seznamu.
2. Vytvořte třídu `LinkedList`, která bude mít jako atribut hlavičku (první uzel) inicializovanou na hodnotu `None`. Viz kód níže.
class LinkedList: def __init__(self): # Inicializace hlavy seznamu na None self.head = None
3. Máme k dispozici třídy `Node` a `LinkedList`. Jak ale vložíme nový uzel do seznamu? Nejjednodušším řešením je vytvořit metodu ve třídě `LinkedList`. To je rozumný nápad. Napišme tedy metodu pro vložení nového uzlu do spojového seznamu.
Při vkládání nového uzlu je třeba provést několik kroků.
Podívejme se na ně:
- Zkontrolujte, zda je hlava seznamu prázdná (tedy má hodnotu None).
- Pokud je hlava prázdná, nový uzel se stane hlavou seznamu.
- Pokud hlava není prázdná, najděte poslední uzel v seznamu.
- Nastavte ukazatel `next` posledního uzlu tak, aby odkazoval na nový uzel.
Zde je kód pro vložení nového uzlu do seznamu.
class LinkedList: #### def insert(self, new_node): # Kontrola, zda je seznam prázdný if self.head: # Získání posledního uzlu last_node = self.head while last_node.next != None: last_node = last_node.next # Připojení nového uzlu na konec last_node.next = new_node else: # Seznam je prázdný # Nastavení nového uzlu jako hlavy seznamu self.head = new_node
Výborně! Dokončili jsme metodu pro vložení nového uzlu do spojového seznamu. Jak ale můžeme přistupovat k datům uloženým v uzlech?
Pro přístup k datům musíme projít celý seznam pomocí ukazatele `next`, stejně jako při hledání posledního uzlu v metodě vkládání. Napišme metodu do třídy `LinkedList`, která vytiskne všechna data uložená v uzlech seznamu.
4. Pro tisk všech dat v seznamu provedeme následující kroky:
- Inicializujte pomocnou proměnnou s hlavou seznamu.
- Použijte cyklus, který bude pokračovat, dokud nedojdeme na konec seznamu.
- Vytiskněte data z aktuálního uzlu.
- Posuňte se na další uzel pomocí ukazatele `next`.
Zde je příslušný kód:
class LinkedList:
####
def display(self):
# Pomocná proměnná pro iteraci
temp_node = self.head
# Iterace přes seznam, dokud nenarazíme na konec
while temp_node != None:
# Tisk dat z uzlu
print(temp_node.data, end='->')
# Přesun na další uzel
temp_node = temp_node.next
print('Null')
Skvělé! Úspěšně jsme vytvořili spojový seznam se všemi potřebnými metodami. Nyní ho otestujeme vytvořením instance a vložením několika dat.
Uzel vytvoříme jednoduše pomocí `Node(1)`. Níže je kompletní kód implementace spojového seznamu, včetně ukázkového použití.
class Node:
def __init__(self, data):
# Data uložená v uzlu
self.data = data
# Ukazatel na následující uzel
self.next = None
class LinkedList:
def __init__(self):
# Inicializace hlavy seznamu na None
self.head = None
def insert(self, new_node):
# Kontrola, zda je seznam prázdný
if self.head:
# Získání posledního uzlu
last_node = self.head
while last_node.next != None:
last_node = last_node.next
# Připojení nového uzlu na konec
last_node.next = new_node
else:
# Seznam je prázdný
# Nastavení nového uzlu jako hlavy seznamu
self.head = new_node
def display(self):
# Pomocná proměnná pro iteraci
temp_node = self.head
# Iterace přes seznam, dokud nenarazíme na konec
while temp_node != None:
# Tisk dat z uzlu
print(temp_node.data, end='->')
# Přesun na další uzel
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
# Vytvoření instance spojového seznamu
linked_list = LinkedList()
# Vkládání dat do seznamu
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))
# Zobrazení seznamu
linked_list.display()
Spuštěním uvedeného programu získáte následující výstup:
1->2->3->4->5->6->7->Null
To je vše, co se týká jednosměrně vázaného seznamu. Nyní víte, jak ho implementovat. S pomocí znalostí o jednosměrně vázaném seznamu můžete snadno implementovat i obousměrně vázaný seznam. Pojďme se tedy vrhnout na další část článku.
#2. Obousměrně Vázaný Seznam
Obousměrně vázaný seznam obsahuje pro každý uzel dva ukazatele. Jeden ukazuje na předchozí uzel a druhý na následující uzel v seznamu. Každý uzel v obousměrně vázaném seznamu tedy musí obsahovat data a dva ukazatele.
Předchozí ukazatel prvního uzlu a následující ukazatel posledního uzlu mají hodnotu null, což signalizuje začátek a konec seznamu.
Níže je ilustrativní znázornění obousměrného seznamu.
Implementace obousměrně vázaného seznamu je podobná implementaci jednosměrně vázaného seznamu. Opětovné vysvětlování stejných kroků by pro vás mohlo být nudné. Projděte si kód krok za krokem, a rychle pochopíte, o co jde. Pojďme na to.
Implementace Obousměrně Vázaného Seznamu
1. Vytvoření uzlu pro obousměrně vázaný seznam s ukazatelem na předchozí uzel, data a ukazatelem na následující uzel.
class Node: def __init__(self, data): # Ukazatel na předchozí uzel self.prev = None # Data uložená v uzlu self.data = data # Ukazatel na následující uzel self.next = None
2. Třída pro reprezentaci obousměrně vázaného seznamu.
class LinkedList: def __init__(self): # Inicializace hlavy seznamu na None self.head = None
3. Metoda pro vložení nového uzlu do obousměrně vázaného seznamu.
class LinkedList: #### def insert(self, new_node): # Kontrola, zda je seznam prázdný if self.head: # Získání posledního uzlu last_node = self.head while last_node.next != None: last_node = last_node.next # Nastavení ukazatele prev nového uzlu na poslední uzel new_node.prev = last_node # Připojení nového uzlu na konec last_node.next = new_node else: # Seznam je prázdný, nový uzel se stane hlavou self.head = new_node
4. Metoda pro zobrazení dat obousměrně vázaného seznamu.
class LinkedList:
####
def display(self):
# Zobrazení dat v normálním pořadí
print("Normální pořadí: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
# Zobrazení dat v obráceném pořadí pomocí ukazatele prev
print("Obrácené pořadí: ", end='')
# Získání posledního uzlu
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 jste kód pro obousměrně vázaný seznam. A nyní je na vás, abyste kód vyzkoušeli! Použijte třídu obousměrně vázaného seznamu podobně jako u jednosměrně vázaného seznamu. Bavte se 🙂
Závěr
Na základě konceptu spojových seznamů lze řešit mnoho problémů. Nicméně musíte mít solidní základy v implementaci, které jste se naučili v tomto článku. Doufám, že se vám nové poznatky líbily.
Přeji vám příjemné kódování 🙂