Le Liste

Dato un insieme di valori U , chiamiamo lista una sequenza finita L di elementi appartenenti all’insieme U .

Una struttura dati d tipo lista può non contenere alcun elemento:
L = \Lambda
Oppure può essere composta da una sequenza finita di valori:
L = \{a_{1}, a_{2}, \ldots, a_{n}\} \text{ con } n \ge 1 \text{ e } a_{i} \in U \forall i = \{1, 2, \ldots, n\}

L’accesso diretto alla lista è limitato al primo elemento, per accedere ad un qualsiasi altro elemento occorre scandire la lista, cella per cella, fino ad arrivare al blocco interessato.

La struttura delle liste permette di svolgere alcune operazioni complesse sulle celle. Queste operazioni vanno dall’inserimento di un nuovo elemento, alla lettura di un valore precedentemente memorizzato. Le operazioni sono più semplici se vengono eseguite sul valore in testa alla lista, tuttavia esse possono essere eseguite su una posizione arbitraria.

Le operazioni definite su una struttura dati di tipo lista sono:

  • \text{IS\_EMPTY}(L) , controlla che la lista sia vuota;
  • \text{GET}(L, k) , restituisce il valore contenuto all’interno del nodo k -esimo;
  • \text{ADD}(L, k, u) , permette l’inserimento di un valore u in una data posizione k della lista;
  • \text{REMOVE}(L, k) , permette l’eliminazione del nodo k -esimo.

In formule:
\text{IS\_EMPTY}(L) = \{ 1 \text{ if } L=\Lambda; 0 \text{ else } \}

\text{GET}(L, k) = \{ a_{k} \text{ if } L=(a_{1}, a_{1}, \ldots, a_{n}) \text{ e } 1 \le k \le n; \perp \text{ else } \}

\text{ADD}(L, k, u) = \{ (u) \text{ if } L=\Lambda \text{ e } k=1 \}
\text{ADD}(L, k, u) = \{ (a_{1}, \ldots, u, a_{k}, \ldots) \text{ if } L=(a_{1}, \ldots, a_{n}) \text{ e } 1 \le k \le n+1 \}
\text{ADD}(L, k, u) = \{ \perp \text{ else } \}

\text{REMOVE}(L, k) = \{ (a_{1}, \ldots, a_{k-1}, a_{k+1}, \ldots) \text{ if } L=(a_{1}, \ldots, a_{n}) \text{ e } 1 \le k \le n \}
\text{REMOVE}(L, k) = \{ \perp \text{ else } \}

Implementazione delle Liste

In via teorica le liste possono essere implementate in tre modi differenti:

  • Mediante una tabelle;
  • Mediante due tabelle;
  • Mediante un record.

Le liste mediante Tabelle

La prima implementazione prevede la creazione di una lista L = (a_{1}, a_{2}, \ldots, a_{n}) di n elementi mediante una tabella T di dimensione m con m \le n, che manterrà nelle prime n celle i valori \{a_{1}, a_{2}, \ldots, a_{n}\}. In questa implementazione la selezione dell’elemento k -esimo (operazione di GET) richiederà la proiezione della k -esima componente della tabella. Questa operazione ha normalmente costo O(1) con il criterio uniforme, tuttavia l’inserimento o la cancellazione di un nuovo elemento richiedono un numero superiore di passi dal momento che tutti i valori devono essere cariati sequenzialmente e nell’ordine corretto. In tali circostanze potrebbe essere necessario intervenire sulla dimensione della tabella o verificare la dimensione del contatore ad essa associato.

Il costo spaziale di questa implementazione è quindi pari a \Theta(n) .

Le liste mediante due Tabelle

La seconda implementazione di una struttura dati di tipo lista fa nuovamente uso le tabelle, tuttavia questa volta vengono utilizzate due tabelle distinte identificate rispettivamente come: Nome e Successivo; per mantenere in memoria il valore dell’elemento e il suo puntatore al blocco successivo.

Nome
1 A
2 C
3 D
4 B
Successivo
1 4
2 3
3 0
4 2

Il valore ‘0’ posto nella tabella Successivo indica la fine della lista. Questa seconda implementazione non richiede il salvataggio sequenziale degli elementi della lista, tuttavia potrebbe ancora richiedere la riallocazione della tabella in caso di raggiungimento della sua dimensione massima.

Il costo spaziale di questa implementazione è pari a \Theta(2n) = \Theta(n) .

Le liste mediante Record

