Tablica kontra lista połączona

Dlaczego ktoś miałby chcieć używać listy połączonej nad tablicą?

Kodowanie listy połączonych jest bez wątpienia nieco większym wysiłkiem niż użycie tablicy i można się zastanawiać, co uzasadniałoby dodatkowy wysiłek.

Wydaje mi się, że wstawianie nowych elementów jest trywialne na liście połączonej, ale jest dużym obowiązkiem w tablicy. Czy istnieją inne zalety używania połączonej listy do przechowywania zestawu danych w porównaniu do przechowywania ich w tablicy?

To pytanie nie jest duplikatem tego pytania, ponieważ drugie pytanie dotyczy konkretnej klasy Java, podczas gdy to pytanie dotyczy ogólnych struktur danych.

• Łatwiej jest przechowywać dane o różnych rozmiarach na połączonej liście. Tablica zakłada, że ​​każdy element ma dokładnie taki sam rozmiar.
• Jak już wspomniałeś, lista połączona łatwiej rośnie organicznie. Rozmiar tablicy musi być znany z wyprzedzeniem lub ponownie utworzony, gdy musi się rozwijać.
• Przetasowanie listy połączonej to tylko kwestia zmiany tego, co wskazuje na co. Przetasowanie tablicy jest bardziej skomplikowane i / lub zajmuje więcej pamięci.
• Tak długo, jak wszystkie iteracje odbywają się w kontekście „foreach”, nie tracisz żadnej wydajności w iteracji.

Innym dobrym powodem jest to, że połączone listy dobrze nadają się do wydajnych implementacji wielowątkowych. Powodem tego jest to, że zmiany mają charakter lokalny - wpływają tylko na wskaźnik lub dwa dla wstawiania i usuwania w zlokalizowanej części struktury danych. Tak więc możesz mieć wiele wątków działających na tej samej połączonej liście. Co więcej, możliwe jest tworzenie wersji bez zamków przy użyciu operacji typu CAS i całkowite unikanie ciężkich zamków.

Z połączoną listą iteratory mogą również przechodzić przez listę podczas modyfikacji. W optymistycznym przypadku, gdy modyfikacje nie kolidują, iteratory mogą kontynuować bez rywalizacji.

W przypadku tablicy każda zmiana, która modyfikuje rozmiar tablicy, prawdopodobnie będzie wymagać zablokowania dużej części tablicy, a tak naprawdę jest to rzadkie, że odbywa się to bez globalnej blokady całej tablicy, więc modyfikacje zatrzymują światowe sprawy.

Wikipedia ma bardzo dobrą sekcję na temat różnic.

Listy połączone mają kilka zalet w stosunku do tablic. Elementy można wstawiać na listy połączone w nieskończoność, podczas gdy tablica w końcu albo się zapełni, albo będzie wymagać zmiany rozmiaru, co jest kosztowną operacją, która może nie być możliwa nawet w przypadku fragmentacji pamięci. Podobnie tablica, z której usunięto wiele elementów, może stać się niepotrzebnie pusta lub wymagać zmniejszenia.

Z drugiej strony tablice umożliwiają losowy dostęp, podczas gdy połączone listy umożliwiają tylko sekwencyjny dostęp do elementów. W rzeczywistości listy pojedynczo połączone można przeglądać tylko w jednym kierunku. To sprawia, że ​​listy połączone nie są odpowiednie dla aplikacji, w których przydatne jest szybkie wyszukiwanie elementu według jego indeksu, takich jak heapsort. Dostęp sekwencyjny do tablic jest również szybszy niż na listach połączonych na wielu komputerach ze względu na lokalizację referencji i pamięci podręcznych danych. Listy połączone prawie nie korzystają z pamięci podręcznej.

Kolejną wadą list połączonych jest dodatkowe miejsce do przechowywania potrzebnych referencji, co często sprawia, że ​​są one niepraktyczne w przypadku list małych elementów danych, takich jak znaki lub wartości logiczne. Może być również powolny, a przy naiwnym alokatorze marnotrawstwem przydzielanie pamięci osobno dla każdego nowego elementu, problem zwykle rozwiązywany za pomocą pul pamięci.

