Kiedy używać listy połączonej nad tablicą / listą tablic?

Tablice mają o (1) losowy dostęp, ale są naprawdę drogie, aby dodawać lub usuwać rzeczy z.

Połączone listy są naprawdę tanie, aby dodawać lub usuwać elementy w dowolnym miejscu i iterację, ale dostęp losowy to O (n).

Aby dodać do innych odpowiedzi, większość implementacji array list rezerwuje dodatkową pojemność na końcu listy, aby nowe elementy mogły być dodawane na końcu listy w czasie O(1). Gdy pojemność listy tablic jest przekroczona, nowa, większa tablica jest alokowana wewnętrznie, a wszystkie stare elementy są kopiowane. Zwykle nowa tablica jest dwukrotnie większa od starej. Oznacza to, że średnio dodawanie nowych elementów na końcu listy tablicy jest operacją O (1) w tych wdrożenia. Więc nawet jeśli nie znasz wcześniej liczby elementów, lista tablic może być szybsza od listy połączonej do dodawania elementów, o ile dodajesz je na końcu. Oczywiście wstawianie nowych elementów w dowolnych miejscach na liście tablicy jest nadal operacją O (n).

Dostęp do elementów z listy tablicy jest również szybszy niż lista połączona, nawet jeśli dostęp jest sekwencyjny. Dzieje się tak dlatego, że elementy tablicy są przechowywane w ciągłej pamięci i mogą być buforowane łatwo. Węzły listy połączonej mogą być potencjalnie rozproszone na wielu różnych stronach.

Zalecałbym używanie listy linkowanej tylko wtedy, gdy wiesz, że będziesz wstawiać lub usuwać elementy w dowolnych miejscach. Listy tablic będą szybsze dla prawie wszystkich innych.

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists są dobre dla write-once-read-many lub appenders, ale złe w Dodaj/usuń z przodu lub pośrodku.

Zaleta list pojawia się, gdy trzeba wstawić elementy w środku i nie chce się zmieniać rozmiaru tablicy i przesuwać rzeczy wokół.

Masz rację, że zazwyczaj tak nie jest. Miałem kilka bardzo konkretnych przypadków, ale nie za wiele.

Są to najczęściej używane implementacje kolekcji.

ArrayList:

• Wstaw/Usuń na końcu ogólnie O (1) najgorszy przypadek O (N)

• Insert/delete in the middle O (n)

• Pobierz dowolną pozycję O(1)

LinkedList:

• Insert/delete in any position O (1) (note if you have a reference to the element)

• Pobierz w środku O (n)

• Pobieranie pierwszego lub ostatniego elementu O(1)

Vector: nie używaj go. Jest to stara implementacja podobna do ArrayList, ale ze wszystkimi metodami zsynchronizowanymi. Nie jest to właściwe podejście do udostępnionej listy w środowisku wielowątkowym.

HashMap

Insert / delete / retrieve by key in O (1)

TreeSet insert/delete / contains in O (log N)

HashSet insert/remove/contains / size in O(1)

Wszystko zależy od tego, jaki rodzaj operacji wykonujesz podczas iteracji, wszystkie struktury danych mają kompromis między czasem a pamięcią i w zależności od naszych potrzeb powinniśmy wybrać odpowiedni DS. Są więc przypadki, w których LinkedList jest szybszy niż array i odwrotnie . Rozważmy trzy podstawowe operacje na strukturach danych.

• Wyszukiwanie

Ponieważ tablica jest indeksową tablicą przeszukiwania struktury danych.get (index) zajmie O(1) czas, podczas gdy linkedlist nie jest indeks DS więc będziesz musiał przejść do indeksu, gdzie indeks

Q.So co za tym stoi ?

Ponieważ tablice są sąsiadującymi blokami pamięci, duże ich fragmenty zostaną załadowane do pamięci podręcznej przy pierwszym dostępie, co sprawia, że dostęp do pozostałych elementów tablicy jest stosunkowo szybki, tak samo jak dostęp do elementów w lokalizacji tablicy odniesienia również zwiększa w ten sposób mniej błędów połowu, Cache location odnosi się do operacji znajdujących się w cache i tym samym wykonać znacznie szybciej w porównaniu do w pamięci, w zasadzie w tablicy maksymalizujemy szanse na dostęp do elementów sekwencyjnych jest w cache. Chociaż połączone listy niekoniecznie znajdują się w ciągłych blokach pamięci, nie ma gwarancji, że elementy, które pojawiają się kolejno na liście, są faktycznie rozmieszczone blisko siebie w pamięci, oznacza to mniej trafień pamięci podręcznej, np. więcej chybień pamięci podręcznej, ponieważ musimy odczyt z pamięci dla każdego dostępu do linkowanego elementu listy, co zwiększa czas potrzebny na dostęp do niego i obniża wydajność, więc jeśli robimy więcej operacji dostępu losowego aka wyszukiwanie, tablica będzie szybka, jak wyjaśniono poniżej.

