[c#] Quando dovrei usare una lista vs una lista collegata



6 Answers

Nella maggior parte dei casi, List<T> è più utile. LinkedList<T> avrà meno costi quando si aggiungono / rimuovono gli elementi nel mezzo dell'elenco, mentre List<T> può solo aggiungere / rimuovere a basso costo alla fine dell'elenco.

LinkedList<T> è solo più efficiente se si accede a dati sequenziali (in avanti o indietro) - l'accesso casuale è relativamente costoso poiché deve percorrere la catena ogni volta (quindi perché non ha un indicizzatore). Tuttavia, poiché un List<T> è essenzialmente solo un array (con un wrapper), l'accesso casuale va bene.

List<T> offre anche molti metodi di supporto: Find , ToArray , ecc; tuttavia, questi sono anche disponibili per LinkedList<T> con .NET 3.5 / C # 3.0 tramite i metodi di estensione - quindi questo è meno di un fattore.

Question

Quando è meglio usare una List(Of T) contro una LinkedList(Of T) ?




Una circostanza comune per usare LinkedList è come questa:

Supponiamo di voler rimuovere molte stringhe certe da un elenco di stringhe di grandi dimensioni, ad esempio 100.000. Le stringhe da rimuovere possono essere ricercate in HashSet dic e si ritiene che l'elenco di stringhe contenga da 30.000 a 60.000 tali stringhe da rimuovere.

Allora qual è il miglior tipo di lista per la memorizzazione delle 100.000 stringhe? La risposta è LinkedList. Se sono archiviati in un ArrayList, eseguono il iterazione su di esso e rimuovono le stringhe corrispondenti che richiedono fino a miliardi di operazioni, mentre impiegano solo circa 100.000 operazioni utilizzando un iteratore e il metodo remove ().

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}






Gli elenchi collegati forniscono l'inserimento o la cancellazione molto veloce di un membro della lista. Ogni membro in un elenco collegato contiene un puntatore al membro successivo nell'elenco in modo da inserire un membro nella posizione i:

  • aggiorna il puntatore nel membro i-1 in modo che punti al nuovo membro
  • imposta il puntatore nel nuovo membro in modo che punti al membro i

Lo svantaggio di una lista collegata è che l'accesso casuale non è possibile. Per accedere a un membro è necessario attraversare l'elenco finché non viene trovato il membro desiderato.




Questo è adattato dalla risposta accettata di Tono Nam che corregge alcune misurazioni sbagliate in esso.

Il test:

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

E il codice:

using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace 
{
    static class LinkedListPerformance
    {
        class Temp
        {
            public decimal A, B, C, D;

            public Temp(decimal a, decimal b, decimal c, decimal d)
            {
                A = a; B = b; C = c; D = d;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

Puoi vedere i risultati in accordo con le prestazioni teoriche che altri hanno documentato qui. Abbastanza chiaro - LinkedList<T> guadagna molto tempo in caso di inserimenti. Non ho provato la rimozione dal centro della lista, ma il risultato dovrebbe essere lo stesso. Ovviamente List<T> ha altre aree dove funziona meglio come O (1) accesso casuale.




Usa LinkedList<> quando

  1. Non sai quanti oggetti stanno arrivando attraverso il cancello dell'inondazione. Ad esempio, Token Stream .
  2. Quando si voleva SOLO eliminare \ inserire alle estremità.

Per tutto il resto, è meglio usare List<> .




Il vantaggio principale delle liste collegate sugli array è che i collegamenti ci forniscono la capacità di riorganizzare gli articoli in modo efficiente. Sedgewick, p. 91




Related