Code Review: Jak to jest z List<T> i LinkedList<T>?

List jest bardzo popularną kolekcją danych, niestety często źle używaną. Kiedyś pisałem, że jeśli ma się jakiekolwiek informację o rozmiarze kolekcji, warto w konstruktorze przekazać początkowy rozmiar.

Temat jednak będzie dotyczył porównania List<T> z LinkedList<T>.

Jeśli ktoś samemu kiedyś pisał dynamiczną tablicę danych, to wie, że realokacja pamięci jest bardzo kosztowna. W przypadku np. listy jednokierunkowej, dodawanie nowego elementu to nic innego jak doczepienie kolejnego węzła.

List<T> ma tą zaletę, że można uzyskać dostęp przez indeks – identycznie jak w przypadku  tablic. LinkedList ma oczywiście funkcję ElementAt ale kosztuje to O(n), a nie O(1). W praktyce jednak, bardzo często nie trzeba używać dostępu przez indeks…

Czytając powyższe rozważania można dojść do wniosku, że zwykle lepiej używać LinkedList niż List. Niestety wiele programistów wpada tą w pułapkę, ponieważ złożoność pesymistyczna jest wyższa dla List<T> niż LinkedList<T>, jeśli chodzi o dodawanie nowego elementu. W praktyce jest jednak dokładnie odwrotnie:

var list = new List<int>();
var linkedList = new LinkedList<int>();
const int n = 10000000;

var stopwatch = Stopwatch.StartNew();
for(int i=0;i<n;i++)
list.Add(i);

Console.WriteLine(stopwatch.ElapsedMilliseconds);

stopwatch=Stopwatch.StartNew();
for (int i = 0; i < n; i++)
linkedList.AddLast(i);

Console.WriteLine(stopwatch.ElapsedMilliseconds);

Wynik dla List<T> to 67 a dla LinkedList<T> 1754.

Dlaczego LinkedList jest tak wolny? List<T> to dynamiczna kolekcja danych i nie realokuje pamięci za każdym razem, gdy wywołujemy Add. W momencie gdy brakuje pamięci w buforze, alokowana jest dodatkowa pamięć – za każdym razem tworząc większą rezerwę. Skutkuje to, że tylko w kilku wywołaniach Add, należy przealokować pamięć. LinkedList z kolei, za każdym razem musi stworzyć LinkedNode, który opakowuje wartość (dodaje wskaźniki Next, Previous itp.).

Nie znaczy to, że LinkedList jest zawsze wolniejszy. Wszystko zależy jak dodajemy elementy. LinkedList jest skuteczny jak chcemy dodać wartość konkretnie pomiędzy dwa inne elementy. Wtedy za pomocą wskaźników Previous, Next jest to dość łatwe – nie trzeba nic przesuwać.

Mam nadzieje, że pokazałem jak łatwo popełnić błąd w optymalizacji, jeśli nie ma się dobrego zestawu testów, potwierdzających przypuszczenia.

Leave a Reply

Your email address will not be published.