Array versus linked-list

Innym dobrym powodem jest to, że listy połączone dobrze nadają się do wydajnych implementacji wielowątkowych. Powodem tego jest to, że zmiany wydają się być lokalne - 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 blokady przy użyciu operacji typu CAS i całkowite uniknięcie ciężkich zamków.

Z linkowaną listą Iteratory może również przemierzać listę podczas wprowadzania modyfikacji. W optymistycznym przypadku, w którym modyfikacje nie kolidują, Iteratory mogą kontynuować bez zastrzeżeń.

W przypadku tablicy, jakakolwiek zmiana modyfikująca rozmiar tablicy może wymagać zablokowania dużej części tablicy i w rzeczywistości rzadko jest to wykonywane bez blokady globalnej całej tablicy, więc modyfikacje stają się zatrzymaniem spraw światowych.

Wikipedia ma bardzo dobry dział o różnicach.

Listy połączone mają kilka zalet nad tablicami. Elementy można wstawiać do list połączonych w nieskończoność, podczas gdy tablica ostatecznie wypełni w górę lub trzeba zmienić rozmiar, drogie operacja, która może nawet nie być możliwe, jeśli pamięć jest fragmentaryczna. Podobnie tablica, z której wiele elementy są usuwane mogą stać się marnotrawstwo lub konieczność dokonania mniejszy.

On the other ręcznie, tablice pozwalają na losowe dostęp, natomiast listy połączone pozwalają tylko sekwencyjny dostęp do elementów. Listy pojedynczo połączone, w rzeczywistości mogą tylko być przemierzane w jednym kierunku. To sprawia, że połączone listy nie nadają się do aplikacje, w których warto szukać szybki wzrost elementu o jego indeks, takich jak heapsort. Sekwencyjny dostęp na tablic jest również szybszy niż na linked listy na wielu maszynach ze względu na lokalizację pamięci podręcznej referencji i danych. Linked listy nie otrzymują prawie żadnych korzyści z na cache.

Kolejna wada list linkowanych czy potrzebne jest dodatkowe miejsce do referencje, co często czyni je niepraktyczne dla list małych danych elementy takie jak znaki lub logiczne wartości. Może być również powolny, a z naiwny, marnotrawny, do przydzielanie pamięci osobno dla każdego nowy element, problem ogólnie rozwiązane przy użyciu 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 różne listy współdzielące tę samą sekcję końcową

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

Czyli:

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

Bez konieczności kopiowania danych wskazywanych przez a do b i c.

Dlatego są tak popularne w językach funkcyjnych, które używają zmiennych niezmiennych-operacje prepend i tail mogą odbywać się swobodnie bez konieczności kopiowania oryginalnych danych - bardzo ważne funkcje, gdy traktujesz dane jako niezmienne.

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

EDIT: dla wyjaśnienia, miałem na myśli" scalanie " w sensie nieuporządkowanym, a nie jak w sortowaniu scalającym. Być może" konkatenacja " byłoby lepszym słowem.

Poza tym, że wstawianie do środka listy jest łatwiejsze - znacznie łatwiej jest również usunąć ze środka połączonej listy niż tablicę.

Ale szczerze mówiąc, nigdy nie używałem połączonej listy. Gdy potrzebowałem szybkiego wstawiania i usuwania, potrzebowałem również szybkiego wyszukiwania, więc poszedłem do HashSet lub słownika.

Po pierwsze, w C++ linked-lists nie powinno być dużo więcej problemów niż tablica. Możesz użyć std::list lub boost pointer list dla połączonych list. Kluczowe problemy z listami połączonymi vs tablicami to dodatkowe miejsce wymagane na wskaźniki i straszny losowy dostęp. Powinieneś użyć połączonej listy, Jeśli

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

Powszechnie niedocenianym argumentem dla ArrayList i przeciwko LinkedList jest to, że LinkedList są niewygodne podczas debugowania. Czas spędzony przez programistów konserwacji na zrozumienie programu, np. na znalezienie błędów, wzrasta i IMHO czasami nie uzasadnia nanosekund w poprawie wydajności lub bajtów w zużyciu pamięci w aplikacjach korporacyjnych. Czasami (no, oczywiście zależy to od rodzaju aplikacji), lepiej zmarnować kilka bajtów, ale mieć aplikacja, która jest bardziej łatwa w utrzymaniu lub łatwiejsza do zrozumienia.

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

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>

Dla mnie jest tak,

