Wideo: Różnica Między Tablicami A Listami Połączonymi
2024 Autor: Mildred Bawerman | [email protected]. Ostatnio zmodyfikowany: 2023-12-16 08:41
Tablice a listy połączone
Tablice są najczęściej używaną strukturą danych do przechowywania kolekcji elementów. Większość języków programowania udostępnia metody umożliwiające łatwe deklarowanie tablic i uzyskiwanie dostępu do elementów w tablicach. Lista połączona, a dokładniej lista połączona pojedynczo, jest również strukturą danych, której można użyć do przechowywania kolekcji elementów. Składa się z sekwencji węzłów, a każdy węzeł ma odniesienie do następnego węzła w sekwencji.
Na rysunku 1 pokazano fragment kodu zwykle używany do deklarowania i przypisywania wartości do tablicy. Rysunek 2 przedstawia, jak tablica wyglądałaby w pamięci.
Powyższy kod definiuje tablicę, która może przechowywać 5 liczb całkowitych, a dostęp do nich uzyskuje się za pomocą indeksów od 0 do 4. Jedną z ważnych właściwości tablicy jest to, że cała tablica jest przydzielana jako pojedynczy blok pamięci, a każdy element otrzymuje własną przestrzeń w tablicy. Po zdefiniowaniu tablicy jej rozmiar jest ustalany. Więc jeśli nie masz pewności co do rozmiaru tablicy w czasie kompilacji, musisz zdefiniować wystarczająco dużą tablicę, aby była bezpieczna. Ale przez większość czasu będziemy używać mniejszej liczby elementów, niż przydzieliliśmy. Tak więc znaczna ilość pamięci jest marnowana. Z drugiej strony, jeśli „wystarczająco duża tablica” nie jest w rzeczywistości wystarczająco duża, program ulegnie awarii.
Lista połączona przydziela pamięć do swoich elementów oddzielnie we własnym bloku pamięci, a ogólną strukturę uzyskuje się przez połączenie tych elementów jako ogniw w łańcuchu. Każdy element na połączonej liście ma dwa pola, jak pokazano na rysunku 3. Pole danych zawiera faktycznie przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Pierwszy element listy połączonej jest przechowywany jako nagłówek listy połączonej.
dane | Kolejny |
Rysunek 3: Element listy połączonej
Rysunek 4 przedstawia połączoną listę z trzema elementami. Każdy element przechowuje swoje dane, a wszystkie elementy oprócz ostatniego przechowują odniesienie do następnego elementu. Ostatni element zawiera wartość null w swoim następnym polu. Dostęp do dowolnego elementu na liście można uzyskać, zaczynając od początku i podążając za następnym wskaźnikiem, aż do osiągnięcia wymaganego elementu.
Mimo że tablice i połączone listy są podobne w tym sensie, że obie są używane do przechowywania kolekcji elementów, występują w nich różnice wynikające ze strategii, których używają do przydzielania pamięci do jej elementów. Tablice alokują pamięć do wszystkich swoich elementów jako pojedynczy blok, a rozmiar tablicy należy określić w czasie wykonywania. To spowodowałoby, że tablice byłyby nieefektywne w sytuacjach, w których nie znasz rozmiaru tablicy w czasie kompilacji. Ponieważ lista połączona przydziela pamięć do swoich elementów oddzielnie, byłaby bardzo wydajna w sytuacjach, w których nie znasz rozmiaru listy w czasie kompilacji. Deklaracja i dostęp do elementów na liście połączonej nie byłyby proste w porównaniu do bezpośredniego dostępu do elementów w tablicy przy użyciu jej indeksów.
Zalecane:
Różnica Między Różnicą Faz A Różnicą ścieżki
Różnica faz a różnica ścieżek Różnica faz i różnica ścieżek to dwa bardzo ważne pojęcia w optyce. Zjawiska te są widoczne w problemach
Różnica Między Tablicami A Tablicami
Tablice a tablice Tablice to najczęściej używana struktura danych do przechowywania kolekcji elementów. Większość języków programowania udostępnia metody easi
Różnica Między Genami Połączonymi I Niepowiązanymi
Kluczowa różnica - geny połączone i niepowiązane Geny to specyficzne sekwencje DNA w chromosomach. W ludzkim genomie jest 46 chromosomów. Pomiędzy nimi
Różnica Między Połączonymi I Skonsolidowanymi Sprawozdaniami Finansowymi
Kluczowa różnica - Połączone a skonsolidowane sprawozdania finansowe Gdy firmy realizują strategie ekspansji, mogą przejąć kontrolę lub niekontrolowanie
Różnica Między Kluczową Różnicą Między Minerałami Metalicznymi I Niemetalicznymi
Kluczowa różnica - minerały metaliczne i niemetaliczne Minerał to naturalnie występujący stały i nieorganiczny składnik o określonym wzorze chemicznym