http://en.wikipedia.org/wiki/Linked_list

Dodam jeszcze - listy mogą działać jako czysto funkcjonalne struktury danych.

Na przykład możesz mieć zupełnie inne listy, które mają tę samą sekcję końcową

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

to znaczy:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

bez konieczności kopiowania danych wskazywanych przez ado bi c.

Dlatego są one tak popularne w językach funkcjonalnych, które wykorzystują niezmienne zmienne - prependa tailoperacje mogą odbywać się swobodnie bez konieczności kopiowania oryginalnych danych - bardzo ważne cechy, gdy traktujesz dane jako niezmienne.

Oprócz tego, że wstawianie na środku listy jest łatwiejsze - znacznie łatwiej jest usunąć ze środka połączonej listy niż z tablicy.

Ale szczerze mówiąc, nigdy nie korzystałem z połączonej listy. Ilekroć potrzebowałem szybkiego wstawiania i usuwania, potrzebowałem też szybkiego wyszukiwania, więc poszedłem do HashSet lub Dictionary.

Scalenie dwóch połączonych list (szczególnie dwóch podwójnie połączonych list) jest znacznie szybsze niż scalenie dwóch tablic (zakładając, że scalanie jest destrukcyjne). Pierwszy przyjmuje O (1), drugi przyjmuje O (n).

EDYCJA: Aby wyjaśnić, miałem na myśli „scalenie” tutaj w nieuporządkowanym sensie, a nie w rodzaju scalania. Być może „konkatenacja” byłaby lepszym słowem.

Powszechnie niedocenianym argumentem dla ArrayList i przeciwko LinkedList jest to, że LinkedLists są niewygodne podczas debugowania . Czas poświęcony przez programistów konserwacji na zrozumienie programu, np. Na znalezienie błędów, wzrost i IMHO czasami nie usprawiedliwia nanosekund w poprawie wydajności lub bajtach zużycia pamięci w aplikacjach korporacyjnych. Czasami (cóż, oczywiście, że zależy to od rodzaju aplikacji) lepiej jest marnować kilka bajtów, ale mieć aplikację, którą można łatwiej utrzymać lub łatwiej zrozumieć.

Na przykład w środowisku Java i przy użyciu debugera Eclipse debugowanie ArrayList ujawni bardzo łatwą do zrozumienia strukturę:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

Z drugiej strony, oglądanie zawartości LinkedList i znajdowanie określonych obiektów staje się koszmarem klikania Rozwiń drzewo, nie wspominając już o kosztach poznawczych potrzebnych do odfiltrowania wewnętrznych elementów LinkedList:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

Po pierwsze, w połączonych listach w C ++ nie powinno być większych problemów z pracą niż z tablicą. Możesz użyć std :: list lub listy wskaźników doładowania dla list połączonych. Kluczowe problemy z połączonymi listami a tablicami to dodatkowe miejsce wymagane na wskaźniki i straszny losowy dostęp. Jeśli chcesz, powinieneś użyć listy połączonej

• nie potrzebujesz losowego dostępu do danych
• będziesz dodawać / usuwać elementy, szczególnie na środku listy

Dla mnie jest tak

1. Dostęp

   • Listy połączone umożliwiają tylko sekwencyjny dostęp do elementów. Zatem złożoność algorytmiczna jest rzędu O (n)
   • Tablice umożliwiają losowy dostęp do jego elementów, a zatem złożoność jest rzędu O (1)

2. Przechowywanie

   • Listy połączone wymagają dodatkowego miejsca do przechowywania referencji. To sprawia, że ​​są one niepraktyczne w przypadku list małych elementów danych, takich jak znaki lub wartości logiczne.
   • Tablice nie potrzebują dodatkowej pamięci, aby wskazać następny element danych. Dostęp do każdego elementu można uzyskać za pomocą indeksów.

