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

Używam wielu list i tablic, ale nie spotkałem jeszcze scenariusza, w którym lista tablic nie mogłaby być używana tak łatwo, jeśli nie łatwiej niż z listy połączonej. Miałem nadzieję, że ktoś poda mi kilka przykładów, kiedy lista z linkami jest znacznie lepsza.

Połączone listy są lepsze niż tablice, gdy:

1. potrzebujesz wstawiania / usuwania z listy w stałym czasie (na przykład w obliczeniach w czasie rzeczywistym, gdzie przewidywalność czasu jest absolutnie krytyczna)

2. nie wiesz, ile elementów będzie na liście. W przypadku tablic może być konieczne ponowne zadeklarowanie i skopiowanie pamięci, jeśli tablica stanie się zbyt duża

3. nie potrzebujesz swobodnego dostępu do żadnych elementów

4. chcesz mieć możliwość wstawiania pozycji na środku listy (np. kolejka priorytetowa)

Tablice są preferowane, gdy:

1. potrzebujesz indeksowanego / swobodnego dostępu do elementów

2. znasz liczbę elementów w tablicy z wyprzedzeniem, aby móc przydzielić odpowiednią ilość pamięci dla tablicy

3. potrzebujesz szybkości podczas iterowania wszystkich elementów w kolejności. Możesz użyć matematyki wskaźnikowej na tablicy, aby uzyskać dostęp do każdego elementu, podczas gdy musisz wyszukać węzeł na podstawie wskaźnika dla każdego elementu na liście połączonej, co może skutkować błędami strony, które mogą skutkować uderzeniami wydajności.

4. pamięć jest problemem. Wypełnione tablice zajmują mniej pamięci niż połączone listy. Każdy element tablicy to tylko dane. Każdy węzeł listy połączonej wymaga danych oraz jednego (lub więcej) wskaźników do innych elementów na liście połączonej.

Listy tablic (takie jak te w .Net) zapewniają zalety tablic, ale dynamicznie przydzielają zasoby za Ciebie, dzięki czemu nie musisz się zbytnio martwić o rozmiar listy i możesz usuwać elementy z dowolnego indeksu bez żadnego wysiłku lub ponownego tasowanie elementów dookoła. Pod względem wydajności arraylists są wolniejsze niż surowe tablice.

Tablice mają swobodny dostęp O (1), ale dodawanie lub usuwanie rzeczy jest naprawdę drogie.

Listy połączone są naprawdę tanie w dodawaniu lub usuwaniu elementów w dowolnym miejscu i iteracji, ale dostęp losowy to O (n).

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 do wielokrotnego zapisu lub dodawania, ale źle dodają / usuwają z przodu lub od środka.

Aby dodać do innych odpowiedzi, większość implementacji list tablicowych rezerwuje dodatkową pojemność na końcu listy, tak aby nowe elementy mogły być dodawane na końcu listy w czasie O (1). W przypadku przekroczenia pojemności listy tablic nowa, większa tablica jest przydzielana 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 tablic jest operacją O (1) w tych implementacjach. Więc nawet jeśli nie znasz z góry liczby elementów, lista tablic może nadal być szybsza niż lista połączona do dodawania elementów, o ile dodajesz je na końcu. Oczywiście wstawianie nowych elementów w dowolnych lokalizacjach na liście tablic jest nadal operacją O (n).

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

Polecam używanie listy połączonej tylko wtedy, gdy wiesz, że będziesz wstawiać lub usuwać elementy w dowolnych lokalizacjach. Listy tablicowe będą szybsze dla prawie wszystkiego innego.

Zaleta list pojawia się, gdy musisz wstawić elementy w środku i nie chcesz zmieniać rozmiaru tablicy i przesuwać rzeczy.

Masz rację, ponieważ zazwyczaj tak nie jest. Miałem kilka bardzo specyficznych przypadków, ale niezbyt wiele.

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

• Badawczy

Ponieważ tablica jest oparta na indeksach, wyszukiwanie struktury danych array.get (index) zajmie O (1) czasu, podczas gdy lista linkowana nie jest indeksem DS, więc będziesz musiał przejść do indeksu, gdzie indeks <= n, n to rozmiar listy połączonej, więc tablica jest szybsza niż połączona lista, gdy mamy swobodny dostęp do elementów.

P: Więc jakie jest piękno tego?

Ponieważ tablice są ciągłymi blokami pamięci, duże fragmenty z nich 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, o ile uzyskujemy dostęp do elementów w lokalizacji odniesienia tablicy, a tym samym mniejszy chwyt misses, lokalizacja pamięci podręcznej odnosi się do operacji znajdujących się w pamięci podręcznej, a tym samym wykonywanych znacznie szybciej niż w pamięci, w zasadzie w tablicy maksymalizujemy szanse na dostęp do elementu sekwencyjnego w pamięci podręcznej. Chociaż połączone listy niekoniecznie muszą znajdować się w ciągłych blokach pamięci, nie ma gwarancji, że elementy, które pojawiają się sekwencyjnie na liście, są faktycznie ułożone blisko siebie w pamięci, oznacza to mniej trafień w pamięci podręcznej, np.

• Wprowadzenie

