Pochopení implementace propojených seznamů v Pythonu

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.

#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.

  Jak obnovit účet Kik

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.

  Upravte zaostření a intenzitu efektu rozostření v aplikaci Fotoaparát Google

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 🙂

  Jak používat více e-mailových podpisů v Gmailu

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í 🙂

x