Tablica kontra lista połączona

200

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.

Onorio Catenacci
źródło
1
Powiązane - Kiedy używać LinkedList <> ponad ArrayList <>? - to Java, ale tablice (ArrayList) i listy łączy przypuszczalnie mają taką samą wydajność w każdym języku.
Bernhard Barker
1
@rootTraveller Właściwie to pytanie byłoby duplikatem tego pytania, ponieważ moje pytanie zostało opublikowane jako pierwsze.
Onorio Catenacci

Odpowiedzi:

147
  • Ł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.
Ryan
źródło
19
Jak przedmioty o różnych rozmiarach są traktowane inaczej? Połączona lista albo używa stałej struktury z następnym polem (wymaga stałego rozmiaru), albo przechowuje wskaźnik do danych w samochodzie (rozmiar zmiennej OK). Oba podejścia są równie łatwe z wektorem. To samo dotyczy tasowania.
Brian
32
Powiedziałbym, że przetasowanie tablicy jest mniej skomplikowane.
Hugh Allen
23
Ta odpowiedź jest niepoprawna i myląca. (z wyjątkiem konieczności znajomości rozmiaru tablicy, gdy ją deklarujesz)
Robert Paulson
35
Czy iteracja połączonej listy nie byłaby wolniejsza z powodu lokalizacji danych?
Firas Assaad
6
@ Rick, wektory zazwyczaj ogólnie przydzielają potrzebne miejsce, aby nie musiały przydzielać nowego miejsca za każdym razem, gdy zwiększa się rozmiar. Powoduje to, że wektory zwykle wymagają znacznie mniej pamięci, a nie więcej niż listy połączone.
Winston Ewert,
179

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.

Alex Miller
źródło
9
Alex - to ciekawe zagadnienie, które nigdy nie przyszło mi do głowy. Bardzo dobra odpowiedź. Głosowałbym za tobą dwa razy, gdybym mógł. :-)
Onorio Catenacci
5
Rzuć okiem na listy pominięć (w szczególności ConcurrentSkipListMap w Javie 6), aby uzyskać dobry pomysł na to, gdzie możesz to zrobić. CSLM to posortowana, współbieżna mapa o doskonałej wydajności. Daleko, znacznie lepiej niż zsynchronizowana mapa drzewa. tech.puredanger.com/2007/10/03/skip-lists
Alex Miller
... oprócz tego, że ConcurrentSkipListMapalbo ConcurrentSkipListMapnie są listy, nawet jeśli „Lista” występuje gdzieś w ich imieniu. Oba wymagają kluczy, które zostaną posortowane i unikalne. Jeśli potrzebujesz List, tzn. Takiej struktury danych, która zezwala na duplikowanie elementów w dowolnej kolejności, nie jest to odpowiednie i musisz zrobić wiele, aby stworzyć strukturę danych, która LinkedListjest jednocześnie aktualizowalna. Jeśli potrzebujesz tylko równoczesnej kolejki lub deque, cóż, istnieją nawet przykłady, ale jednocześnie List… Nie jestem przekonany, że jest to nawet możliwe.
Holger
128

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

Jonas Klemming
źródło
4
To idealna odpowiedź. Zwięźle opisuje zalety i wady obu.
Rick
dziękuję)) bardzo prosty, ale nie widziałem go na wiki)
Timur Fayzrakhmanov
58

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.

Brian
źródło
4
Jeszcze jedna bardzo interesująca uwaga, której nigdy bym nie wymyślił. Dziękuję Ci.
Onorio Catenacci
Jak mogę to zrobić w Pythonie?
nadmierna wymiana
29

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.

Tom Ritter
źródło
2
To prawda, że ​​wstawianie i usuwanie następuje po przeszukiwaniu przez większość czasu, więc należy również wziąć pod uwagę sumę złożoności czasu.
MA Hossain Tonu,
28

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.

szaleństwo
źródło
2
Tylko jeśli po prostu dołączasz jedną listę do drugiej. Jeśli faktycznie łączysz dwie posortowane listy, zajmie to więcej niż O (1).
Herms
3
@Herms, ale możesz scalić dwie posortowane połączone listy bez przydzielania dodatkowej pamięci, po prostu przechodząc przez obie listy i odpowiednio ustawiając wskaźniki. Scalenie dwóch tablic zwykle wymaga co najmniej jednej dodatkowej tablicy.
Paul Tomblin
1
Tak, scalanie list jest bardziej wydajne pod względem pamięci, ale tak naprawdę nie komentowałem tego. Mówienie o łączeniu list połączonych to O (1) jest bardzo mylące bez wyjaśnienia sprawy.
Herms
Scalanie list @Herms nie jest bardziej wydajne pod względem pamięci niż scalanie tablic w dowolnym rozsądnym modelu danych.
Alexei Averchenko
2
Aleksiej Awerczenko: Łączenie dwóch list, a nawet scalanie i sortowanie dwóch posortowanych list, można wykonać w miejscu, z pamięcią O (1). Łączenie dwóch tablic wymaga koniecznie pamięci O (n), chyba że tablice już sąsiadują ze sobą w pamięci. Myślę, że celem, do którego dążysz jest to, że zarówno lista n elementów, jak i tablica n elementów zajmują pamięć O (n), ale współczynnik jest wyższy dla list połączonych.
rampion
17

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>
mhaller
źródło
17

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
David Nehme
źródło
14

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.
Sulman
źródło
Masz 2 cyfry 2 i 2 cyfrę 3 :)
Hengameh
Możemy zadeklarować pustą tablicę, a następnie dodawać dane zgodnie z wymaganiami. Jak to sprawia, że ​​wciąż ma stały rozmiar?
HebleV
11

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.

