Liste in Python

Creazione e accesso

vuota = []
numeri = [3, 1, 4, 1, 5]
mista = [1, "due", 3.0, [4, 5]]     # elementi di tipo qualunque
zeri = [0] * 5                      # [0, 0, 0, 0, 0]
cifre = list("123")                 # ['1', '2', '3']
quadrati = list(range(1, 6))        # [1, 2, 3, 4, 5]

Definizione (lista mutabile). Indici, indici negativi, slicing, len, in, +, * funzionano come per le Stringhe in Pythonstr come sequenza immutabile di caratteri Unicode; indici e slicing; operatori; metodi principali (split, join, strip, find, replace...); f-string e formattazione; confronto lessicografico.Stringhe in Python →. La differenza è che la lista è mutabile:

numeri[0] = 10           # [10, 1, 4, 1, 5]
numeri[1:3] = [7, 7, 7]  # assegnamento a una fetta: [10, 7, 7, 7, 1, 5]
del numeri[0]            # [7, 7, 7, 1, 5]

Esempio. Con numeri = [3, 1, 4], numeri[0] = 10 dà [10, 1, 4] e numeri[1:3] = [7, 7, 7] dà [10, 7, 7, 7].

Internamente una lista è un array dinamico di riferimenti: celle contigue, accesso per indice in tempo costante, spazio di riserva in fondo per gli append.

Metodi

Proprietà (metodi delle liste e loro costo)

Operazione	Effetto	Costo
l[i], l[i] = x	lettura/scrittura per indice	$O(1)$
l.append(x)	aggiunge in fondo	$O(1)$ ammortizzato
l.pop()	toglie e restituisce l'ultimo	$O(1)$
l.pop(i), l.insert(i, x)	toglie/inserisce in posizione i, sposta gli elementi successivi	$O(n)$
l.remove(x)	toglie la prima occorrenza di x (ValueError se manca)	$O(n)$
x in l, l.index(x), l.count(x)	ricerca lineare	$O(n)$
l.extend(seq)	aggiunge tutti gli elementi di seq	$O(k)$
l.sort()	ordina sul posto, restituisce None	$O(n \log n)$
l.reverse()	rovescia sul posto	$O(n)$
sorted(l), reversed(l)	nuova lista ordinata / iteratore al contrario
min(l), max(l), sum(l)		$O(n)$

Esempio. Con l = [3, 1, 2], sorted(l) restituisce [1, 2, 3] senza toccare l; l.sort() restituisce None e lascia l == [1, 2, 3].

Significato dei costi: Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →.

l = [3, 1, 2]
l = l.sort()       # ERRORE logico: sort restituisce None, ora l è None
l = sorted(l)      # oppure: l.sort() da solo

Aliasing e copie

a = [1, 2, 3]
b = a              # alias: stesso oggetto
c = a[:]           # copia superficiale (anche a.copy() o list(a))

Definizione (copia superficiale e profonda). Copia superficiale: nuova lista, ma gli elementi sono gli stessi oggetti. Con liste annidate non basta:

import copy
m = [[1, 2], [3, 4]]
s = m.copy()
s[0][0] = 99       # modifica anche m[0][0]: le righe sono condivise
d = copy.deepcopy(m)   # copia profonda: anche le righe sono nuove

Esempio. Con m = [[1, 2], [3, 4]] e s = m.copy(), s[0][0] = 99 cambia anche m[0][0]; con copy.deepcopy(m) no.

List comprehension

Definizione (list comprehension). [espressione for x in iterabile if condizione] costruisce una nuova lista.

Esempio. [x * x for x in range(5) if x % 2 == 0] restituisce [0, 4, 16].

quadrati = [x * x for x in range(10)]
pari = [x for x in numeri if x % 2 == 0]
parole_lunghe = [p.upper() for p in parole if len(p) > 3]
coppie = [(i, j) for i in range(3) for j in range(3) if i != j]

Equivale al ciclo for con append, ma è un'espressione. Se la logica è complicata, il ciclo esplicito è più leggibile.

Liste annidate e matrici

righe, colonne = 3, 4
M = [[0] * colonne for _ in range(righe)]   # corretto: 3 liste distinte
M[1][2] = 5

for riga in M:
    print(" ".join(f"{x:3}" for x in riga))

trasposta = [[M[i][j] for i in range(righe)] for j in range(colonne)]

M = [[0] * 4] * 3    # SBAGLIATO: 3 riferimenti alla STESSA riga
M[0][0] = 1          # cambia la prima colonna di tutte le righe

Liste come array

Una lista Python fa da array: in C l'array ha dimensione fissa e tipo unico (vedi Array e stringhe in CArray di dimensione fissa in memoria contigua, inizializzazione, nessun controllo sugli indici, passaggio a funzioni con la lunghezza, matrici; stringhe come array di char terminati da '\0' e funzioni di string.h.Array e stringhe in C →); in Python la lista cresce e contiene oggetti di tipo qualunque. Per stringhe e liste di elementi omogenei si scrivono gli stessi algoritmi: Pattern algoritmici iterativiSchemi ricorrenti nei cicli: accumulatore, contatore, massimo e minimo, ricerca con uscita anticipata, verifica universale, filtro e trasformazione, finestra scorrevole, due indici, elaborazione di coppie.Pattern algoritmici iterativi →, Ricerca lineare e binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria →, Algoritmi di ordinamentoSelection sort, insertion sort e bubble sort (quadratici), merge sort (n log n, divide et impera); stabilità, ordinamento sul posto, costo nei vari casi; sort e sorted con key.Algoritmi di ordinamento →.

Errori tipici

• l = l.append(x) o l = l.sort(): i metodi che modificano sul posto restituiscono None.
• Matrice creata con [[0] * m] * n.
• Indice len(l) (l'ultimo valido è len(l) - 1).
• Rimuovere elementi dalla lista mentre la si scorre con for: costruire una nuova lista con una comprehension.