Liste semplicemente connesse

Note

Una lista semplicemente connessa (Linked List) stocca gli elementi sparsi in memoria. Quindi ogni elemento ha un riferimento al successivo.

Se la lista di lunghezza non è ordinata:

  • Ricerca, minimo, massimo, successore sono
  • Inserimento è
  • Cancellazione è se l'elemento va trovato, se si ha un riferimento alla posizione di inserimento

Se la lista di lunghezza è ordinata:

  • Uno dei due tra minimo e massimo è , l'altro . Se si ha un puntatore accessorio ad entrambi gli elementi sono entrambi
  • Ricerca e successore sono
  • Inserimento e cancellazione sono

Liste doppiamente concatenate

Note

Una lista doppiamente concatenata (Double Linked List), è simile alle liste semplicemente connesse, con l'aggiunta che ogni elemento ha un riferimento al precedente. Si comporta come una lista semplice, tranne per la cancellazione: cancellare un elemento fornito alla Delete(L,e) per riferimento è : 

e.prev.next <- e.next
e.next.prev <- e.prev