Jest to łatwe i szybkie w LinkedList, ponieważ wstawianie jest operacją O (1) w LinkedList (w Javie) w porównaniu z tablicą; rozważmy przypadek, gdy tablica jest pełna, musimy skopiować zawartość do nowej tablicy, jeśli tablica się zapełni, co powoduje wstawienie element ArrayList z O (n) w najgorszym przypadku, podczas gdy ArrayList musi również zaktualizować swój indeks, jeśli wstawisz coś w dowolnym miejscu poza końcem tablicy, w przypadku listy połączonej nie musimy zmieniać jej rozmiaru, po prostu musisz wskaźniki aktualizacji.

• Usunięcie

Działa jak wstawienia i lepiej w LinkedList niż tablica.

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

ArrayList:

• wstaw / usuń na końcu ogólnie O (1) najgorszy przypadek O (n)

• wstaw / usuń w środku O (n)

• odzyskaj dowolną pozycję O (1)

Połączona lista:

• wstaw / usuń w dowolnej pozycji O (1) (zwróć uwagę, czy masz odniesienie do elementu)

• odzyskać w środku O (n)

• pobierz pierwszy lub ostatni element O (1)

Wektor: nie używaj go. Jest to stara implementacja podobna do ArrayList, ale z zsynchronizowanymi wszystkimi metodami. Nie jest to poprawne podejście do listy współdzielonej w środowisku wielowątkowym.

HashMap

wstaw / usuń / pobierz za pomocą klucza w O (1)

TreeSet wstaw / usuń / zawiera w O (log N)

HashSet wstaw / usuń / zawiera / rozmiar w O (1)

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

Zwiększone wykorzystanie przesyłania strumieniowego dysków w przetwarzaniu „dużych zbiorów danych” w porównaniu z dostępem swobodnym pokazuje, jak struktura aplikacji wokół tego może znacznie poprawić wydajność na większą skalę.

Jeśli istnieje sposób sekwencyjnego dostępu do tablicy, jest to zdecydowanie najlepszy sposób. Projektowanie z tym jako celem powinno być rozważane przynajmniej, jeśli wydajność jest ważna.

Hmm, Arraylist może być używany w następujących przypadkach, jak sądzę:

1. nie masz pewności, ile elementów będzie obecnych
2. ale musisz mieć dostęp do wszystkich elementów losowo poprzez indeksowanie

Np. Musisz zaimportować i uzyskać dostęp do wszystkich elementów listy kontaktów (których rozmiar nie jest Ci znany)

Użyj połączonej listy do sortowania według radix na tablicach i do operacji wielomianowych.

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

2) Operacje wyszukiwania (metoda pobierania) są szybkie w Arraylist (O (1)), ale nie w LinkedList (O (n)), więc jeśli jest mniej operacji dodawania i usuwania i więcej operacji wyszukiwania, najlepszym rozwiązaniem będzie ArrayList.

Myślę, że główna różnica polega na tym, czy często musisz wstawiać lub usuwać rzeczy z góry listy.

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

W przypadku listy połączonej jest to o (1), ponieważ wystarczy utworzyć węzeł, ponownie przypisać nagłówek i przypisać odniesienie do następnego nagłówka jako poprzedniego.

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

Myślę, że wyszukiwanie w połączonej liście i tablicach będzie o (log n), ponieważ prawdopodobnie będziesz używać wyszukiwania binarnego.

Przeprowadziłem pewne testy porównawcze i stwierdziłem, że klasa list jest w rzeczywistości szybsza niż LinkedList w przypadku 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();
        }
    }
}

Lista połączona zajmuje 900 ms, a klasa list 100 ms.

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

Tablice są zdecydowanie najpowszechniej używanymi strukturami danych. Jednak połączone listy okazują się użyteczne na swój własny, unikalny sposób, gdy tablice są niezgrabne - lub co najmniej drogie.

Listy połączone są przydatne do implementowania stosów i kolejek w sytuacjach, gdy ich rozmiar może się różnić. Każdy węzeł na połączonej liście można wypchnąć lub usunąć bez zakłócania większości węzłów. To samo dotyczy wstawiania / usuwania węzłów gdzieś pośrodku. Jednak w tablicach wszystkie elementy muszą zostać przesunięte, co jest kosztowne pod względem czasu wykonania.

Drzewa binarne i drzewa wyszukiwania binarnego, tabele skrótów i próby to tylko niektóre ze struktur danych, w których - przynajmniej w języku C - potrzebujesz połączonych list jako podstawowego składnika do ich tworzenia.

Jednak list połączonych należy unikać w sytuacjach, w których oczekuje się, że będzie można wywołać dowolny element za pomocą indeksu.

Prostą odpowiedź na pytanie można udzielić za pomocą następujących punktów:

1. Tablice mają być używane, gdy wymagana jest kolekcja elementów danych podobnego typu. Natomiast lista połączona jest zbiorem elementów połączonych z danymi o mieszanym typie, zwanych węzłami.

2. W array można odwiedzić dowolny element w czasie O (1). Podczas gdy na liście połączonej musielibyśmy przejść całą połączoną listę od głowy do wymaganego węzła, zajmując czas O (n).

3. W przypadku tablic należy wstępnie zadeklarować określony rozmiar. Ale połączone listy mają dynamiczny rozmiar.