Nel progetto (Web) a cui sto lavorando è stata richiesta la visualizzazione di una lista di elementi con le seguenti caratteristiche:

• i nuovi elementi devono essere inseriti all'inizio dell'elenco (i più recenti verranno visualizzati per primi)
• la lista deve contenere al massimo n elementi: l'inserimento di un nuovo elemento, raggiunto il limite n, deve prevedere la rimozione dell'elemento più vecchio presente nella lista (ovvero quello inserito da più tempo)
• l'aggiunta di nuovi elementi è corposa (centinaia di insert al secondo per tutto il ciclo di vita dell'applicazione)
• il limite del numero massimo di elementi che devono essere mantenuti nella lista (n) è relativamente basso (< 10.000)

In pratica, definito un limite di 3 elementi e immaginando l'accodamento dei primi 5 interi in ordine crescente (1, 2, 3, 4 e 5) il risultato atteso è:

Ho pensato che sia una cosa semplicissima da realizzare in .NET sfruttando le classi in System.Collection.Generic ma... quale usare? Il framework prevede infatti:

List<T>

Lista generica, non utilizzabile allo scopo in quanto non è possibile inserire elementi in posizioni specifiche ma solo "to the end of the List(T)".

In realtà sarebbe possibile effettuare l'inserimento all'inizio della lista effettuando uno shift di tutti gli elementi ma le performance sarebbero improponibili!

Stack<T>

è letteralmente un insieme di elementi "impilati"; possiamo vederlo come una vaschetta portadocumenti sulla scrivania in cui vengono aggiunte delle pratiche (Push) semplicemente appoggiandole sopra e con l'impiegato che le processa che prende (Pop) il primo foglio che trova in cima alla pigna. Non assolve dunque allo scopo in quanto rimuove gli elementi più "nuovi" anziché quelli più "vecchi".

In pratica il seguente codice:

int capacity = 3; 
  
int max = 5; 

  
Stack<int> list = new Stack<int>(capacity); 

  
for (int i = 1; i <= max; i++) 

  
{ 

  
    if (list.Count >= capacity) 

  
        list.Pop(); 

  
    list.Push(i); 

  
    foreach (var item in list) 

  
        Console.Write("{0} ", item); 

  
    Console.WriteLine(); 

  
}

Produce:

1
2 1
3 2 1
4 2 1
5 2 1

Non ci siamo.

Queue<T>

è appunto una "coda" dove il primo elemento inserito (Enqueue) è anche il primo a venire rimosso (Dequeue); l'analogia che mi viene in mente è quella delle macchine ferme al casello dell'autostrada: il primo arrivato sarà anche il primo a superare la barriera. Questa collection assolve per metà allo scopo garantendo il corretto meccanismo di in/out ma ha il contro di presentare l'enumerazione degli elementi in ordine inverso rispetto a quanto richiesto (scorrendo la collection ottengo prima gli elementi più "vecchi" e poi quelli più "nuovi")

In pratica il seguente codice:

int capacity = 3; 
  
int max = 5; 

  
Queue<int> list = new Queue<int>(capacity); 

  
for (int i = 1; i <= max; i++) 

  
{ 

  
    if (list.Count >= capacity) 

  
        list.Dequeue(); 

  
    list.Enqueue(i); 

  
    foreach (var item in list) 

  
        Console.Write("{0} ", item); 

  
    Console.WriteLine(); 

  
}

Produce:

1
1 2
1 2 3
2 3 4
3 4 5

Non ci siamo ancora ma manca poco :-)

LinkedList<T>

Si tratta di un elenco con doppio collegamento; espone metodi per l'inserimento di nuovi elementi sia all'inizio dell'elenco (AddFirst) che alla fine (AddLast) che in posizioni intermedie (AddAfter e AddBefore), sia per la rimozione (RemoveFirst, RemoveLast, Remove), dandoci la massima flessibilità possibile. In pratica possiamo immaginare questa collection come un trenino giocattolo: possiamo aggiungere o togliere vagoni da entrambe le estremità del convoglio in modo del tutto indifferente.