1. Access

   • listy połączone umożliwiają tylko sekwencyjny dostęp do elementów. Tak więc 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 na odniesienia. To czyni je niepraktycznymi dla list małych pozycji danych, takich jak znaki lub wartości logiczne.
   • Tablice nie potrzebują dodatkowego miejsca do wskazywania następnej pozycji danych. Dostęp do każdego elementu można uzyskać za pomocą indeksów.

3. Rozmiar

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

4. Wstawianie/Usuwanie

   • elementy mogą być wstawiane i usuwane w linkowanych listach w nieskończoność.
   • wstawianie / usuwanie wartości w tablicach jest bardzo kosztowne. Wymaga realokacji pamięci.

Dwie rzeczy:

Kodowanie listy linkowanej jest, bez wątpienia, nieco więcej pracy niż używanie tablicy i zastanawiał się, co uzasadniłoby dodatkowy wysiłek.

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

Jeśli chodzi o rzeczywiste różnice między tablicą a listą połączoną, dla mnie najważniejsze jest to, jak planuj wykorzystanie struktury. Użyję terminu vector, ponieważ jest to termin dla tablicy z możliwością zmiany rozmiaru w C++.

Indeksowanie na połączoną listę jest powolne, ponieważ musisz przemierzyć listę, aby dostać się do podanego indeksu, podczas gdy wektor jest przylegający do pamięci i można się tam dostać za pomocą matematyki wskaźników.

Dodawanie na końcu lub początku połączonej listy jest łatwe, ponieważ musisz zaktualizować tylko jeden link, gdzie w wektorze możesz zmienić rozmiar i skopiować zawartość odbiór.

Usunięcie elementu z listy jest łatwe, ponieważ wystarczy zerwać parę linków, a następnie połączyć je z powrotem. Usuwanie elementu z wektora może być szybsze lub wolniejsze, w zależności od kolejności. Zamiana ostatniego elementu na górny element, który chcesz usunąć, jest szybsza, podczas gdy przesuwanie wszystkiego po nim jest wolniejsze, ale zachowuje kolejność.

Eric Lippert ostatnio napisał post na jednym z powodów, dla których tablice powinny być używane zachowawczo.

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

Oto szybki: usuwanie przedmiotów jest szybsze.

Linked-list są szczególnie przydatne, gdy kolekcja stale rośnie i kurczy się. Na przykład, trudno sobie wyobrazić próbę zaimplementowania kolejki (Dodaj do końca, usuń z przodu) za pomocą tablicy-spędzałbyś cały swój czas przesuwając rzeczy w dół. Z drugiej strony, to trywialne z linked-list.

Poza dodawaniem i usuwaniem ze środka listy, Lubię listy połączone bardziej, ponieważ mogą rosnąć i kurczyć się dynamicznie.

Nikt już nie koduje własnej listy linkowanych. To byłoby głupie. Założenie, że korzystanie z połączonej listy wymaga więcej kodu, jest po prostu błędne.

