Le strutture dati giocano un ruolo chiave nel mondo della programmazione. Ci aiutano a organizzare i nostri dati in modo che possano essere utilizzati in modo efficiente.
In questo tutorial, impareremo l’elenco con collegamento singolo e l’elenco con collegamento doppio.
Un elenco collegato è una struttura di dati lineare. Non memorizza i dati in posizioni di memoria contigue come gli array. E ogni elemento in collegato è chiamato nodo e sono collegati usando i puntatori. Il primo nodo nell’elenco collegato è chiamato head.
La dimensione dell’elenco collegato è dinamica. Quindi, possiamo avere qualsiasi numero di nodi che vogliamo a meno che lo spazio di archiviazione non sia disponibile nel dispositivo.
Esistono due tipi di elenchi collegati. Vediamo il tutorial dettagliato su di loro uno per uno.
Sommario:
#1. Elenco collegato singolarmente
Un elenco collegato singolarmente contiene un singolo puntatore connesso al nodo successivo nell’elenco collegato. Dobbiamo memorizzare i dati e il puntatore per ogni nodo nell’elenco collegato.
L’ultimo nodo nell’elenco collegato contiene null come puntatore successivo per rappresentare la fine dell’elenco collegato.
Puoi vedere l’illustrazione di un link qui sotto.
Ora, abbiamo una piena comprensione di un elenco collegato singolarmente. Vediamo i passaggi per implementarlo in Python.
Implementazione di elenchi collegati singolarmente
1. Il primo passaggio consiste nel creare il nodo per l’elenco collegato.
Come crearlo?
In Python, possiamo facilmente creare il nodo usando la classe. La classe contiene dati e un puntatore per il nodo successivo.
Guarda il codice per il nodo.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Possiamo creare il nodo con qualsiasi tipo di dati utilizzando la classe precedente. Lo vedremo tra un po’.
Ora abbiamo il nodo con noi. Successivamente, dobbiamo creare un elenco collegato con più nodi. Creiamo un’altra classe per un elenco collegato.
2. Creare una classe denominata LinkedList con head inizializzata su None. Vedi il codice qui sotto.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Abbiamo con noi le classi Node e LinkedList. Come inseriamo un nuovo nodo nell’elenco collegato? Una semplice risposta potrebbe essere l’utilizzo di un metodo nella classe LinkedList. Sì, sarebbe bello. Scriviamo un metodo per inserire un nuovo nodo nell’elenco collegato.
Per inserire un nuovo nodo nell’elenco collegato, dobbiamo seguire alcuni passaggi.
Vediamoli.
- Controlla se la testa è vuota o no.
- Se la testa è vuota, assegna il nuovo nodo alla testa.
- Se l’intestazione non è vuota, ottieni l’ultimo nodo dell’elenco collegato.
- Assegna il nuovo nodo al puntatore next dell’ultimo nodo.
Vediamo il codice per inserire un nuovo nodo nella lista collegata.
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
Evviva! abbiamo completato il metodo per inserire un nuovo nodo nella lista collegata. Come possiamo accedere ai dati dei nodi dall’elenco collegato?
Per accedere ai dati dall’elenco collegato, dobbiamo iterare attraverso il collegamento utilizzando il puntatore successivo come facciamo per ottenere l’ultimo nodo nel metodo di inserimento. Scriviamo un metodo all’interno della classe LinkedList per stampare tutti i dati dei nodi nella lista collegata.
4. Seguire i passaggi seguenti per stampare tutti i dati dei nodi nell’elenco collegato.
- Inizializza una variabile con head.
- Scrivi un ciclo che itera finché non raggiungiamo la fine dell’elenco collegato.
- Stampa i dati del nodo.
- Sposta il puntatore successivo
Vediamo il codice.
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')
Uff! abbiamo completato la creazione del collegamento con i metodi necessari. Testiamo l’elenco collegato istanziandolo con alcuni dati.
Possiamo creare il nodo con il codice Node(1). Vediamo il codice completo dell’implementazione dell’elenco collegato insieme all’utilizzo di esempio.
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()
Eseguire il programma precedente per ottenere il seguente risultato.
1->2->3->4->5->6->7->Null
Questo è tutto per l’elenco collegato. Ora sai come implementare un elenco con collegamento singolo. Puoi implementare facilmente l’elenco a doppio collegamento con la conoscenza dell’elenco a collegamento singolo. Passiamo alla sezione successiva del tutorial.
#2. Elenco doppiamente collegato
Un elenco a doppio collegamento contiene due puntatori collegati al nodo precedente e al nodo successivo nell’elenco collegato. Dobbiamo memorizzare i dati e due puntatori per ogni nodo nell’elenco collegato.
Il puntatore precedente del primo nodo è nullo e il puntatore successivo dell’ultimo nodo è nullo per rappresentare la fine dell’elenco collegato su entrambi i lati.
Puoi vedere l’illustrazione di un link qui sotto.
L’elenco a doppio collegamento ha anche passaggi simili a quelli dell’elenco a collegamento singolo nell’implementazione. Di nuovo spiegare le stesse cose sarà noioso per te. Esamina il codice in ogni passaggio e lo capirai molto rapidamente. Andiamo.
Implementazione di elenchi doppiamente collegati
1. Creazione di un nodo per l’elenco a doppio collegamento con il puntatore del nodo precedente, i dati e il puntatore del nodo successivo.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Classe elenco doppiamente collegato.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Un metodo per inserire un nuovo nodo nell’elenco doppiamente collegato.
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. Un metodo per visualizzare i dati dell’elenco doppiamente collegati.
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()
Abbiamo visto il codice della lista doppiamente collegata. E non c’è codice per l’utilizzo della classe lista doppiamente collegata. Questo è per te. Utilizzare la classe dell’elenco a doppio collegamento simile all’elenco a collegamento singolo. Divertiti 🙂
Conclusione
Puoi trovare molti problemi basati su elenchi collegati. Ma devi conoscere l’implementazione di base del collegamento che hai imparato in questo tutorial. Spero ti sia divertito ad apprendere il nuovo concetto.
Buona programmazione 🙂