3. Rozmiar

   • Rozmiar połączonych listów jest z natury dynamiczny.
   • Rozmiar tablicy jest ograniczony do deklaracji.

4. Wstawianie / usuwanie

   • Elementy można wstawiać i usuwać na połączonych listach w nieskończoność.
   • Wstawianie / usuwanie wartości w tablicach jest bardzo kosztowne. Wymaga ponownego przydzielenia pamięci.

Dwie rzeczy:

Kodowanie połączonej listy to bez wątpienia trochę więcej pracy niż użycie tablicy i zastanawiał się, co uzasadniałoby dodatkowy wysiłek.

Nigdy nie koduj połączonej listy, używając C ++. Wystarczy użyć STL. To, jak trudne jest wdrożenie, nigdy nie powinno być powodem wyboru jednej struktury danych zamiast drugiej, ponieważ większość z nich jest już zaimplementowana.

Jeśli chodzi o rzeczywiste różnice między tablicą a połączoną listą, najważniejsze dla mnie jest to, jak planujesz używać struktury. Użyję terminu wektor, ponieważ jest to termin dla tablicy o zmiennym rozmiarze w C ++.

Indeksowanie do listy połączonej jest powolne, ponieważ musisz przejść przez listę, aby dostać się do podanego indeksu, podczas gdy wektor jest ciągły w pamięci i możesz się tam dostać za pomocą matematyki wskaźnika.

Dołączanie na końcu lub na początku listy połączonej jest łatwe, ponieważ wystarczy zaktualizować tylko jeden link, w przypadku którego w wektorze może być konieczna zmiana rozmiaru i skopiowanie zawartości.

Usunięcie elementu z listy jest łatwe, ponieważ wystarczy złamać parę linków, a następnie połączyć je z powrotem. Usunięcie elementu z wektora może być szybsze lub wolniejsze, w zależności od tego, czy zależy Ci na porządku. Zamiana ostatniego elementu na wierzch elementu, który chcesz usunąć, jest szybsza, a przesunięcie wszystkiego po nim jest wolniejsze, ale zachowuje porządek.

Eric Lippert niedawno napisał post na temat jednego z powodów, dla których tablice należy stosować zachowawczo.

Szybkie wstawianie i usuwanie są rzeczywiście najlepszymi argumentami dla połączonych list. Jeśli Twoja struktura rośnie dynamicznie, a dostęp do dowolnego elementu nie jest wymagany (np. Dynamiczne stosy i kolejki), połączone listy są dobrym wyborem.

Oto szybki: Usuwanie przedmiotów jest szybsze.

Lista połączona jest szczególnie przydatna, gdy kolekcja stale się powiększa i kurczy. Na przykład trudno sobie wyobrazić próbę zaimplementowania kolejki (dodaj do końca, usuń z przodu) za pomocą tablicy - spędzasz cały swój czas na robieniu rzeczy. Z drugiej strony jest to banalne z listą połączoną.

Oprócz dodawania i usuwania ze środka listy, bardziej lubię połączone listy, ponieważ mogą się dynamicznie powiększać i zmniejszać.

Nikt nigdy nie koduje już własnej listy, do której prowadzi link. To byłoby głupie. Założenie, że użycie listy połączonej wymaga więcej kodu, jest po prostu błędne.

