Una lista è una sequenza finita di oggetti di un qualche tipo. Le operazioni canoniche sulle liste sono l'inserimento, la ricerca e la cancellazione. Nell'implementazione canonica si usano liste concatenate (o doppiamente concatenate).
Se la lista viene mantenuta ordinata l'inserimento costa O(n^2), la ricerca O(n), la cancellazione O(n). Se la lista
non é ordinata l'inserimento in testa o in coda costa O(1), la ricerca e la cancellazione O(n). In entrambi i casi il costo della cancellazione è dovuto alla ricerca che deve rinvenire l'elemento da cancellare.

Omissioni:
Una lista è una sequenza finita di oggetti di un qualche tipo. Le operazioni canoniche sulle liste sono l'inserimento, la ricerca, la cancellazione. Nell'implementazione canonica a liste di nodi concatenati (o doppiamente concatenati) queste operazioni prendono O(n).

---

Modificato il 2007-05-04 00:12:16 da MarKuS

Aggiunzioni:
Una lista è una sequenza finita di oggetti di un qualche tipo. Le operazioni canoniche sulle liste sono l'inserimento, la ricerca, la cancellazione. Nell'implementazione canonica a liste di nodi concatenati (o doppiamente concatenati) queste operazioni prendono O(n).

pile

Una pila è una lista il cui accesso è limitato alll'inserimento ed all'estrazione in testa alla pila (lista). Le operazioni di push, pop prendono tempo O(1). E' possibile definire un'operazione head che legge in O(1) la testa della pila senza estrarne l'elemento.

code

Anche le code possono essere realizzate come liste ad accesso limitato. In questo caso sono consentiti esclusivamente l'inserimento in coda (per l'appunto) e l'estrazione in testa, più eventualmente un'operazione di peek ("sbirciare" la testa) analoga alla precedente. enqueue, peek e dequeue prendono tempo O(1).


Omissioni:
Una lista è una sequenza finita di oggetti di un qualche tipo. Le operazioni canoniche sulle liste