Liste, pile e code

In questa pagina 5

Un ADT (vedi Problemi computazionali e algoritmi e, per le basi, Tipi di dato astratti) specifica tipo dei dati, operazioni e parametri, non l'implementazione. Le stesse strutture sono presentate in modo più elementare in Pila e coda, Liste concatenate e Realizzare contenitori su array e liste (Fondamenti di Informatica). In Java si descrive con un'interfaccia (solo costanti e metodi senza corpo); in C non esistono costrutti per gli ADT, si usano struct e funzioni (vedi Liste concatenate in C).

Lista

Collezione di elementi con un ordine lineare: primo, secondo, ..., ultimo. Si accede a un elemento in due modi.

Lista index-based

Definizione (lista index-based). L'elemento si identifica con l'indice $i \ge 0$ = numero di elementi che lo precedono.

Metodo Effetto

size(), isEmpty() numero di elementi, lista vuota

get(i) elemento in posizione $i$ , senza toglierlo

set(i, e) sostituisce l'elemento in $i$ con e e restituisce il vecchio

add(i, e) inserisce e all'indice $i$ spostando a destra i successivi

remove(i) toglie e restituisce l'elemento in $i$ , spostando a sinistra i successivi

Metodo	Effetto
`size()`, `isEmpty()`	numero di elementi, lista vuota
`get(i)`	elemento in posizione $i$ , senza toglierlo
`set(i, e)`	sostituisce l'elemento in $i$ con `e` e restituisce il vecchio
`add(i, e)`	inserisce `e` all'indice $i$ spostando a destra i successivi
`remove(i)`	toglie e restituisce l'elemento in $i$ , spostando a sinistra i successivi

Esempio. Su [7, 8, 9] si ha get(2) = 9, e add(1, 5) produce [7, 5, 8, 9].

Proprietà (array estendibile con raddoppio). Si realizza con un array: get, set, size in $O(1)$ ; add e remove in $O(n)$ per gli spostamenti. Se l'array è pieno si alloca un array di taglia doppia e si copiano gli elementi: il costo $\Theta(n)$ della copia è ammortizzato dai $n$ inserimenti precedenti, quindi l'inserimento in fondo costa $O(1)$ ammortizzato.

Esempio. Partendo da capacità $1$ e raddoppiando, $8$ inserimenti in fondo copiano in tutto $1+2+4=7$ elementi: meno di una copia per inserimento.

Perché l'ammortizzato è $O(1)$ . Con capacità iniziale $1$ , la copia avviene quando l'array contiene $1, 2, 4, 8, \dots$ elementi ed è pieno: copia rispettivamente $1, 2, 4, 8, \dots$ elementi. Dopo $n$ inserimenti le copie sono avvenute per le potenze di $2$ minori di $n$ , e il loro totale è la somma geometrica $1 + 2 + 4 + \dots + 2^{k} = 2^{k+1} - 1 < 2n \qquad \text{con } 2^k < n \le 2^{k+1}$ (formula della serie geometrica finita, vedi Notazione asintotica e Serie notevoli - geometrica, telescopica, armonica; per $2^k<n$ si ha $2^{k+1}-1<2n$ ). Quindi il costo totale di $n$ inserimenti è al più $n$ (scritture) più $2n$ (copie), cioè $\Theta(n)$ , e il costo medio per inserimento è $\Theta(1)$ : un singolo inserimento può costare $\Theta(n)$ , ma sono rari. Se invece si allungasse l'array di una sola cella ogni volta si copierebbero $1+2+\dots+(n-1)=\frac{n(n-1)}{2}$ elementi in totale:

Grafico interattivo: Elementi copiati in totale dopo n inserimenti in fondo: con raddoppio (2^ceil(log2 n) − 1, sempre sotto 2n) contro allungamento di una cella alla volta (n(n−1)/2); a n = 30 sono 31 contro 435

Lista position-based

L'elemento si identifica con la posizione (Position<E>, con getElement()): il contenitore, o nodo, che lo ospita. Metodi: first(), last(), before(p), after(p), addFirst(e), addLast(e), addBefore(p, e), addAfter(p, e), remove(p), set(p, e).