W dzisiejszych czasach tworzenie połączonej listy jest tylko ćwiczeniem dla studentów, aby mogli zrozumieć tę koncepcję. Zamiast tego wszyscy korzystają z gotowej listy. W C ++, w oparciu o opis w naszym pytaniu, prawdopodobnie oznaczałoby to wektor stl ( #include <vector>).

Dlatego wybór połączonej listy w porównaniu z tablicą polega wyłącznie na ważeniu różnych charakterystyk każdej struktury w zależności od potrzeb Twojej aplikacji. Przezwyciężenie dodatkowego obciążenia związanego z programowaniem powinno mieć zerowy wpływ na decyzję.

To naprawdę kwestia wydajności, narzut związany z wstawianiem, usuwaniem lub przenoszeniem (tam, gdzie nie jest to po prostu zamiana) elementów na połączonej liście jest minimalny, tj. Sama operacja to O (1), werset O (n) dla tablicy. Może to mieć znaczącą różnicę, jeśli intensywnie operujesz na liście danych. Wybrałeś typy danych w oparciu o to, jak będziesz na nich operował, i wybierasz najbardziej efektywny dla używanego algorytmu.

Tablice mają sens tam, gdzie dokładna liczba elementów będzie znana i gdzie wyszukiwanie według indeksu ma sens. Na przykład, jeśli chciałbym zapisać dokładny stan mojego wyjścia wideo w danym momencie bez kompresji, prawdopodobnie użyłbym tablicy o rozmiarze [1024] [768]. To zapewni mi dokładnie to, czego potrzebuję, a lista byłaby o wiele, znacznie wolniejsza, aby uzyskać wartość danego piksela. W miejscach, w których tablica nie ma sensu, istnieją zazwyczaj lepsze typy danych niż lista do skutecznego radzenia sobie z danymi.

Lista połączonych tablic Vs:

1. Alokacja pamięci tablic czasami się nie powiedzie z powodu fragmentacji pamięci.
2. Buforowanie jest lepsze w tablicach, ponieważ wszystkie elementy mają przydzielone ciągłe miejsce w pamięci.
3. Kodowanie jest bardziej złożone niż tablice.
4. Brak ograniczenia rozmiaru na liście połączonej, w przeciwieństwie do tablic
5. Wstawianie / usuwanie jest szybsze na liście połączonej, a dostęp jest szybszy w tablicach.
6. Lista połączona lepiej z wielowątkowego punktu widzenia.

ponieważ tablice mają charakter statyczny, dlatego wszystkie operacje, takie jak przydział pamięci, występują tylko w czasie kompilacji. Procesor musi więc włożyć mniej wysiłku w środowisko wykonawcze.

Załóżmy, że masz uporządkowany zestaw, który również chcesz zmodyfikować, dodając i usuwając elementy. Ponadto potrzebujesz zdolności do zachowania odniesienia do elementu w taki sposób, aby później uzyskać poprzedni lub następny element. Na przykład lista rzeczy do zrobienia lub zestaw akapitów w książce.

Najpierw powinniśmy zauważyć, że jeśli chcesz zachować odniesienia do obiektów poza samym zestawem, prawdopodobnie skończysz przechowywanie wskaźników w tablicy, zamiast przechowywania samych obiektów. W przeciwnym razie nie będziesz mógł wstawić do tablicy - jeśli obiekty zostaną osadzone w tablicy, będą się przesuwać podczas wstawiania, a wszelkie wskaźniki do nich staną się nieprawidłowe. To samo dotyczy indeksów tablic.

Pierwszym problemem, jak sam zauważyłeś, jest lista połączona ze wstawianiem, która umożliwia wstawianie w O (1), ale tablica zazwyczaj wymaga O (n). Problem ten można częściowo rozwiązać - możliwe jest stworzenie struktury danych, która zapewnia tablicowy interfejs dostępu uporządkowanego, w którym zarówno odczyt, jak i zapis są w najgorszym przypadku logarytmiczne.

Twoim drugim, poważniejszym problemem jest to, że biorąc pod uwagę element znajdujący następny element, jest O (n). Jeśli zestaw nie został zmodyfikowany, możesz zatrzymać indeks elementu jako referencję zamiast wskaźnika, dzięki czemu find-next jest operacją O (1), ale ponieważ wszystko, co masz, to wskaźnik do samego obiektu i nie ma mowy w celu ustalenia jego bieżącego indeksu w tablicy innej niż skanowanie całej „tablicy”. Jest to problem nie do przezwyciężenia dla tablic - nawet jeśli możesz zoptymalizować wstawienia, nie możesz nic zrobić, aby zoptymalizować operację znajdowania następnego typu.

W tablicy masz uprawnienia dostępu do dowolnego elementu w czasie O (1). Z tego powodu nadaje się do operacji takich jak Szybkie wyszukiwanie binarne itp. Z drugiej strony powiązana lista jest odpowiednia do usuwania wstawiania, jak w czasie O (1). Oba mają zarówno zalety, jak i wady, a preferowanie jednej z drugiej sprowadza się do tego, co chcesz wdrożyć.

- Większe pytanie brzmi: czy możemy mieć hybrydę obu. Coś jak Python i Perl implementują jako listy.

Połączona lista

Bardziej preferowane jest wstawianie! Zasadniczo robi to, że zajmuje się wskaźnikiem

1 -> 3 -> 4

Wstaw (2)

1 ........ 3 ...... 4
..... 2

Wreszcie

1 -> 2 -> 3 -> 4

Jedna strzała z 2 punktów na 3 i strzałka 1 punktu na 2

Prosty!

Ale z tablicy

| 1 | 3 | 4 |

Wstaw (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Każdy może sobie wyobrazić różnicę! Tylko dla 4 indeksów wykonujemy 3 kroki

Co jeśli długość tablicy wynosi milion? Czy macierz jest wydajna? Odpowiedź brzmi nie! :)

To samo dotyczy usuwania! Na liście połączonej możemy po prostu użyć wskaźnika i zerować element, a następnie w klasie obiektów! Ale w przypadku tablicy musimy wykonać shiftLeft ()

Mam nadzieję, że to pomaga! :)

