Liste in Python

In questa pagina 7

Creazione e accesso

python

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]

Indici, indici negativi, slicing, len, in, +, * funzionano come per le Stringhe in Python. La differenza è che la lista è mutabile:

python

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]

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

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)$

Significato dei costi: Complessità computazionale.

python

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

python

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

Copia superficiale: nuova lista, ma gli elementi sono gli stessi oggetti. Con liste annidate non basta:

python

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

List comprehension

[espressione for x in iterabile if condizione] costruisce una nuova lista.

python

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

python

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)]

python

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 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 iterativi, Ricerca lineare e binaria, 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.

Liste in Python

Creazione e accesso

Metodi

Aliasing e copie

List comprehension

Liste annidate e matrici

Liste come array

Errori tipici

Teoria collegata