W dzisiejszych czasach budowanie listy linkowanej jest tylko ćwiczeniem dla uczniów, aby mogli zrozumieć tę koncepcję. Zamiast tego każdy używa wstępnie zbudowanej listy. W C++, opierając się na opisie w naszym pytaniu, prawdopodobnie oznaczałoby to wektor stl (#include <vector>).

Dlatego wybór listy połączonej vs tablicy jest całkowicie o ważeniu różne cechy każdej struktury w stosunku do potrzeb aplikacji. Przezwyciężenie dodatkowego obciążenia programowego powinno mieć zerowy wpływ na decyzję.

To naprawdę kwestia wydajności, narzut na wstawianie, usuwanie lub przenoszenie (gdzie nie jest to zwykła Zamiana) elementów wewnątrz połączonej listy jest minimalny, tzn. sama operacja to O(1), wersety O(n) dla tablicy. Może to mieć istotne znaczenie, jeśli intensywnie operujesz na liście danych. Wybrałeś swoje typy danych na podstawie tego, jak będziesz na nich działać i wybierz najbardziej efektywny dla używanego algorytmu.

Tablice mają sens, gdzie będzie znana dokładna liczba elementów i gdzie wyszukiwanie według indeksu ma sens. Na przykład, gdybym chciał 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 znacznie wolniejsza, aby uzyskać wartość danego piksela. W miejscach, w których tablica nie ma sensu, istnieją ogólnie lepsze typy danych niż Lista do obsługi z danymi skutecznie.

Arrays Vs Linked List:

1. alokacja pamięci tablicy czasami się nie powiedzie z powodu fragmentarycznej pamięci.
2. buforowanie jest lepsze w tablicach, ponieważ wszystkie elementy są przydzielane do sąsiedniej przestrzeni 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. Linked List lepiej z wielowątkowego punktu widzenia.

Ponieważ tablice mają charakter statyczny, dlatego wszystkie operacje podobnie jak alokacja pamięci występuje w momencie kompilacji tylko. Procesor musi więc wkładać mniej wysiłku w swoje działanie.

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

Najpierw powinniśmy zauważyć, że jeśli chcesz zachować odwołania do obiektów poza samym zestawem, prawdopodobnie skończy się to przechowywaniem wskaźników w tablicy, zamiast przechowywania samych obiektów. W przeciwnym razie nie będzie można wstawiać do tablicy - jeśli obiekty zostaną w niej osadzone, zostaną one przeniesione podczas wstawiania i wszelkie wskaźniki do nich staną się nieważne. To samo dotyczy indeksów tablic.

Twoim pierwszym problemem, jak sam zauważyłeś, jest wstawianie-lista linkowana pozwala na wstawianie W O(1), ale tablica zazwyczaj wymaga O (n). Problem ten można częściowo przezwyciężyć - możliwe jest stworzenie struktury danych, która daje interfejs dostępu typu array by-ordinal, gdzie zarówno czytanie, jak i pisanie są w najgorszym wypadku logarytmiczne.

Twoim drugim i poważniejszym problemem jest to, że dany element znajdujący następny element to O (n). Jeśli zestaw nie został zmodyfikowany, możesz zachować indeks elementu jako odniesienie zamiast wskaźnika, co czyni find-next operacją O( 1), ale jako że masz tylko wskaźnik do samego obiektu i nie możesz określić jego bieżącego indeksu w tablicy inaczej niż przez skanowanie całej "tablicy". Jest to problem nie do pokonania w przypadku tablic - nawet jeśli można zoptymalizować wstawianie, nie ma nic, co można zrobić, aby zoptymalizować operację Znajdź-następny typ.

W tablicy masz prawo dostępu do dowolnego elementu w czasie O(1). Więc nadaje się do operacji takich jak szybkie wyszukiwanie binarne sortowanie itp. Z drugiej strony Linked list nadaje się do wstawiania usuwania jako jego w czasie O(1). Zarówno ma zalety, jak i wady i preferowanie jednego nad drugim sprowadza się do tego, co chcesz wdrożyć.

-- większe pytanie brzmi Czy możemy mieć hybrydę obu. Coś w stylu tego, co python i perl implementują jako listy.

Linked List

Jest bardziej korzystne, jeśli chodzi o wstawianie! Zasadniczo to, co robi, to to, że zajmuje się wskaźnikiem

1 -> 3 -> 4

Insert (2)

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

Wreszcie

1 -> 2 -> 3 -> 4

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

Proste!

Ale z tablicy

| 1 | 3 | 4 |

Insert (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Cóż każdy może wyobrazić sobie różnicę! Tylko dla 4 indeksu wykonujemy 3 kroki

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

To samo dotyczy usunięcia! W Linked List możemy po prostu użyć wskaźnika i nullify elementu i dalej w klasie object! Ale dla array, musimy wykonać shiftLeft ()

Mam nadzieję, że to pomoże! :)

Linked List są bardziej narzut do utrzymania niż tablica, wymaga również dodatkowej pamięci wszystkie te punkty są uzgodnione. Ale jest kilka rzeczy, które array nie może zrobić. W wielu przypadkach Załóżmy, że chcesz tablicę o długości 10^9 nie możesz jej uzyskać, ponieważ uzyskanie jednej lokalizacji pamięci ciągłej musi tam być. Linked list może być tutaj Zbawicielem.

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

STL kontenery zwykle mają implementację list połączonych za sceną.

Różnica między ArrayList i LinkedList

ArrayList i LinkedList oba implementują interfejs List i utrzymują porządek wstawiania. Obie są klasami nie zsynchronizowanymi. Istnieje jednak wiele różnic między klasami ArrayList i LinkedList, które są podane poniżej.

ArrayList -

1. ArrayList wewnętrznie używa tablicy dynamicznej do przechowywania elementów.

2. Manipulacja z ArrayList jest powolna, ponieważ wewnętrznie wykorzystuje / align = "left" / Jeśli jakikolwiek element zostanie usunięty z tablicy, wszystkie bity zostaną przesunięte w pamięć.

3. ArrayList klasa może działać jako lista tylko dlatego, że implementuje tylko List.
4. ArrayList jest lepszy do przechowywania i dostęp do danych.

LinkedList -

1. LinkedList wewnętrznie używa podwójnie połączonej listy do przechowywania elementów.

2. Manipulacja z {[1] } jest szybsza niż ArrayList, ponieważ używa podwójnie połączonej listy, więc nie ma bitu przesunięcie jest wymagane w pamięci.

3. LinkedList klasa może działać jako lista i Kolejka, ponieważ implementuje interfejsy List i Deque.

4. LinkedList jest lepszy do manipulowania danymi.

Jedynym powodem użycia listy linkowanej jest to, że wstawianie elementu jest łatwe (również usuwanie).

Disadvatige może być tak, że wskaźniki zajmują dużo miejsca.

A o tym kodowaniu jest trudniej: Zazwyczaj nie potrzebujesz listy z linkami kodowymi (lub tylko raz), które są zawarte w STL i to nie jest takie skomplikowane, jeśli nadal musisz to zrobić.

Uważam też, że lista linków jest lepsza od tablic. ponieważ robimy przemierzanie w liście linków, ale nie w tablicach

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

język programowania C: podczas korzystania z listy połączonej (zazwyczaj za pomocą wskaźników struct) należy zwrócić szczególną uwagę na to,aby nie wyciekała pamięć. Jak wspomniano wcześniej, listy połączone są łatwe do przetasowania, ponieważ wszystko, co robi, zmienia wskaźniki, ale czy będziemy pamiętać, aby uwolnić wszystko?

Java: Java ma automatyczne zbieranie śmieci, więc wyciekanie pamięci nie będzie problemem, ale ukryte przed programistą wysokiego poziomu są szczegóły implementacji tego, czym jest powiązana lista. Metody takie jak usunięcie węzła ze środka listy są bardziej skomplikowane niż niektórzy użytkownicy języka by się tego spodziewali.

Dlaczego lista linkowana nad tablicą ? Jak już niektórzy powiedzieli, większa szybkość wstawiania i usuwania.

Ale może nie musimy żyć z ograniczeniami jednego z nich, i uzyskać to, co najlepsze z obu, w tym samym czasie... eh ?

Do usunięcia tablicy można użyć bajtu' Deleted', aby przedstawić fakt, że wiersz został usunięty, więc zmiana kolejności tablicy nie jest już konieczna. Aby zmniejszyć obciążenie wstawiania lub szybko zmieniających się danych, użyj w tym celu połączonej listy. Wtedy odnosząc się do nich, niech twoja logika najpierw przeszukuje jeden, a potem drugi. Tak więc używanie ich w połączeniu daje to, co najlepsze z obu.

Jeśli masz naprawdę dużą tablicę, możesz połączyć ją z inną, znacznie mniejszą tablicą lub linkowaną listą, gdzie mniejsza zawiera 20, 50, 100 ostatnio używanych elementów. Jeśli potrzebna tablica nie znajduje się na krótszej liście lub tablicy, przejdź do dużej tablicy. Jeśli tam znajdziesz, możesz dodać go do mniejszej listy/tablicy linkowanych na domniemanie że "rzeczy ostatnio używane są najbardziej lubiane do ponownego użycia" (i tak, prawdopodobnie uderzając w najmniej ostatnio używany element z listy ). Co jest prawdą w wielu przypadkach i rozwiązał problem musiałem rozwiązać w .Moduł sprawdzania uprawnień zabezpieczeń ASP, z łatwością, elegancją i imponującą szybkością.

Podczas gdy wielu z was dotknęło głównego adv. / dis linked list vs array, większość porównań jest jak jeden jest lepszy / gorszy niż other.Eg. możesz zrobić dostęp losowy w tablicy, ale nie jest to możliwe w linked list i innych. Jest to jednak przy założeniu, że listy linków i tablica zostaną zastosowane w podobnej aplikacji. Jednak poprawną odpowiedzią powinno być to, w jaki sposób lista linków byłaby preferowana zamiast tablicy i odwrotnie w konkretnym wdrożeniu aplikacji. Załóżmy, że chcesz wdrożyć aplikacja słownikowa, czego byś użył ? Array: MMM to pozwoli na łatwe pobieranie poprzez wyszukiwanie binarne i inne wyszukiwanie algo .. ale zastanówmy się, jak lista linków może być lepsza..Powiedz, że chcesz wyszukać "Blob" w słowniku. Czy byłoby sensowne mieć listę linków A - > B - > C - > D - - - - > Z, a następnie każdy element listy również wskazujący na tablicę lub inną listę wszystkich słów zaczynających się na tę literę ..

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