Implementazione di elenchi concatenati singolarmente in Python
Scopri come implementare un elenco collegato singolarmente in Python. Esplora l'allocazione dinamica della memoria, le operazioni dei nodi, l'inserimento, l'attraversamento e l'eliminazione.
Panoramica
Una lista concatenata è una struttura di dati lineare in cui gli elementi non sono archiviati in posizioni di memoria contigue. Invece, ogni elemento (chiamato nodo) è un oggetto separato che contiene un riferimento al nodo successivo nella sequenza.
Il vantaggio principale di una lista concatenata rispetto a un array tradizionale è il suo dimensionamento dinamico e la possibilità di inserire o eliminare elementi in un tempo O(1) costante all'inizio. Tuttavia, l'accesso agli elementi tramite indice richiede un attraversamento lineare, che richiede tempo O(n).
In Python, implementiamo una lista concatenata definendo una classe Node per memorizzare i dati e il puntatore di riferimento, e una classe LinkedList per gestire il nodo head, gli inserimenti in testa o in coda e le cancellazioni.
Codice e output di esecuzione
Implementazione di elenchi collegati singolarmente in Python, che mostra la creazione di nodi, l'aggiunta e l'attraversamento di elenchi.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def delete(self, key):
curr = self.head
if curr and curr.data == key:
self.head = curr.next
curr = None
return
prev = None
while curr and curr.data != key:
prev = curr
curr = curr.next
if not curr:
return
prev.next = curr.next
curr = None
def display(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
print(" -> ".join(elements) + " -> None")
# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()
print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> NoneImplementazione passo dopo passo
- Implementazione della funzionalità di annullamento-ripristino negli editor di testo
- Costruire strutture dati complesse come grafici, stack e code
- Gestione di elenchi in cui le frequenze di inserimento e cancellazione superano le azioni di ricerca
Domande frequenti
Qual è la differenza tra elenchi collegati singolarmente e doppiamente?
In un elenco collegato singolarmente, ciascun nodo punta solo al nodo successivo. In una lista doppiamente collegata, ogni nodo contiene riferimenti sia al nodo successivo che a quello precedente, consentendo l'attraversamento bidirezionale al costo di memoria aggiuntiva.
Perché Python non ha una classe LinkedList incorporata?
Gli array (elenchi) Python sono implementati come array dinamici. Grazie alla gestione della memoria di Python e alle ottimizzazioniCPython, gli elenchi standard sono estremamente veloci ed efficienti per la maggior parte delle attività, riducendo la necessità pratica di un elenco collegato integrato.
Argomenti correlati
Implementa uno stack LIFO in Python. Esegui il nostro esempio di codice stack interattivo per padroneggiare i limiti di push, pop, peek e capacità.
Tutorial sulla struttura dei dati della coda PythonMaster operazioni coda FIFO in Python. Esegui ed esegui il nostro esempio di coda interattiva che mostra i metodi di accodamento e rimozione dalla coda.