In questo articolo impareremo l'implementazione di un elenco collegato in Pitone . Per implementare l'elenco collegato in Python, utilizzeremo classi in Python . Ora, sappiamo che una lista collegata è composta da nodi e i nodi hanno due elementi, ovvero dati e un riferimento a un altro nodo. Implementiamo prima il nodo.
Cos'è la lista collegata in Python
Un elenco collegato è un tipo di struttura dati lineare simile agli array. È una raccolta di nodi collegati tra loro. Un nodo contiene due cose: la prima sono i dati e la seconda è un collegamento che lo collega ad un altro nodo. Di seguito è riportato un esempio di un elenco collegato con quattro nodi e ciascun nodo contiene dati sui caratteri e un collegamento a un altro nodo. Il nostro primo nodo è dove Testa punti e possiamo accedere a tutti gli elementi dell'elenco collegato utilizzando il file Testa.
Lista collegata
Creazione di un elenco collegato in Python
In questa classe LinkedList utilizzeremo la classe Node per creare un elenco collegato. In questa classe abbiamo un __caldo__ metodo che inizializza l'elenco collegato con un'intestazione vuota. Successivamente, abbiamo creato un file insertAtBegin() metodo per inserire un nodo all'inizio dell'elenco collegato, an insertAtIndex() metodo per inserire un nodo all'indice dato della lista collegata, e insertAtEnd() Il metodo inserisce un nodo alla fine dell'elenco collegato. Dopodiché, abbiamo il rimuovi_nodo() metodo che accetta i dati come argomento per eliminare quel nodo. Nel rimuovi_nodo() metodo attraversiamo la lista concatenata se è presente un nodo uguale ai dati allora eliminiamo quel nodo dalla lista concatenata. Poi abbiamo il dimensioneOfLL() metodo per ottenere la dimensione corrente dell'elenco collegato e l'ultimo metodo della classe LinkedList è stampaLL() che attraversa la lista concatenata e stampa i dati di ciascun nodo.
Creazione di una classe di nodo
Abbiamo creato una classe Node in cui abbiamo definito a __caldo__ funzione per inizializzare il nodo con i dati passati come argomento e un riferimento con None perché se abbiamo un solo nodo allora non c'è nulla nel suo riferimento.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Inserimento in Linked List
Inserimento all'inizio della lista collegata
Questo metodo inserisce il nodo all'inizio dell'elenco collegato. In questo metodo, creiamo a nuovo_nodo con il dato dati e controlla se la testa è un nodo vuoto o no, se la testa è vuota allora creiamo il file nuovo_nodo COME Testa E ritorno altrimenti inseriamo la testa al successivo nuovo_nodo e fare il Testa uguale a nuovo_nodo.
Python3
def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> |
elaborazione dell'hacking
>
>
Inserisci un nodo in una posizione specifica in un elenco collegato
Questo metodo inserisce il nodo in corrispondenza dell'indice specificato nell'elenco collegato. In questo metodo, creiamo a nuovo_nodo con dati forniti, un current_node uguale a head e un contatore 'posizione' inizializza con 0. Ora, se l'indice è uguale a zero significa che il nodo deve essere inserito all'inizio così abbiamo chiamato metodo insertAtBegin() altrimenti eseguiamo un ciclo while fino al nodo_corrente non è uguale a Nessuno O (posizione+1) non è uguale all'indice che dobbiamo inserire in una determinata posizione in una determinata posizione per effettuare il collegamento dei nodi e in ogni iterazione incrementiamo la posizione di 1 e creiamo il nodo_corrente il prossimo. Quando il loop si interrompe e se nodo_corrente non è uguale a Nessuno inseriamo new_node dopo nel file nodo_corrente. Se nodo_corrente è uguale a Nessuno significa che l'indice non è presente nella lista e stampiamo Indice non presente.
Python3
# Indexing starts from 0.> def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> |
>
>
Inserimento in Linked List alla fine
Questo metodo inserisce il nodo alla fine dell'elenco collegato. In questo metodo, creiamo a nuovo_nodo con i dati forniti e controlla se il Testa è un nodo vuoto o meno se il file Testa è vuoto, allora creiamo il file nuovo_nodo COME Testa E ritorno altro facciamo a nodo_corrente uguale A la testa traversare fino all'ultimo nodo dell'elenco collegato e quando otteniamo Nessuno dopo il current_node il ciclo while si interrompe e inserisce il file nuovo_nodo nel prossimo di nodo_corrente che è l'ultimo nodo della lista concatenata.
Python3
def> inserAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> |
>
>
Aggiorna il nodo di una lista collegata
Questo codice definisce un metodo chiamato updateNode in una classe di elenco collegato. Viene utilizzato per aggiornare il valore di un nodo in una determinata posizione nell'elenco collegato.
Python3
# Update node of a linked list> # at given position> def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> |
>
>
Elimina nodo in un elenco collegato
Rimuovi il primo nodo dall'elenco collegato
Questo metodo rimuove il primo nodo dell'elenco collegato semplicemente creando il secondo nodo Testa dell'elenco collegato.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
leggere da csv java
>
Rimuovi l'ultimo nodo dall'elenco collegato
In questo metodo, elimineremo l'ultimo nodo. Innanzitutto, attraversiamo il penultimo nodo utilizzando il ciclo while, quindi creiamo il successivo di quel nodo Nessuno e l'ultimo nodo verrà rimosso.
Python3
def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> |
>
>
Elimina un nodo della lista collegata in una determinata posizione
In questo metodo rimuoveremo il nodo in corrispondenza dell'indice specificato, questo metodo è simile a IL insert_at_inded() metodo. In questo metodo, se il Testa È Nessuno noi semplicemente ritorno altrimenti inizializziamo a nodo_corrente con sé.testa E posizione con 0. Se la posizione è uguale all'indice che abbiamo chiamato rimuovi_primo_nodo() altrimenti passiamo al nodo prima che vogliamo rimuovere usando il ciclo while. Dopodiché, quando usciamo dal ciclo while, controlliamo quel nodo_corrente è uguale a Nessuno in caso contrario rendiamo il successivo di current_node uguale al successivo del nodo che vogliamo rimuovere altrimenti stampiamo il messaggio Indice non presente Perché nodo_corrente è uguale a Nessuno.
Python3
# Method to remove at given index> def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> |
>
>
Elimina un nodo dell'elenco collegato di un dato dato
Questo metodo rimuove il nodo con i dati specificati dall'elenco collegato. In questo metodo, innanzitutto abbiamo creato a nodo_corrente uguale a Testa ed esegui a ciclo while per attraversare l'elenco collegato. Questo ciclo while si interrompe quando nodo_corrente diventa Nessuno oppure i dati accanto al nodo corrente sono uguali ai dati forniti nell'argomento. Ora, dopo essere uscito dal giro se il nodo_corrente è uguale a Nessuno significa che il nodo non è presente nei dati e dobbiamo semplicemente restituire, e se i dati accanto a nodo_corrente è uguale ai dati forniti, quindi rimuoviamo quel nodo trasformando il successivo nodo_rimosso nel successivo nodo_corrente. E questo viene implementato utilizzando la condizione if else.
Python3
def> remove_node(>self>, data):> >current_node>=> self>.head> ># Check if the head node contains the specified data> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while> current_node>is> not> None> and> current_node.>next>.data !>=> data:> >current_node>=> current_node.>next> >if> current_node>is> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> |
>
>
Attraversamento di elenchi collegati in Python
Questo metodo attraversa l'elenco collegato e stampa i dati di ciascun nodo. In questo metodo, abbiamo creato a nodo_corrente uguale a Testa e scorrere l'elenco collegato utilizzando a ciclo while fino al nodo_corrente diventa None e stampa i dati di nodo_corrente in ogni iterazione e crea il file nodo_corrente Vicino a esso.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Ottieni la lunghezza di un elenco collegato in Python
Questo metodo restituisce la dimensione dell'elenco collegato. In questo metodo, abbiamo inizializzato un contatore 'misurare' con 0, e poi se head non è uguale a None attraversiamo la lista concatenata utilizzando a ciclo while e incrementare il misurare con 1 in ogni iterazione e restituisce la dimensione quando nodo_corrente diventa Nessun altro restituiamo 0.
Python3
def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> |
>
>
Esempio dell'elenco collegato in Python
In questo esempio, dopo aver definito la classe Node e LinkedList, abbiamo creato un elenco collegato denominato llist utilizzando la classe elenco collegato e quindi inserire quattro nodi con dati carattere ‘a’, ‘b’, ‘c’, ‘d’ E 'G' nell'elenco collegato, quindi stampiamo l'elenco collegato utilizzando stampaLL() metodo della classe elenco collegato, dopodiché abbiamo rimosso alcuni nodi utilizzando i metodi di rimozione e quindi stampare nuovamente l'elenco collegato e possiamo vedere nell'output che il nodo è stato eliminato con successo. Successivamente, stampiamo anche la dimensione dell'elenco collegato.
Python3
Java se altro
# Create a Node class to create a node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> # Create a LinkedList class> class> LinkedList:> >def> __init__(>self>):> >self>.head>=> None> ># Method to add a node at begin of LL> >def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> ># Method to add a node at any index> ># Indexing starts from 0.> >def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> ># Method to add a node at the end of LL> >def> insertAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> ># Update node of a linked list> ># at given position> >def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> ># Method to remove first node of linked list> >def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> >self>.head>=> self>.head.>next> ># Method to remove last node of linked list> >def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> ># Method to remove at given index> >def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> ># Method to remove a node from linked list> >def> remove_node(>self>, data):> >current_node>=> self>.head> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while>(current_node !>=> None> and> current_node.>next>.data !>=> data):> >current_node>=> current_node.>next> >if> current_node>=>=> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> ># Print the size of linked list> >def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> ># print method for the linked list> >def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> # create a new linked list> llist>=> LinkedList()> # add nodes to the linked list> llist.insertAtEnd(>'a'>)> llist.insertAtEnd(>'b'>)> llist.insertAtBegin(>'c'>)> llist.insertAtEnd(>'d'>)> llist.insertAtIndex(>'g'>,>2>)> # print the linked list> print>(>'Node Data'>)> llist.printLL()> # remove a nodes from the linked list> print>(>'
Remove First Node'>)> llist.remove_first_node()> print>(>'Remove Last Node'>)> llist.remove_last_node()> print>(>'Remove Node at Index 1'>)> llist.remove_at_index(>1>)> # print the linked list again> print>(>'
Linked list after removing a node:'>)> llist.printLL()> print>(>'
Update node Value'>)> llist.updateNode(>'z'>,>0>)> llist.printLL()> print>(>'
Size of linked list :'>, end>=>' '>)> print>(llist.sizeOfLL())> |
>
>Produzione
Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2>