bradtgmurray
źródło
Jak powiedziałem komuś powyżej, po prostu starałem się odnieść pytanie w sposób, w jaki zostało mi to przekazane. Zresztą nigdy nie używałbym tablicy (ani listy z linkami typu „roll-my-own”) w C ++ - używałbym obu wersji STL.
Onorio Catenacci
10

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

Rik
źródło
2
To wprawdzie dobry post, ale nie ma znaczenia na połączonej liście w porównaniu do dyskusji tablicy.
Robert Paulson
2
Sugerowałbym, że znaczna część artykułu Erica jest istotna, ponieważ omawia zarówno wady tablic, jak i zalety list, niezależnie od implementacji listy.
Bevan
8

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.

Firas Assaad
źródło
7

Oto szybki: Usuwanie przedmiotów jest szybsze.

itsmatt
źródło
7

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

James Curran
źródło
4
Możesz mieć kolejkę opartą na tablicy bez zbyt dużej ilości pracy, która wciąż była szybka / wydajna. Musisz tylko sprawdzić, który indeks był „głową”, a który „ogonem”. Działa to dość dobrze, jeśli potrzebujesz kolejki o stałym rozmiarze (na przykład bufor klawiatury w jądrze).
Herms
3
Nazywa się to „okrągłym buforem”, jeśli chcesz sprawdzić go w swoim ulubionym algorytmie.
Steve Jessop
7

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

Wasil
źródło
6
Wektory (= w zasadzie tablice) również mogą to robić, a zamortyzowany koszt dla nich jest zwykle mniejszy niż w przypadku list ze względu na problemy z lokalizacją odniesienia.
Konrad Rudolph
7

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

Joel Coehoorn
źródło
2
Er..umm .. Std :: vector jest tablicą, a nie listą połączoną. Standardowa lista łączy to, cóż, std :: list.
James Curran
1
tak, ale myślę, że wektor jest bliższy temu, o co prosi operacja - dynamicznej zamianie tablicy.
Joel Coehoorn
@Joel, właśnie próbowałem odnieść się do pytania, jakie zadał mi ten facet, który próbuje nauczyć się C ++. Nie zawracałbym sobie głowy kodowaniem mojej własnej listy, ale tak mnie zapytał. :-)
Onorio Catenacci
W środowiskach o ograniczonej pamięci (mikrokontrolery), dla których istnieją niestandardowe kompilatory, nie wszystkie języki (np. Kontenery w C ++) są zaimplementowane. Może być tak, że musisz zakodować własną listę, do której prowadzi link. nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus
Minh Tran
6

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.

Steve Baker
źródło
6

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.

tloach
źródło
6

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.
AKS
źródło
-1: Wszystkie te muszą być uzasadnione, a nie tylko wyliczone.
John Saunders,
Każdy punkt został już wyjaśniony w powyższych odpowiedziach. Jako spóźniony nie miałem innej opcji niż wyliczenie. BTW, który chciałbyś wyjaśnić?
AKS
Jeśli zostały już wyjaśnione, to dlaczego odpowiadasz?
John Saunders,
2
Dzięki temu uzyskasz podsumowany pogląd na dyskusję. I lubię tego rodzaju odpowiedzi, aby nie musiałem od nowa czytać tego samego wyjaśnienia. I zrobiłem to dla tych ludzi, którzy mają taki sam styl myślenia jak mój. Różne ppl mają różne style. Nic nowego.
AKS,
3

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.

debayan
źródło
3

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.

DenNukem
źródło
Czy mógłbyś to wyjaśnić: „możliwe jest stworzenie struktury danych, która zapewnia tablicowy interfejs dostępu porządkowego, w którym zarówno odczyt, jak i zapis są w najgorszym przypadku logarytmiczne”.
Hengameh,
1
W Wikipedii jest kilka rzeczy w dziale Dynamic Array / Vriants. Nie do końca o tym jednak myślałem ... Wyobraź sobie strukturę przypominającą drzewo b + ze stronami, ale bez kluczy, zamiast tego każda strona pośrednia pamięta, ile elementów jest na każdej podstronie, podczas gdy strony liści zawierają tylko elementy w małej tablicy. Wstawiając element na stronę liścia, należy przesunąć ~ połowę strony, aby zrobić miejsce, a następnie przejść w górę i zaktualizować liczbę elementów na wszystkich stronach przodków. Szukając elementu #N, po prostu zlicz liczbę podrzędnych elementów strony, aż przekroczysz N, a następnie zejdź do tego poddrzewa
DenNukem
3

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.

pranjal
źródło
3

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! :)

Farah Nazifa
źródło
3

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

iec2011007
źródło
3

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.

Ayman Amjad
źródło
2

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

użytkownik15453
źródło
2
Wskaźniki zajmują dużo miejsca? Nie całkiem. Jeśli przechowujesz połączoną listę wartości logicznych, to oczywiście, w procentach, wskaźniki zajmują dużo miejsca. Ale jeśli przechowujesz złożone obiekty (co zazwyczaj ma miejsce), wskaźniki prawdopodobnie byłyby nieistotne.
Herms
zapomniałem uśmiechu :) Ale powiedziałem „nie mogę” nie jest.
user15453
1

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

iram Arshad
źródło
1

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

SetSlapShot
źródło
1

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

Juan-Carlos
źródło
1

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ę :)

Vikalp Veer
źródło