Klasa
LinkedList jest w .NET Base Class Library od bardzo dawna (od wersji 2.0) i bardzo rzadko jest używana. Zawsze była dla mnie pewną tajemnicą, więc postanowiłem zrobić parę testów na tej klasie. Ogólny sposób działania linked listy można poczytać na stronie
wikipedii. Poniżej przedstawiam w punktach krótką charakterystykę:
1) LinkedList występuje tylko w postaci generycznej (LinkedList<T>).
2) LinkedList nie jest "listą" - to znaczy, że nie implementuje interfejsu IList. Interfejsy z których implementuje LinkedList to:
- ICollection<T>, ICollection
- IEnumerable<T>, IEnumerable
- ISerializable, IDeserializationCallback
Dla uproszczenia słownictwa przyjmujemy, że
LinkedList<T> i List<T> będziemy nazywać listą.
3) Metody AddFirst i AddLast określają kolejność zapisywanych obiektów. Możemy w prosty sposób dodać obiekt na końcu listy jak i na początku
NP:
var linkedList = new LinkedList<int>();
//tworzy LinkedList
linkedList.AddFirst(1);
// 1
linkedList.AddFirst(2);
// 2, 1
linkedList.AddFirst(3);
// 3, 2, 1
linkedList.AddLast(4);
// 3, 2, 1, 4
linkedList.AddLast(5);
// 3, 2, 1, 4, 5
linkedList.AddLast(6);
// 3, 2, 1, 4, 5, 6
4) Możemy dodać element do wyznaczonego węzła
var linkedList = new LinkedList<int>();
//tworzy LinkedList
var objOne= linkedList.AddFirst(1);
// 1
var objTwo = linkedList.AddAfter(objOne, 2);
// 1, 2
var objThree = linkedList.AddBefore(objTwo, 3);
// 1, 3, 2
var objFour = linkedList.AddAfter(objThree, 4);
// 1, 3, 4, 2
var objFive = linkedList.AddAfter(objFour, 5);
// 1, 3, 4, 5, 2
5) LinkedList nie stosuje się we wszystkich zagadnieniach. Poniżej przedstawiam wyniki czasu działa różnych operacji na LinkedList i List. Wyniki są przedstawiane w milisekundach dla tysiąca, 10 tysięcy, 100 tysięcy oraz miliona elementów w listach. Na początku implementacja:
var list = new List<int>();
var linkedList = new LinkedList<int>();
Stopwatch watchLinkedList = new Stopwatch();
Stopwatch watchList = new Stopwatch();
5a) Dodawanie elementu na końcu listy.
watchList.Start();
for (int i = 0; i < counts; i++)
{
list.Add(i);
}
watchList.Stop();
watchLinkedList.Start();
for (int i = 0; i < counts; i++)
{
linkedList.AddLast(i);
}
watchLinkedList.Stop();
Wykres jest przedstawiony w skali liniowej. Poniżej tabela z wynikami:
| Add Last |
|---|
| | LinkedList | List |
| 1,000 | 0 | 0 |
| 10,000 | 0 | 0 |
| 100,000 | 9 | 1 |
| 1,000,000 | 106 | 13 |
| 10,000,000 | 2770 | 256 |
Bardzo dokładnie widać, że czas dodawania elementu na koniec listy dla LinkedList jest większy niż dla List.
5b) Dodawanie elementu na początku listy
watchList.Start();
for (int i = 0; i < counts; i++)
{
list.Insert(0,i);
}
watchList.Stop();
watchLinkedList.Start();
for (int i = 0; i < counts; i++)
{
linkedList.AddFirst(i);
}
watchLinkedList.Stop();
| Add First |
|---|
| | LinkedList | List |
| 1,000 | 0 | 0 |
| 10,000 | 0 | 25 |
| 100,000 | 8 | 2347 |
| 1,000,000 | 97 | 274540 |
Wykres jest przedstawiony w skali logarytmicznej. Tutaj dokładnie widać, że czas dla List jest dużo większy od LinkedList. Dla 100 tys. jest około 300 razy większy, a dla miliona elementów jest z 3 000 razy większy.
Sprawdźmy co się stanie, gdy porównamy dla LinkedList metodę AddFirst (dodawanie elementu na początek listy) z metodą AddLast (dodawanie elementu na koniec listy). Okazuje się, że czasy dla tych operacji są bardzo zbliżone.
| Add First | Add Last |
|---|
| 1,000 | 0 | 0 |
| 10,000 | 0 | 0 |
| 100,000 | 8 | 9 |
| 1,000,000 | 97 | 106 |
| 10,000,000 | 2775 | 2770 |
5c) Usuwanie podanego elementu z gotowej listy (za pomocą metody Remove(int))
| Remove |
|---|
| | LinkedList | List |
| 1,000 | 0 | 0 |
| 10,000 | 0 | 24 |
| 100,000 | 2 | 2370 |
| 1,000,000 | 30 | 283608 |
Czas dla List<T> przy operacji usunięcia elementów jest bardzo duży. Wiąże się to z koniecznością "przebudowania" listy (klasa List<T> jest zaimplementowania za pomocą
Array).
5d) Sortujemy elementy. Do tego zastosujemy metodę rozszerzającą OrderBy
| OrderBy |
|---|
| | LinkedList | List |
| 1,000 | 0 | 4 |
| 10,000 | 1 | 1 |
| 100,000 | 18 | 19 |
| 1,000,000 | 212 | 233 |
| 10,000,000 | 3335 | 3092 |
Czas poświęcony na sortowanie listy dla obu klas jest bardzo podobny.
5e) Dodawanie elementu w sam środek listy
Kod dla List:
for (int i = 0 ; i < counts ; i++)
{
int center = (int)
Math.Floor( (double)list.Count / 2 );
list.Insert( center, i );
}
Kod dla LinkedList:
bool addBefore = false;
LinkedListNode<int> centerNode = linkedList.AddFirst(0); ;
for (int i = 1; i < counts; i++)
{
if (addBefore)
{
centerNode = linkedList.AddBefore( centerNode, i );
addBefore = false;
}
else
{
centerNode = linkedList.AddAfter( centerNode, i );
addBefore = true;
}
}
| Add Inner |
|---|
| | LinkedList | List |
| 1,000 | 1 | 0 |
| 10,000 | 0 | 15 |
| 100,000 | 9 | 1467 |
| 1,000,000 | 155 | 148823 |
| 10,000,000 | 2736 | 19992188 |
Wykres jest przedstawiony w skali logarytmicznej. Operacja na 10 milionach elementach w LinkedList jest podobnie czasochłonna co operacja na 100 tysiącach dla List. W tym eksperymencie ewidentnie widać, że lepiej jest zastosować LinkedList.
Poniżej jest porównanie 3 operacji. Dodawanie elementu na początek listy, w środek i na koniec list. Wyniki są prawie identyczne.
| Add First | Add Inner | Add Last |
|---|
| 1,000 | 0 | 1 | 0 |
| 10,000 | 0 | 0 | 0 |
| 100,000 | 8 | 9 | 9 |
| 1,000,000 | 97 | 155 | 106 |
| 10,000,000 | 2775 | 2736 | 2770 |
5f) Przechodzenie po liście. Dla uproszenie sprawdzę wykonania operacji foreach oraz znajdę liczbę maksymalną.
| Foreach | Max |
|---|
| | LinkedList | List | LinkedLIst | List |
| 1,000 | 0 | 0 | 0 | 0 |
| 10,000 | 0 | 0 | 0 | 0 |
| 100,000 | 1 | 0 | 1 | 1 |
| 1,000,000 | 9 | 5 | 15 | 11 |
| 10,000,000 | 96 | 66 | 165 | 118 |
Wnioski:
LinkedList<T> bardzo dobrze sprawuje się przy modyfikacji (dodawanie i usuwanie) obiektów w liście, natomiast List<T> dobrze sprawdza się przy dodawaniu elementu na końcu listy. Z racja, że LinkedList<T> nie ma indeksu to przechodzenie po liście jest kosztowniejsze niż dla List<T>.
