Structurile de date joacă un rol cheie în lumea programării. Ele ne ajută să ne organizăm datele într-un mod care poate fi utilizat eficient.
În acest tutorial, vom afla despre lista cu linkuri simple și lista cu linkuri duble.
O listă legată este o structură de date liniară. Nu stochează datele în locații de memorie adiacente, cum ar fi matrice. Și fiecare element din linked se numește nod și sunt conectați folosind pointerii. Primul nod din lista legată se numește cap.
Mărimea listei legate este dinamică. Deci, putem avea orice număr de noduri după cum ne dorim, cu excepția cazului în care stocarea este disponibilă în dispozitiv.
Există două tipuri de liste legate. Să vedem tutorialul detaliat despre ele unul câte unul.
Cuprins
#1. Lista legată individual
O listă legată individual conține un singur pointer conectat la următorul nod din lista legată. Trebuie să stocăm datele și pointerul pentru fiecare nod din lista legată.
Ultimul nod din lista legată conține null ca următor indicator pentru a reprezenta sfârșitul listei legate.
Puteți vedea ilustrația unui link de mai jos.
Acum, avem o înțelegere completă a unei liste conectate individual. Să vedem pașii pentru a-l implementa în Python.
Implementarea listelor conectate individual
1. Primul pas este crearea nodului pentru lista legată.
Cum să o creez?
În Python, putem crea cu ușurință nodul folosind clasa. Clasa conține date și un pointer pentru următorul nod.
Uită-te la codul nodului.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Putem crea nodul cu orice tip de date folosind clasa de mai sus. O să vedem în scurt timp.
Acum, avem nodul cu noi. În continuare, trebuie să creăm o listă legată cu mai multe noduri. Să creăm o altă clasă pentru o listă legată.
2. Creați o clasă numită LinkedList cu capul inițializat la None. Vezi codul de mai jos.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Avem la noi clasele Node și LinkedList. Cum inserăm un nou nod în lista legată? Un răspuns simplu ar putea fi utilizarea unei metode din clasa LinkedList. Da, ar fi frumos. Să scriem o metodă pentru a insera un nou nod în lista legată.
Pentru a insera un nou nod în lista legată, trebuie să urmam anumiți pași.
Să-i vedem.
- Verificați dacă capul este gol sau nu.
- Dacă capul este gol, atunci atribuiți noul nod capului.
- Dacă capul nu este gol, obțineți ultimul nod al listei legate.
- Atribuiți noul nod ultimului nod următor indicator.
Să vedem codul pentru a insera un nou nod în lista legată.
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
Ura! am finalizat metoda de inserare a unui nou nod în lista legată. Cum putem accesa datele nodurilor din lista legată?
Pentru a accesa datele din lista legată, trebuie să iterăm prin linked folosind următorul pointer așa cum facem pentru a obține ultimul nod în metoda de inserare. Să scriem o metodă în clasa LinkedList pentru a tipări toate datele nodurilor din lista legată.
4. Urmați pașii de mai jos pentru a imprima toate datele nodurilor din lista legată.
- Inițializați o variabilă cu cap.
- Scrieți o buclă care se repetă până ajungem la sfârșitul listei legate.
- Tipăriți datele nodului.
- Mutați următorul indicator
Să vedem codul.
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')
Pf! am finalizat crearea link-ului cu metodele necesare. Să testăm lista legată prin instanțierea acesteia cu câteva date.
Putem crea nodul cu codul Node(1). Să vedem codul complet al implementării listei legate împreună cu exemplul de utilizare.
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()
Rulați programul de mai sus pentru a obține următorul rezultat.
1->2->3->4->5->6->7->Null
Asta este pentru lista legată. Acum, știți cum să implementați o listă unică. Puteți implementa cu ușurință lista dublu legată cu cunoștințele listei cu legătură unică. Să trecem la următoarea secțiune a tutorialului.
#2. Listă dublu legată
O listă dublu legată conține doi pointeri conectați la nodul anterior și următorul nod din lista legată. Trebuie să stocăm datele și doi pointeri pentru fiecare nod din lista legată.
Pointerul anterior al primului nod este nul și următorul pointer al ultimului nod este nul pentru a reprezenta sfârșitul listei legate de ambele părți.
Puteți vedea ilustrația unui link de mai jos.
Lista dublu legată are, de asemenea, pași similari cu lista cu legături unice în implementare. Din nou explicarea acelorași lucruri va fi plictisitor pentru tine. Parcurgeți codul la fiecare pas și îl veți înțelege foarte repede. Sa mergem.
Implementarea listei dublu legate
1. Crearea unui nod pentru lista dublu legată cu indicatorul de nod anterior, datele și indicatorul de nod următor.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Clasă de listă dublu legată.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. O metodă de a insera un nou nod în lista dublu legată.
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. O metodă de afișare a datelor listei dublu legate.
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()
Am văzut codul listei dublu legate. Și nu există niciun cod pentru utilizarea clasei de listă dublu legată. Asta e pentru tine. Utilizați clasa de listă cu legături duble, similară listei cu legături simple. Distreaza-te 🙂
Concluzie
Puteți găsi multe probleme pe baza listelor legate. Dar, trebuie să cunoașteți implementarea de bază a link-ului pe care l-ați învățat în acest tutorial. Sper că v-ați distrat de minune învățând noul concept.
Codare fericită 🙂