Strutture dati: Linked list

Le liste concatenate (doppiamente e non ordinate in questo caso) sono facilmente implementabili se si utilizzano strutture dati che mantengono puntatori agli elementi precedenti e successivi, oltre che ai dati propri di ogni elemento.

Il codice presentato di seguito implementa anche alcuni metodi di supporto per cercare, inserire ed eliminare elementi dalla lista.

/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di 
utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme 
C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono 
una maggiore semplificazione.*/
 
#include <stdio.h>
 
struct link
{
 int val;
 struct link *prev;
 struct link *next;
};
 
link* list_search(link*, int);
void list_insert(link*&, link&);
void list_delete(link*&, link&);
void print_list(link*);
 
int main(int argc, char *argv[], char *envp[])
{
 link l1 = { 1, nullptr, nullptr };
 link *first = &l1;
 
 link l2 = { 2, nullptr, nullptr };
 link l3 = { 3, nullptr, nullptr };
 link l4 = { 4, nullptr, nullptr };
 
 list_insert(first, l2);
 list_insert(first, l3);
 list_insert(first, l4);
 
 print_list(first);
 
 list_delete(first, l3);
 
 print_list(first);
 
 link *f;
 if (f = list_search(first, 4))
  printf("Trovato Elemento della lista con valore %d all'indirizzo %#x\n", f->val, f);
 else
  printf("Elemento con valore %d assente nella lista\n", f->val);
 
 list_delete(first, *f);
 
 print_list(first);
 
 return 0;
}
 
link* list_search(link *first, int x)
{
 link *lp = first;
 while (lp != nullptr && x != lp->val)
  lp = lp->next;
 
 return lp;
}
 
// Anche i puntatori vengono passati per valore quindi first è un riferimento ad un puntatore.
// Scambia first con il nuovo elemento
void list_insert(link *&first, link &l)
{
 l.next = first;
 
 if (first)
  first->prev = &l;
 
 l.prev = nullptr;
 first = &l;
}
 
 
// Anche puntatori vengono passati per valore quindi first è un riferimento ad un puntatore.
// Sovrascrive first se l'elemento da cancellare è il primo e lo
// sovrascrive con il successivo, che può essere null
void list_delete(link *&first, link &l)
{
 if (l.prev != nullptr)
  l.prev->next = l.next;
 else
  first = (l.next);
 
 if (l.next != nullptr)
  l.next->prev = l.prev;
}
 
void print_list(link *first)
{
 link *lp = first;
 while (lp->next != nullptr)
 {
  printf("%d ", lp->val);
  lp = lp->next;
 }
 printf("%d", lp->val);
 printf("\n");
}

Riferimenti
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Algoritmi in C - Sedgewick