• Wstawianie

Jest to łatwe i szybkie w LinkedList, ponieważ wstawianie jest o (1) operacja w LinkedList (w Javie) w porównaniu do array, rozważ przypadek, gdy tablica jest pełna, musimy skopiować zawartość do nowej tablicy, jeśli tablica jest pełna co sprawia, że wstawianie elementu do ArrayList O (n) w najgorszym przypadku, podczas gdy ArrayList również musi zaktualizować swój indeks , jeśli wstawisz coś gdziekolwiek poza końcem tablicy, w przypadku linked list nie musimy zmieniać jego rozmiaru, wystarczy zaktualizować wskaźniki.

• delecja

Działa jak insertions i lepiej w LinkedList niż array.

Hmm, Arraylist może być używany w takich przypadkach jak:

1. nie jesteś pewien, ile elementów będzie obecnych
2. ale musisz uzyskać dostęp do wszystkich elementów losowo poprzez indeksowanie

Na przykład, musisz zaimportować i uzyskać dostęp do wszystkich elementów na liście kontaktów (której rozmiar jest dla Ciebie nieznany)

Użyj listy połączonej dla sortowania Radix nad tablicami i dla operacji wielomianowych.

1) Jak wyjaśniono powyżej operacje wstawiania i usuwania dają dobrą wydajność (O(1)) w LinkedList w porównaniu do ArrayList(O (n)). Dlatego jeśli istnieje wymóg częstego dodawania i usuwania w aplikacji, LinkedList jest najlepszym wyborem.

2) operacje wyszukiwania (get) są szybkie w Arraylist(O (1)), ale nie w LinkedList(O (n)), więc jeśli jest mniej operacji dodawania i usuwania oraz więcej operacji wyszukiwania, ArrayList byłoby najlepszym rozwiązaniem.

Myślę, że główną różnicą jest to, czy często trzeba wstawiać lub usuwać rzeczy z góry listy.

W przypadku tablicy, jeśli usuniesz coś z góry listy, złożoność jest o (n), ponieważ wszystkie indeksy elementów tablicy będą musiały się przesunąć.

Z listą połączoną jest o(1), ponieważ wystarczy utworzyć węzeł, ponownie przypisać head i przypisać referencję do next jako poprzedni head.

Przy częstym wstawianiu lub usuwaniu na koniec listy, tablice są preferowane, ponieważ złożoność będzie wynosić o( 1), nie jest wymagane ponowne łączenie, ale dla listy połączonej będzie to o(n), ponieważ musisz przejść od głowicy do ostatniego węzła.

Myślę, że wyszukiwanie zarówno w linkowanych listach, jak i tablicach będzie o (log n), ponieważ prawdopodobnie będziesz używał wyszukiwania binarnego.

Zrobiłem trochę benchmarkingu i stwierdziłem, że Klasa list jest w rzeczywistości szybsza niż LinkedList do losowego wstawiania:

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Potrzeba 900 ms dla linked list i 100 ms dla list class.

Tworzy listy kolejnych liczb całkowitych. Każda nowa liczba całkowita jest wstawiana po liczbie losowej, która jest już na liście. Może Klasa List używa czegoś lepszego niż tablica.

W rzeczywistości pamięć ma ogromny wpływ na wydajność w rzeczywistym przetwarzaniu.

Zwiększone wykorzystanie strumieniowania dysków w przetwarzaniu" dużych danych " w porównaniu z dostępem losowym pokazuje, jak struktura aplikacji wokół tego może znacznie poprawić wydajność na większą skalę.

Jeśli istnieje jakakolwiek możliwość uzyskania dostępu do tablicy sekwencyjnie, która jest zdecydowanie najlepiej działająca. Projektowanie z tym celem powinno być przynajmniej brane pod uwagę, jeśli wydajność jest ważna.