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.
arrays
data-structures
linked-list
language-agnostic
Onorio Catenacci
źródło
źródło
Odpowiedzi:
źródło
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.
źródło
ConcurrentSkipListMap
alboConcurrentSkipListMap
nie są listy, nawet jeśli „Lista” występuje gdzieś w ich imieniu. Oba wymagają kluczy, które zostaną posortowane i unikalne. Jeśli potrzebujeszList
, 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óraLinkedList
jest jednocześnie aktualizowalna. Jeśli potrzebujesz tylko równoczesnej kolejki lub deque, cóż, istnieją nawet przykłady, ale jednocześnieList
… Nie jestem przekonany, że jest to nawet możliwe.Wikipedia ma bardzo dobrą sekcję na temat różnic.
http://en.wikipedia.org/wiki/Linked_list
źródło
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ą
to znaczy:
bez konieczności kopiowania danych wskazywanych przez
a
dob
ic
.Dlatego są one tak popularne w językach funkcjonalnych, które wykorzystują niezmienne zmienne -
prepend
atail
operacje mogą odbywać się swobodnie bez konieczności kopiowania oryginalnych danych - bardzo ważne cechy, gdy traktujesz dane jako niezmienne.źródło
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.
źródło
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.
źródło
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ę:
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:
źródło
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
źródło
Dla mnie jest tak
Dostęp
Przechowywanie
Rozmiar
Wstawianie / usuwanie
źródło
Dwie rzeczy:
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.
źródło
Eric Lippert niedawno napisał post na temat jednego z powodów, dla których tablice należy stosować zachowawczo.
źródło
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.
źródło
Oto szybki: Usuwanie przedmiotów jest szybsze.
źródło
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ą.
źródło
Oprócz dodawania i usuwania ze środka listy, bardziej lubię połączone listy, ponieważ mogą się dynamicznie powiększać i zmniejszać.
źródło
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ę.
źródło
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.
źródło
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.
źródło
Lista połączonych tablic Vs:
źródło
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.
źródło
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.
źródło
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.
źródło
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! :)
źródło
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ą.
źródło
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.
źródło
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ódło
również uważam, że lista linków jest lepsza niż tablice. ponieważ przeglądamy listę linków, ale nie tablice
źródło
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ć.
źródło
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ą.
źródło
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 ---->
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ę :)
źródło