Infine, la terza implementazione fa uso dei record per mantenere in memoria una lista concatenata di n elementi. In questi casi una lista L = (a_{1}, a_{2}, \ldots, a_{n}) viene rappresentata mediante l’uso di n record, uno per ogni posizione.
Ogni record è composto da due campi:

  1. il valore dell’elemento;
  2. il puntatore al blocco successivo.

Esiste inoltre un particolare puntatore contenente l’indirizzo del valore iniziale. Il valore della complessità spaziale risulta essere uguale a \Theta(n) .

algo_str1

È possibile modificare l’implementazione della lista in modo da renderla percorribile in entrambe le direzioni, per farlo sarà necessario introdurre al suo interno il puntatore al blocco precedente.

Implementazione delle Liste in Linguaggio C

Nel linguaggio C il modo più pratico per definire una lista ordinata di elementi richiede l’utilizzo delle strutture. Ogni elemento della struttura andrà a contenere il valore del campo e il puntatore al blocco successivo (quindi alla struttura successiva). In alcuni casi può essere più pratico creare un campo aggiuntivo in cui conservare anche il puntatore al nodo precedente.

Iniziamo definendo la struttura che conterà i nostri valori:

struct node {
 int value;
 struct node *next;
};
typedef struct node node;

Andiamo poi a creare un puntatore al valore iniziale della lista, tale puntatore dovrà essere inizializzato con il valore NULL, questo ci permetterà di capire se la lista è già stata inizializzata.

struct node *first = null;

Considerando la precedente implementazione presentiamo in seguito le funzioni principali precedentemente descritte.

Controllo sulla Lista

La funzione \text{IS\_EMPTY(list)} permette di verificare l’esistenza della lista.

Procedura IS_EMPTY(L)
begin
  if L = null then
    return 1
  else
    return 0
end

Il costo dell’operazione di verifica è unitario, O(1) .

Per l’implementazione in linguaggio C si faccia riferimento a questa pagina.

Lettura di un valore della Lista

La funzione \text{GET(list, count)} ci permette di acquisire il valore di un determinato nodo della lista.

Procedura GET(L, k)
begin
  if IS_EMPTY(L) = 1 then
    return 丄
  else
    T = L
    i := 1
    while T != 0 do
      if i = k then
        return T∙valore
      else
        i := i+1
        ∗T := T∙puntatore
    end while
end

Il costo dell’operazione è strettamente dipendente dalla posizione dell’elemento scelto, risulta quindi essere O(k) . Si faccia presente che in caso di accesso alla prima posizione si ottiene il costo unitario, O(1) .

Per l’implementazione in linguaggio C si faccia riferimento a questa pagina.

Inserimento di un nuovo valore nella Lista

La funzione \text{ADD(list, count, value)} permette l’inserimento di un nuovo valore in posizione k -esima.

Procedura ADD(L, k, a)
begin
  creo un nuovo nodo X (nuova struttura record)
  X∙valore := a
  if IS_EMPTY(L) = 1 ⋁ k = 1
    X∙puntatore := ∗L
    return X
  else
    T := L
    i := 1
    while T != 0 do
      if i = k-1 then
        X∙puntatore := T∙puntatore
        T∙puntatore := ∗X
        return L
      else
        i := i+1
        ∗T := T∙puntatore
    end while
  end if
end

Il costo dell’operazione dipende dalla posizione dell’elemento, risulta quindi essere nuovamente O(k) . Ancora una volta l’esecuzione dell’operazione sul primo elemento della lista avviene in tempo unitario.

Per l’implementazione in linguaggio C si faccia riferimento a questa pagina.

Rimozione di un valore dalla Lista

La funzione \text{REMOVE(list, count)} consente l’eliminazione di un nodo presente all’interno della lista. Anche in questo caso l’utente segnalerà l’indice del nodo da eliminare.

Procedura REMOVE(L, k)
begin
  if IS_EMPTY(L) = 1 then
    return 丄
  else if k = 1 then
    return L∙puntatore
  else
    T := L
    i := 1
    while T != 0 do
      if i = k-1 then
        T∙puntatore := T∙puntatore∙puntatore
        return L
      else
        i := i+1
        ∗T := T∙puntatore
    end while
  end if
end

Il costo dell’operazione dipende dalla posizione dell’elemento, risulta essere O(k) , valgono le considerazioni già fatte in precedenza.

Per l’implementazione in linguaggio C si faccia riferimento a questa pagina.

Le Liste in Linguaggio C, programma completo

Per completezza allego questo programma scritto in linguaggio C che integra tutte le funzioni per le liste viste in precedenza. È stata aggiunta la funzione print_ls() che stampa a video tutti i nodi della stringa.