Lista połączona jest bardziej narzutem do utrzymania niż tablicą, wymaga również dodatkowej pamięci, wszystkie te punkty są uzgodnione. Ale jest kilka rzeczy, których nie potrafi tablica. W wielu przypadkach przypuśćmy, że potrzebujesz tablicy o długości 10 ^ 9, której nie możesz zdobyć, ponieważ musi istnieć jedno ciągłe miejsce w pamięci. Powiązana lista może być tutaj wybawcą.

Załóżmy, że chcesz przechowywać wiele rzeczy z danymi, a następnie można je łatwo rozszerzyć na połączonej liście.

Kontenery STL zwykle mają zaimplementowaną listę powiązaną za sceną.

1- Połączona lista jest dynamiczną strukturą danych, dzięki czemu może się zwiększać i zmniejszać w czasie wykonywania poprzez przydzielanie i zwalnianie pamięci. Dlatego nie ma potrzeby podawania początkowego rozmiaru połączonej listy. Wstawianie i usuwanie węzłów jest naprawdę łatwiejsze.

2- rozmiar połączonej listy może się zwiększać lub zmniejszać w czasie wykonywania, aby nie marnować pamięci. W przypadku tablicy marnuje się dużo pamięci, na przykład jeśli deklarujemy tablicę o rozmiarze 10 i przechowujemy w niej tylko 6 elementów, wówczas marnuje się przestrzeń 4 elementów. Na połączonej liście nie ma takiego problemu, ponieważ pamięć jest przydzielana tylko w razie potrzeby.

3- Struktury danych, takie jak stos i kolejki, można łatwo wdrożyć za pomocą połączonej listy.

Jedynym powodem do korzystania z połączonej listy jest to, że wstawianie elementu jest łatwe (również usuwanie).

Wadą może być to, że wskaźniki zajmują dużo miejsca.

A o tym kodowanie jest trudniejsze: zwykle nie potrzebujesz listy połączonych kodów (lub tylko raz), są one zawarte w STL i nie jest to tak skomplikowane, jeśli nadal musisz to zrobić.

również uważam, że lista linków jest lepsza niż tablice. ponieważ przeglądamy listę linków, ale nie tablice

W zależności od języka można rozważyć niektóre z tych wad i zalet:

Język programowania C : W przypadku korzystania z listy połączonej (zwykle poprzez wskaźniki strukturalne) należy zwrócić szczególną uwagę na to, aby nie wyciekać pamięć. Jak wspomniano wcześniej, połączone listy można łatwo przetasować, ponieważ wszystko, co robimy, zmienia wskaźniki, ale czy będziemy pamiętać, aby wszystko uwolnić?

