Classe Node e costruzione delle liste
Definisca una dataclass Node, costruisca liste collegando manualmente i nodi e scriva helper insert/delete/print per visualizzare i cambiamenti dei puntatori
Classe Node e costruzione delle liste è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Che cos'è una lista concatenata?
Una lista concatenata è una sequenza di nodi in cui ogni nodo memorizza un valore e un puntatore al nodo successivo. A differenza degli array, i nodi sono sparsi in memoria: non esiste un accesso O(1) basato sull'indice. In compenso, è possibile inserire ed eliminare elementi in O(1) in qualsiasi posizione nota, senza spostare gli elementi.
In Python ogni nodo è rappresentato da una piccola classe che contiene val e next. Collegando i nodi tra loro si forma la lista; il next dell'ultimo nodo è None per segnalare la fine.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Costruire liste a partire da array
Nei colloqui tecnici viene spesso fornita una lista e viene richiesto di costruirne l'equivalente come lista concatenata, o viceversa. Le funzioni di supporto build e to_list sono da memorizzare: build collega i nodi a partire da un array, mentre to_list percorre la lista per raccogliere i valori e facilitarne la verifica.
Costruire una lista concatenata a partire da n elementi richiede tempo O(n) e spazio O(n). Usare un nodo testa fittizia semplifica i casi limite in cui il primo nodo può cambiare.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Inserimento in testa e in coda
Inserire un nuovo nodo in testa richiede O(1): creare il nodo, puntare il suo next alla vecchia testa e restituire il nuovo nodo come testa. Inserire in coda richiede di percorrere la lista fino all'ultimo nodo (O(n)) e quindi collegare il nuovo nodo.
Usare un nodo testa fittizia elimina il caso speciale della lista vuota per entrambe le operazioni, perché dummy.next è sempre la vera testa.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneEliminare un nodo in base al valore
Per eliminare il primo nodo con un determinato valore, mantenere un puntatore prev una posizione prima di curr. Quando curr.val == target, impostare prev.next = curr.next per saltare il nodo. Una testa fittizia è particolarmente utile perché elimina il caso speciale dell'eliminazione della vera testa: prev può sempre partire dalla testa fittizia.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Visualizzare le modifiche ai puntatori
Un errore comune consiste nel perdere il riferimento a un nodo durante l'aggiornamento dei puntatori. Salvare sempre next prima di sovrascriverlo: saved = curr.next, quindi riassegnarlo. Disegnare la lista come riquadri collegati da frecce e simulare ogni aggiornamento dei puntatori su carta prima di scrivere il codice. Questo approccio visivo previene gli errori accidentali di puntatore nullo durante i colloqui tecnici.
Ricordi: in Python, riassegnare curr.next non influisce su curr, ma perdere il riferimento a curr.next prima di averlo salvato impedisce di proseguire l'attraversamento in avanti.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Liste semplici e doppiamente concatenate
Una lista semplicemente concatenata memorizza solo un puntatore next; l'attraversamento è unidirezionale. Una lista doppiamente concatenata memorizza sia prev sia next, consentendo l'attraversamento all'indietro in O(1) e l'eliminazione in O(1) dato un riferimento diretto al nodo, senza il ciclo che tiene traccia di prev.
collections.deque di Python è implementato come una lista doppiamente concatenata, per questo supporta appendleft e popleft in O(1). Nei colloqui tecnici si implementano liste semplicemente concatenate; le liste doppiamente concatenate compaiono nella progettazione di cache LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Funzioni di supporto per lunghezza, coda e stampa
Tre funzioni di utilità da tenere a disposizione durante qualsiasi colloquio tecnico sulle liste concatenate: length(head) conta i nodi in O(n), tail(head) restituisce l'ultimo nodo in O(n) e print_list(head) formatta la lista per il debug. Averle già pronte consente di concentrarsi sull'algoritmo principale invece di reimplementare la logica di supporto.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Impostazione dei due puntatori sulle liste concatenate
La tecnica dei due puntatori è importante per le liste concatenate quanto lo è per gli array, ma i puntatori sono nodi della lista concatenata anziché indici. Le configurazioni più comuni includono una coppia di puntatori lento e veloce (il puntatore veloce si muove a una velocità doppia) per trovare i punti centrali e rilevare i cicli, e una coppia predecessore e corrente per l'eliminazione e l'inversione.
Inizializzare sempre entrambi i puntatori in modo esplicito e gestire con attenzione il controllo della terminazione nulla: fast and fast.next previene gli errori di puntatore nullo quando fast è vicino alla fine.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Il pattern della testa fittizia
Il pattern della testa fittizia (nodo sentinella) è uno dei trucchi più utili nei problemi sulle liste concatenate. Anteponendo un nodo fittizio con valore 0, non è mai necessario gestire separatamente una lista vuota o una modifica della vera testa. Il risultato è sempre dummy.next. Questo pattern compare nella fusione di liste ordinate, nella rimozione dell'n-esimo elemento dalla fine, nel partizionamento di una lista e in molti altri problemi.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Complessità temporale e spaziale
La maggior parte delle operazioni sulle liste concatenate ha le seguenti complessità. Accesso tramite indice: O(n), perché è necessario attraversare la lista dalla testa. Inserimento/eliminazione in corrispondenza di un nodo noto: O(1), perché basta ricollegare i puntatori. Inserimento/eliminazione in posizione k: O(k), perché è necessario attraversare prima la lista. Ricerca: O(n), nel caso peggiore l'intera lista. Lo spazio è O(1) per tutte le operazioni sul posto, escluse le strutture dati aggiuntive.
Rispetto agli array, gli array offrono accesso in O(1), ma l'inserimento e l'eliminazione richiedono O(n) a causa dello spostamento degli elementi. Le liste concatenate sono migliori quando gli inserimenti e le eliminazioni in posizioni arbitrarie sono frequenti.
Consigli per i colloqui sulle liste concatenate
Prima di scrivere codice per una lista concatenata, disegnare visivamente la lista con riquadri e frecce. Verificare ad alta voce i casi limite: lista vuota, un solo nodo, lunghezza pari o dispari. Usare una testa fittizia per semplificare le condizioni ai limiti. Controllare sempre subito if not head. Dopo aver scritto il codice, eseguire una simulazione su una lista di tre nodi per individuare gli errori nei puntatori prima che lo faccia l'intervistatore.
La maggior parte degli errori nelle liste concatenate deriva da una di tre cause: dimenticare di salvare next prima di sovrascriverlo, commettere un errore di un'unità nella condizione di terminazione oppure non gestire il caso limite in cui cambia la testa; il nodo fittizio elimina completamente quest'ultimo problema.
Controllo rapido
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: una lista concatenata è costruita con oggetti Node dotati dei campi val e next, il pattern della testa fittizia elimina i casi limite in cui cambia la testa e la configurazione dei due puntatori lento e veloce è alla base dell'individuazione del punto centrale e del rilevamento dei cicli. Nella prossima lezione si affronterà l'inversione di una lista concatenata, uno dei problemi sui puntatori più frequenti nei colloqui tecnici.
Domande Frequenti
La lezione «Classe Node e costruzione delle liste» è gratuita?
Sì — il testo completo di «Classe Node e costruzione delle liste» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Classe Node e costruzione delle liste»?
Definisca una dataclass Node, costruisca liste collegando manualmente i nodi e scriva helper insert/delete/print per visualizzare i cambiamenti dei puntatori Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Classe Node e costruzione delle liste»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Classe Node e costruzione delle liste
- Invertire una linked list
- Rilevamento dei cicli con l'algoritmo di Floyd
- Unire, dividere e trovare l'ennesimo elemento dalla fine