Szyk I Połączona lista to dwa sposoby organizacji danych w pamięci. Zanim zrozumiesz różnice między Szyk i Połączona lista , najpierw patrzymy przy tablicy I połączona lista .
metoda podciągu w Javie
Co to jest tablica?
Struktura danych zawierająca elementy tego samego typu. Struktura danych to sposób organizowania danych; tablica jest strukturą danych, ponieważ porządkuje dane sekwencyjnie. Tablica to duży fragment pamięci, w którym pamięć jest podzielona na małe bloki, a każdy blok może przechowywać pewną wartość.
Załóżmy, że utworzyliśmy tablicę składającą się z 10 wartości, wówczas w każdym bloku będzie przechowywana wartość typu całkowitego. Jeśli spróbujemy zapisać wartość w tablicy różnych typów, nie będzie to poprawna tablica i zgłosi błąd w czasie kompilacji.
Deklaracja tablicy
Tablicę można zadeklarować jako:
data_type name of the array[no of elements]
Aby zadeklarować tablicę, musimy najpierw określić typ tablicy, a następnie nazwę tablicy. Wewnątrz nawiasów kwadratowych musimy określić liczbę elementów, które powinna zawierać nasza tablica.
Rozumiemy na przykładzie.
int a[5];
W powyższym przypadku zadeklarowaliśmy tablicę 5 elementów za pomocą „ A Imię i nazwisko liczba całkowita typ danych.
Co to jest lista połączona?
Lista połączona to zbiór węzłów, które są przechowywane losowo. Każdy węzeł składa się z dwóch pól, tj. dane I połączyć . Tutaj dane to wartość przechowywana w tym konkretnym węźle, a łącze to wskaźnik przechowujący adres następnego węzła.
Różnice między listą tablicową a listą połączoną
Nie możemy powiedzieć, która struktura danych jest lepsza, tj. tablica czy połączona lista . Może zaistnieć możliwość, że jedna struktura danych będzie lepsza w przypadku jednego rodzaju wymagań, podczas gdy druga struktura danych będzie lepsza w przypadku innego rodzaju wymagań. Istnieją różne czynniki, takie jak częste operacje wykonywane na strukturze danych lub rozmiar danych, a także inne czynniki, na podstawie których wybierana jest struktura danych. Teraz zobaczymy pewne różnice między tablicą a połączoną listą w oparciu o pewne parametry.
1. Koszt dostępu do elementu
W przypadku tablicy, niezależnie od rozmiaru tablicy, dostęp do elementu tablicy zajmuje stały czas. W tablicy elementy są przechowywane w sposób ciągły, więc jeśli znamy adres bazowy elementu, możemy łatwo uzyskać adres dowolnego elementu w tablicy. Aby uzyskać adres dowolnego elementu tablicy, musimy wykonać proste obliczenia. Zatem dostęp do elementu w tablicy to: O(1) pod względem złożoności czasowej.
Na połączonej liście elementy nie są przechowywane w sposób ciągły. Składa się z wielu bloków, a każdy blok jest reprezentowany jako węzeł. Każdy węzeł ma dwa pola, tj. jedno przeznaczone jest na pole danych, a drugie przechowuje adres następnego węzła. Aby znaleźć dowolny węzeł na połączonej liście, musimy najpierw określić pierwszy węzeł, zwany węzłem głównym. Jeśli mamy znaleźć drugi węzeł na liście, to musimy przejść od pierwszego węzła, a w najgorszym przypadku, aby znaleźć ostatni węzeł, będziemy przechodzić przez wszystkie węzły. Przeciętny przypadek dostępu do elementu to O(n).
minipasek narzędzi Excel
Dochodzimy do wniosku, że koszt dostępu do elementu tablicy jest niższy niż w przypadku listy połączonej. Dlatego jeśli mamy jakiekolwiek wymagania dotyczące dostępu do elementów, lepszym wyborem będzie tablica.
2. Koszt wstawienia elementu
Wstawianie może mieć trzy scenariusze:
W przypadku listy połączonej, aby wstawić element na początku listy połączonej, utworzymy nowy węzeł, a do nowego węzła zostanie dodany adres pierwszego węzła. W ten sposób nowy węzeł staje się pierwszym węzłem. Zatem złożoność czasowa nie jest proporcjonalna do rozmiaru listy. Złożoność czasowa byłaby stała, tj. O (1).
Jeśli tablica nie jest pełna, możemy bezpośrednio dodać nowy element poprzez indeks. W tym przypadku złożoność czasowa byłaby stała, tj. O(1). Jeśli tablica jest pełna, najpierw musimy skopiować tablicę do innej tablicy i dodać nowy element. W tym przypadku złożoność czasowa wyniosłaby O(n).
Aby wstawić element na końcu połączonej listy, musimy przejść przez całą listę. Jeśli połączona lista składa się z n elementów, wówczas złożoność czasowa będzie wynosić O(n).
Załóżmy, że chcemy wstawić element w itpozycja tablicy; musimy przesunąć elementy n/2 w prawo. Dlatego złożoność czasowa jest proporcjonalna do liczby elementów. W przypadku przeciętnym złożoność czasowa wyniosłaby O(n).
js ładuje
W przypadku listy połączonej musimy przejść do tej pozycji, w której musimy wstawić nowy element. Co prawda nie musimy dokonywać żadnego przesunięcia, ale musimy przejść do pozycji n/2. Czas potrzebny jest proporcjonalny do liczby n elementów, a złożoność czasowa dla przeciętnego przypadku wyniesie O (n).
Wynikowa lista połączona to:
Implementacja tablicy jest łatwa w porównaniu z listą połączoną. Podczas tworzenia programu przy użyciu listy połączonej program jest bardziej podatny na błędy, takie jak błąd segmentacji lub wyciek pamięci. Dlatego podczas tworzenia programu na liście połączonej należy zachować szczególną ostrożność.
Połączona lista ma dynamiczny rozmiar, podczas gdy tablica jest statyczna. W tym przypadku statyczny nie oznacza, że nie możemy decydować o rozmiarze w czasie wykonywania, ale nie możemy go zmienić po podjęciu decyzji o rozmiarze.
3. Wymagania dotyczące pamięci
Ponieważ elementy tablicy są przechowywane w jednym ciągłym bloku pamięci, tablica ma stały rozmiar. Załóżmy, że mamy tablicę o rozmiarze 7, a tablica składa się z 4 elementów, a reszta miejsca jest niewykorzystana. Pamięć zajmowana przez 7 elementów:
Miejsce w pamięci = 7*4 = 28 bajtów
Gdzie 7 to liczba elementów w tablicy, a 4 to liczba bajtów typu całkowitego.
W przypadku listy połączonej nie ma niewykorzystanej pamięci, ale dodatkowa pamięć jest zajęta przez zmienne wskaźnikowe. Jeżeli dane są typu całkowitego, to całkowita pamięć zajmowana przez jeden węzeł wynosi 8 bajtów, czyli 4 bajty na dane i 4 bajty na zmienną wskaźnikową. Jeśli lista połączona składa się z 4 elementów, wówczas przestrzeń pamięci zajmowana przez listę powiązaną będzie wynosić:
sterownik internetowy
Miejsce w pamięci = 8*4 = 32 bajty
Połączona lista byłaby lepszym wyborem, jeśli część danych ma większy rozmiar. Załóżmy, że dane mają 16 bajtów. Miejsce w pamięci zajmowane przez tablicę będzie wynosić 16*7=112 bajtów, podczas gdy połączona lista zajmie 20*4=80. Tutaj określiliśmy 20 bajtów jako 16 bajtów dla rozmiaru danych plus 4 bajty dla zmiennej wskaźnikowej. Jeśli wybierzemy większy rozmiar danych, połączona lista zajmie mniej pamięci; w przeciwnym razie zależy to od czynników, które przyjmujemy przy określaniu rozmiaru.
Przyjrzyjmy się różnicom między tablicą a połączoną listą w formie tabelarycznej.
| Szyk | Połączona lista |
|---|---|
| Tablica to zbiór elementów o podobnym typie danych. | Lista połączona to zbiór obiektów nazywany węzłem, przy czym węzeł składa się z dwóch części, tj. danych i adresu. |
| Elementy tablicy są przechowywane w ciągłej lokalizacji pamięci. | Połączone elementy listy można przechowywać w dowolnym miejscu pamięci lub losowo. |
| Array współpracuje z pamięcią statyczną. W tym przypadku pamięć statyczna oznacza, że rozmiar pamięci jest stały i nie można go zmienić w czasie wykonywania. | Lista połączona współpracuje z pamięcią dynamiczną. W tym przypadku pamięć dynamiczna oznacza, że rozmiar pamięci można zmienić w czasie wykonywania, zgodnie z naszymi wymaganiami. |
| Elementy tablicy są od siebie niezależne. | Połączone elementy listy są od siebie zależne. Ponieważ każdy węzeł zawiera adres następnego węzła, więc aby uzyskać dostęp do następnego węzła, musimy uzyskać dostęp do jego poprzedniego węzła. |
| Tablica zajmuje więcej czasu podczas wykonywania dowolnej operacji, takiej jak wstawianie, usuwanie itp. | Połączona lista zajmuje mniej czasu podczas wykonywania dowolnej operacji, takiej jak wstawianie, usuwanie itp. |
| Dostęp do dowolnego elementu tablicy jest szybszy, ponieważ dostęp do elementu tablicy można uzyskać bezpośrednio poprzez indeks. | Dostęp do elementu na połączonej liście jest wolniejszy, ponieważ zaczyna się od pierwszego elementu połączonej listy. |
| W przypadku tablicy pamięć jest przydzielana w czasie kompilacji. | W przypadku listy połączonej pamięć jest przydzielana w czasie wykonywania. |
| Wykorzystanie pamięci w tablicy jest nieefektywne. Przykładowo, jeśli rozmiar tablicy wynosi 6, a tablica składa się tylko z 3 elementów, to reszta miejsca będzie niewykorzystana. | Wykorzystanie pamięci jest efektywne w przypadku listy połączonej, ponieważ pamięć może być alokowana lub zwalniana w czasie wykonywania, zgodnie z naszymi wymaganiami. |