In pratica il seguente codice:

int capacity = 3; 
  
int max = 5; 

  
LinkedList<int> list = new LinkedList<int>(); 

  
for (int i = 1; i <= max; i++) 

  
{ 

  
    if (list.Count >= capacity) 

  
        list.RemoveLast(); 

  
    list.AddFirst(i); 

  
    foreach (var item in list) 

  
        Console.Write("{0} ", item); 

  
    Console.WriteLine(); 

  
}

Produce:

1
2 1
3 2 1
4 3 2
5 4 3

Missione compiuta? Sembrerebbe di sì.

Per scrupolo ho fatto un piccolo test di performance, aspettandomi prestazioni simili per Queue e LinkedList:

// 
  
// Performance test configuration 

  
// 

  
DateTime start; 

  
int[] results; 

  
int capacity = 10000; 

  
int max = 1000000000; 

  


  
// 

  
// LinkedList performance test 

  
// 

  
start = DateTime.Now; 

  
LinkedList<int> list = new LinkedList<int>(); 

  
for (int i = 1; i <= max; i++) 

  
{ 

  
    if (list.Count >= capacity) 

  
        list.RemoveLast(); 

  
    list.AddFirst(i); 

  
} 

  
results = new int[list.Count]; 

  
list.CopyTo(results, 0); 

  
foreach (int item in results) 

  
{ 

  
    // do something with "item" 

  
} 

  
Console.WriteLine("LinkedList: max={0} -> {1}", 

  
    max.ToString("#,###"), 

  
    DateTime.Now.Subtract(start)); 

  


  
// 

  
// Queue performance test 

  
// 

  
start = DateTime.Now; 

  
results = null; 

  
Queue<int> queue = new Queue<int>(capacity); 

  
for (int i = 1; i <= max; i++) 

  
{ 

  
    if (queue.Count >= capacity) 

  
        queue.Dequeue(); 

  
    queue.Enqueue(i); 

  
} 

  
results = queue.ToArray(); 

  
foreach (int item in results) 

  
{ 

  
    // do something with "item" 

  
} 

  
Console.WriteLine("Queue: max={0} -> {1}", 

  
    max.ToString("#,###"), 

  
    DateTime.Now.Subtract(start));

Sebbene questo tipo di misurazione sia piuttosto "spannometrico", il risultato (per un miliardo di inserimenti a fronte di una lista con al più 10.000 items) mi ha lasciato basito:

LinkedList: max=1.000.000.000 -> 00:01:17.6770000
Queue: max=1.000.000.000 -> 00:00:30.4030000

Ovvero LinkedList richiede circa 2.5 volte il tempo necessario a Queue!

Conclusioni

Sebbene LinkedList<T> faccia il suo "sporco lavoro" lo fa... troppo lentamente!

Alla fine ho dunque optato per l'utilizzo di Queue<T> con l'aggiunta di poche righe di codice per leggere in modo inverso il contenuto enumerato della lista:

Queue<int> queue = new Queue<int>(capacity); 
  
// (codice omesso) 

  
List<int> temp = new List<int>(queue.ToArray()); 

  
temp.Reverse(); 

  
results = temp.ToArray(); 

  
foreach (int item in results) 

  
{ 

  
    // do something with "item" 

  
}

Infatti il numero di elementi mantenuti nella coda è decisamente troppo basso - meno di 10.000 - per risultare influenti le operazioni di copia in una List e di reverse della lista, anche se molto probabilmente questa porzione di codice potrebbe essere migliorata :-)

PS 1: qualcuno avrà notato l'assenza di acronimi come FIFO (first-in, first-out), LIFO (last-in, first-out), ecc.
Sono stati volutamente omessi perché il significato di "primo" e "ultimo" mi è risultato, leggendo qua e là sul Web, interpretato in modo non del tutto univoco (si riferisce all'ordine di inserimento? alla posizione che assume l'elemento nella collection? ad altro?)

PS 2: un doveroso grazie a Cristian e a Marco che mi hanno supportato sopportato in questa ricerca