Java : Java ma automatyczne wyrzucanie elementów bezużytecznych, więc wyciek pamięci nie będzie problemem, ale przed programistą wysokiego poziomu ukryte są szczegóły implementacji listy połączonej. Metody takie jak usunięcie węzła ze środka listy są bardziej skomplikowane niż procedura, niż niektórzy użytkownicy tego języka mogą oczekiwać.

Dlaczego lista połączona w tablicy? Jak już niektórzy powiedzieli, większa szybkość wstawiania i usuwania.

Ale może nie musimy żyć z ograniczeniami któregokolwiek z nich i jednocześnie uzyskać to, co najlepsze, jednocześnie ... eh?

Do usuwania tablic można użyć bajtu „Usunięte”, który reprezentuje fakt, że wiersz został usunięty, a zatem ponowne ustawienie tablicy nie jest już konieczne. Aby zmniejszyć ciężar wstawiania lub szybko zmieniających się danych, użyj do tego połączonej listy. Następnie, odnosząc się do nich, najpierw przeszukaj swoją logikę, a potem drugą. Dlatego użycie ich w kombinacji daje najlepsze z obu.

Jeśli masz naprawdę dużą tablicę, możesz połączyć ją z inną, znacznie mniejszą tablicą lub połączoną listą, na której mniejsza zawiera 20, 50, 100 ostatnio używanych pozycji. Jeśli potrzebnej nie ma na krótszej połączonej liście lub tablicy, przejdziesz do dużej tablicy. Jeśli tam znajdziesz, możesz dodać go do mniejszej połączonej listy / tablicy, zakładając, że „rzeczy ostatnio używane są najbardziej podobne do ponownego użycia” (i tak, możliwe, że usunęło ostatnio używany element z listy). Co jest prawdą w wielu przypadkach i rozwiązało problem, który musiałem rozwiązać w module sprawdzania uprawnień zabezpieczeń .ASP z łatwością, elegancją i imponującą szybkością.

Podczas gdy wielu z was poruszyło główne zalety / różnice połączonej listy w porównaniu do tablicy, większość porównań dotyczy tego, jak jedno jest lepsze / gorsze od drugiego. możesz zrobić losowy dostęp w tablicy, ale nie jest to możliwe na połączonej liście i innych. Zakłada się jednak, że listy łączy i tablice będą stosowane w podobnej aplikacji. Prawidłowa odpowiedź powinna jednak wskazywać, w jaki sposób lista łączy byłaby preferowana w stosunku do tablicy i odwrotnie w przypadku konkretnego wdrożenia aplikacji. Załóżmy, że chcesz wdrożyć aplikację słownika, czego byś użył? Tablica: mmm, pozwoli to na łatwe wyszukiwanie poprzez wyszukiwanie binarne i inne algo wyszukiwania ... ale zastanówmy się, jak lista linków może być lepsza .. Powiedz, że chcesz przeszukać "Blob" w słowniku. Czy miałoby sens mieć listę linków A-> B-> C-> D ---->

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Czy powyższe podejście jest lepsze, czy płaski zestaw [Adama, Jabłka, Banana, Kropelki, Kota, Jaskini]? Czy byłoby to w ogóle możliwe z tablicą? Główną zaletą listy linków jest to, że element może wskazywać nie tylko na następny element, ale także na inną listę linków / tablicę / stertę / lub inną lokalizację pamięci. Macierz jest jedną płaską, zaraźliwą pamięcią podzieloną na bloki wielkości elementu, który ma przechowywać. Z drugiej strony lista łączy to fragmenty nieinwazyjnych jednostek pamięci (mogą mieć dowolny rozmiar i mogą przechowywać dowolne elementy) i wskazywać na każdy z nich w inny sposób, jak chcesz. Podobnie powiedzmy, że tworzysz napęd USB. Czy chcesz teraz zapisać pliki jako dowolną tablicę lub listę linków? Myślę, że masz pomysł, na co wskazuję :)