Definizione (lista position-based con doppia lista e sentinelle). Si realizza con una lista doppiamente concatenata: ogni nodo punta a predecessore e successore, e due nodi sentinella (senza elemento) delimitano inizio e fine, così nessun inserimento o rimozione ha casi particolari. Tutti i metodi costano $O(1)$ , ma la lista si scandisce solo in sequenza (arrivare al nodo $i$ costa $\Theta(i)$ ). L'implementazione in C con puntatori è in Liste concatenate in C e i puntatori in Puntatori in C.

Come funziona la sentinella. Le sentinelle header e trailer sono nodi senza elemento, con header.next che punta al primo nodo vero e trailer.prev all'ultimo. Per inserire un nodo n con valore e tra p e il suo successore s: si pongono n.prev = p, n.next = s, poi p.next = n e s.prev = n (quattro assegnamenti, indipendenti dalla lunghezza). Poiché p e s esistono sempre (al limite sono le sentinelle) non servono casi speciali per lista vuota o inserimento agli estremi.

Esempio. Dato un nodo $p$ , addAfter(p, e) collega il nuovo nodo ai suoi due vicini in $O(1)$ passi, senza scorrere la lista.

	array (index-based)	doppia lista (position-based)
accesso per indice	$O(1)$	$\Theta(i)$
inserire/togliere dato un nodo	$O(n)$	$O(1)$
spazio	compatto	un nodo con due puntatori per elemento

Si può realizzare una lista index-based con una doppia lista o una position-based con un array, ma con pochi vantaggi.

Pila (stack)

Definizione (pila LIFO). Inserimenti e rimozioni secondo LIFO (last in, first out): push(e) inserisce in cima, top() legge la cima senza togliere, pop() toglie e restituisce la cima, più size() e isEmpty(). Con un array e un indice t di cima, o con una lista concatenata con inserimento e rimozione in testa, tutti i metodi sono $O(1)$ (con array estendibile, ammortizzato). Esempi: stack delle chiamate di una funzione (i record di attivazione di Algoritmi ricorsivi e Stack e chiamata di funzioni in ARM), annulla/ripeti, controllo delle parentesi.

