class Nodo: # Constructor def __init__(self, key=none, next=none): self.key = next self.next = next
Creazione di una linked list
da fare
Python Garbage Collector
Se abbiamo una linked list il cui primo nodo è puntato solamente da un puntatore pe sovrascriviamo questo puntatore (es: p=None) la lista andrà “persa” (non più puntata da niente).
Python in questo caso si occupa di liberare la memoria (cancellando il primo nodo della lista).
Il secondo nodo della linked list ora non è più puntato da niente e verra “cancellato”, e a sua volta accadrà la stessa cosa per il resto dei nodi della lista.
Inserimento
Aggiungere elemento in testa
def Insert0(p, x): # p: puntatore 1° nodo lista # x: elemento da aggiungere in testa alla lista q = p p = Nodo(x, q) return p
note: scritto da me, non dal prof
Aggiungere elemento in coda
Aggiungere un elemento in posizione x
Creare nuovo nodo
Inizializzare il puntatore next del nuovo nodo uguale al puntatore next del puntatore nodo precedente (pos: x−1)
Cambiare puntatore next del nodo precedente (pos x−1) con posizione del nuovo nodo
Posizione non finale:
Eliminazione
Cancella la prima occorrenza di un valore x nella list p
def Cancella(p, x): if p = None: # Lista Vuota return p if p.key == x: p = p.next else: q = p while q.next != None and q.next.key != x: q = q.next if q.next != None: q.next = q.next.next
Costo:O(n)
Ricerca
Esempi
Creazione di una lista
P = Nodo(7)
P.next = Nodo(2)
P.next.next = Nodo(12)
Print di una lista
def Stampa(p): while p != null: print(p.key) p = p.next
note: p is local variable and doesn’t change the original p
