Liste, pile e code

In questa pagina 5

Un ADT (vedi Problemi computazionali e algoritmi) specifica tipo dei dati, operazioni e parametri, non l'implementazione. 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

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

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.

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

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

	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)

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, annulla/ripeti, controllo delle parentesi.

Coda (queue)

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

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

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

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 che costo (vedi Problemi computazionali e algoritmi). In C: struct e funzioni (vedi Liste concatenate in C).
Lista index-based (get, set, add(i,e), remove(i), size, isEmpty): array, $O(1)$ tranne add/remove $O(n)$ ; array pieno ⇒ si raddoppia, inserimento in fondo $O(1)$ ammortizzato.
Lista position-based (first, last, before, after, addBefore/After, remove(p)): doppia lista con due sentinelle, tutto $O(1)$ ma scansione solo sequenziale.
Pila LIFO: push, top, pop, tutti $O(1)$ . Coda FIFO: enqueue, first, dequeue, $O(1)$ con lista e puntatore alla coda o con array circolare ((f+size) mod N). Deque = pila + coda.
Iterator (hasNext, next) e Iterable (iterator()); l'ordine dipende dall'implementazione.
Coda circolare su array di capacità $N$ : enqueue scrive in $(f + \text{size}) \bmod N$ , dequeue pone $f \leftarrow (f+1) \bmod N$ ; array estendibile: pieno ⇒ nuovo array di taglia doppia e copia, $O(1)$ ammortizzato in fondo.
Esempi: pila: stack delle chiamate, annulla/ripeti; coda: BFS dei grafi (vedi Visite di grafi - BFS e DFS).
Errori: costo di add/remove su array; LIFO/FIFO scambiati; sentinelle o puntatori dimenticati; accesso a una struttura vuota.