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

176

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.

bez twarzy1_14
źródło
W Javie ArrayList i LinkedList używają dokładnie tego samego kodu innego niż konstruktor. Twoja „lista tablic ... używana równie łatwo lub łatwiej niż lista połączona” nie ma sensu. Podaj przykład, w którym ArrayList jest „łatwiejszy” niż LinkedList.
S.Lott,
2
Sprawdź to również, stackoverflow.com/questions/322715/ ...
NoNaMe
Możliwy duplikat Array kontra lista połączona
Hawkeye Parker
3
S.Lott To nieprawda. Java ArrayList to opakowanie otaczające tablicę z dodanymi niektórymi funkcjami narzędziowymi. Lista połączona to oczywiście lista połączona. developer.classpath.org/doc/java/util/ArrayList-source.html
kingfrito_5005

Odpowiedzi:

261

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.

Lamar
źródło
7
Dobry początek, ale pomija to ważne rzeczy: listy wspierają współdzielenie struktury, tablice są gęstsze i mają lepszą lokalizację.
Darius Bacon
1
Praktycznie różnica w wydajności między tablicami a tablicami jest pomijalna. Zakłada się, że porównujesz porównywalne i, na przykład, gdy znasz rozmiar z wyprzedzeniem, mówisz o tym arrayliście.
Svick
40
Od kiedy LinkedList ma O (1) wstawia / usuwa (co, jak przypuszczam, masz na myśli, gdy mówisz o stałym czasie wstawiania / usuwania )? Wstawianie rzeczy do środka LinkedList jest zawsze O (n)
Pacerier,
28
LinkedLists mają wstawki O (1), jeśli już znajdujesz się w miejscu wstawienia (za pośrednictwem iteratora). Jednak nie zawsze.
Adam
4
Używanie połączonych list jako kolejek priorytetowych to bardzo głupi pomysł. Dynamiczne sterty oparte na tablicach umożliwiają O (lg n) zamortyzowane wstawianie i logarytmiczne usuwanie min w najgorszym przypadku i należą do najszybszych praktycznych struktur kolejki priorytetowej.
Fred Foo
54

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).

Dustin
źródło
3
Usuwanie elementów z końca tablicy jest ciągłe, podobnie jak wstawianie / usuwanie elementów z dowolnego końca połączonej listy. W środku ... nie za bardzo.
Joey,
1
@Joey nie jest wstawieniem / usunięciem na końcu połączonej listy O (n)? O ile nie jesteś już umieszczony na przedostatnim łączu, nadal będziesz potrzebować O (n) kroków, aby znaleźć ostatni element, prawda?
Alex Moore-Niemi
@ AlexMoore-Niemi: Tak, jeśli chodzi o listę połączoną pojedynczo. Ale wiele z nich ma linki do przodu i do tyłu, dzięki czemu zachowują wskazówki na każdym końcu.
Joey
2
Posiadanie podwójnie połączonych list spowoduje, że będziesz wyszukiwać do przodu i do tyłu, chyba że twój LL ma uporządkowane wartości ... a nadal najgorszym scenariuszem jest O (n)
krzywa
„Połączone listy są naprawdę tanie w dodawaniu lub usuwaniu elementów w dowolnym miejscu i iteracji” nie jest do końca prawdą. Jeśli chcę usunąć element, który znajduje się na środku połączonej listy, będę musiał iterować od początku, aż dotrę do tego elementu na liście. Jego czas O (n / 2), gdzie n = liczba pozycji na liście. Z twojej odpowiedzi wynika, że ​​sugerujesz jej stały czas O (1), jakby był w tablicy. Dodawanie / usuwanie z węzła głównego / głównego połączonej listy jest stałe.
Yawar Murtaza
22
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.

Vpn_talent
źródło
14

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.

Jay Conrod
źródło
1
Ponadto można również implementować listy połączone (w sensie typu danych abstrakcyjnych) przy użyciu tablic dynamicznych. W ten sposób możesz wykorzystać pamięć podręczną komputera, mając zamortyzowane wstawienia i usunięcia o stałym czasie na początku listy, a także zamortyzowane wstawienia i usunięcia w stałym czasie w środku listy, gdy masz indeks elementu, po którym wstawienie musi być wykonane lub indeks elementu do usunięcia (nie są potrzebne żadne przesunięcia / cofnięcia zmian). Dobrym odniesieniem do tego jest CLRS 10.3 .
Domenico De Felice
7

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.

Uri
źródło
Przesuwanie i zmiana rozmiaru tablicy jest tym, co faktycznie dzieje się, gdy wykonujesz inwersje w środku. Będziesz potrzebować zmiany bez zmiany rozmiaru tylko wtedy, gdy nie osiągniesz granicy amortyzacji.
Securecurve
3

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.

Harleen
źródło
2

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)

Praveen Kumar Verma
źródł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.

user3150186
źródło
0

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)

Raghu
źródło
0

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

gizgok
źródło
0

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.

Avanish Kumar
źródło
0

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.

Curious_goat
źródło
0

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.

Emil Albert
źródło
Lista to interfejs, a nie klasa
borgmater
0

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.

fotoniczny
źródło
0

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.

Rohit Goynar
źródło