Controllo delle parentesi. Si scorre la stringa: ogni parentesi aperta si inserisce con push; per ogni parentesi chiusa si fa pop e si controlla che sia del tipo giusto. Su ( [ ] ): push(, push[, ] $\to$ pop dà [ ✓, ) $\to$ pop dà ( ✓, pila vuota alla fine: corretta. Su ( ]: push(, poi ] richiede [ ma pop dà ( ✗: errata. La pila vuota a fine stringa è necessaria (altrimenti restano parentesi aperte). Costo $\Theta(n)$ perché ogni carattere fa al più un push o un pop di costo $O(1)$ .

Esempio. Dopo push(1), push(2), push(3) si ha top() = 3; un pop() restituisce 3 e la nuova cima è 2.

Coda (queue)

Definizione (coda FIFO e buffer circolare). Secondo FIFO (first in, first out): enqueue(e) inserisce in fondo, first() legge il primo, dequeue() toglie e restituisce il primo. Con una lista concatenata con puntatori a testa e coda, tutto in $O(1)$ . Con un array si usa un buffer circolare: indice f del primo e size; enqueue scrive in (f + size) mod N, dequeue avanza f = (f + 1) mod N. Usata dalla visita in ampiezza dei grafi (vedi Visite di grafi - BFS e DFS).

Esempio. Con $N=5$ , primo in f = 3 e size = 2, enqueue scrive in $(3+2)\bmod5=0$ ; dopo un dequeue si ha f = 4. Il resto della divisione per $N$ fa "tornare a capo" l'indice: le celle $3$ e $4$ sono occupate, la prossima libera è $5 \bmod 5 = 0$ . Traccia con $N=5$ :

operazione	`f`	`size`	celle occupate	cella scritta o letta
(iniziale, dopo vari giri)	3	2	3, 4
`enqueue(x)`	3	3	3, 4, 0	scrive in $(3+2)\bmod5=0$
`enqueue(y)`	3	4	3, 4, 0, 1	scrive in $(3+3)\bmod5=1$
`dequeue()`	4	3	4, 0, 1	legge dalla cella $3$ , poi $f=(3+1)\bmod5=4$

La coda è piena quando size == N. Rispetto a un array in cui dequeue sposta tutti gli elementi a sinistra ( $O(n)$ ), qui nessun elemento si sposta e tutte le operazioni costano $O(1)$ . Il resto della divisione è definito in Notazione asintotica (e per i numeri interi in Aritmetica binaria).

Definizione (deque). La deque (double-ended queue) permette inserimento e rimozione sia in testa sia in coda: unisce pila e coda.

Esempio. Dopo addFirst(1), addLast(2), addFirst(3) la deque contiene 3, 1, 2.

Iteratori

Un iteratore (Iterator<E>) esamina gli elementi di una collezione uno alla volta: hasNext() dice se c'è un prossimo elemento, next() lo restituisce. Una collezione iterabile (Iterable<E>) ha un metodo iterator() che ne restituisce uno. L'ordine di restituzione non è fissato dall'ADT ma dall'implementazione dell'iteratore. È il meccanismo con cui, per esempio, si scorrono i vicini di un vertice (incidentEdges(v)). È l'analogo del for x in lista di Python (Ciclo for e range), in cui il ciclo chiama a ogni passo hasNext() e next() dietro le quinte.

Errori comuni

Dimenticare che add/remove per indice su array costano $O(n)$ , non $O(1)$ .
Confondere LIFO e FIFO: la pila restituisce l'ultimo inserito, la coda il primo.
Dimenticare le sentinelle nella lista doppia (casi speciali agli estremi) o aggiornare solo uno dei due puntatori.
Leggere (top, first) o togliere da una pila o coda vuota.

Versione ripasso

ADT = interfaccia (cosa); implementazione = come e a quale costo (vedi Problemi computazionali e algoritmi, Tipi di dato astratti). In C si usano struct e funzioni (vedi Liste concatenate in C).
Lista index-based (get(i), set(i,e), add(i,e), remove(i), size(), isEmpty()): su array get e set sono $O(1)$ , add e remove $O(n)$ per gli spostamenti.
Array estendibile: se è pieno si alloca il doppio e si copia. Partendo da capacità $1$ , dopo $n$ inserimenti le copie totali sono meno di $2n$ (serie geometrica, $2^{k+1}-1<2n$ ): costo ammortizzato $O(1)$ in fondo. Allungare di una cella alla volta costerebbe $\frac{n(n-1)}{2}$ copie.
Lista position-based (first, last, before, after, addBefore, addAfter, remove(p), set(p,e)): doppia lista con due sentinelle header e trailer; tutti i metodi sono $O(1)$ , ma arrivare al nodo $i$ -esimo costa $\Theta(i)$ .
Inserimento con sentinelle: tra $p$ e il suo successore $s$ bastano quattro assegnamenti (n.prev = p, n.next = s, p.next = n, s.prev = n), senza casi speciali per lista vuota o estremi.
Pila LIFO: push(e), top(), pop(), tutti $O(1)$ . Esempi: stack delle chiamate (vedi Algoritmi ricorsivi); controllo delle parentesi con push per le aperte e pop per le chiuse, pila vuota alla fine. Costo $\Theta(n)$ .
Coda FIFO: enqueue(e), first(), dequeue(), $O(1)$ con lista con testa e coda, oppure con array circolare: enqueue scrive in $(f+\text{size}) \bmod N$ , dequeue pone $f \leftarrow (f+1) \bmod N$ . Esempio con $N=5$ , $f=3$ , $\text{size}=2$ : enqueue scrive nella cella $0$ .
Deque: inserimento e rimozione sia in testa sia in coda. Esempio: addFirst(1), addLast(2), addFirst(3) dà 3, 1, 2.
Iteratori: Iterator<E> con hasNext() e next(); Iterable<E> con iterator(). L'ordine dipende dall'implementazione; è il meccanismo del for di Python (Ciclo for e range).
Esempi di uso: pila per annulla/ripeti; coda per la BFS dei grafi (vedi Visite di grafi - BFS e DFS).
Costo di add su array: inserire in testa a un array di $n$ elementi sposta tutti gli $n$ elementi, quindi $\Theta(n)$ ; in fondo, invece, si paga solo l'ammortizzato.
Errori tipici: pensare $O(1)$ add/remove per indice su array; LIFO e FIFO scambiati; sentinelle o puntatori dimenticati; top, first o dequeue su una struttura vuota.