Różnica między listą tablic a powiązaną listą

Jak przechowywane są dane?

Lista tablic i powiązana lista to wspólne warunki, jeśli chodzi o przechowywanie i wyszukiwanie danych. Chociaż ostatecznie istnieje wiele urządzeń do przechowywania, zależą one od mechanizmu przechowywania. Te dwa mechanizmy przechowywania umieszczają dane w urządzeniach pamięci i odzyskują je w razie potrzeby. Rzućmy okiem, w jaki sposób przechowują dane w pamięci. Lista tablic używa sekwencyjnego pamięci, a elementy danych są przechowywane jeden po drugiej. Jest to być może prostsza forma przechowywania - pozwala uniknąć zamieszania. Tak, możemy odzyskać następny element lub dane z następnej lokalizacji pamięci listy tablicy; Jest jednak przechowywany za pomocą wskaźników na połączonej liście. Tutaj potrzebujemy dwóch lokalizacji pamięci do przechowywania - jednej dla danych, drugiej dla wskaźnika. Wskaźnik dotyczy lokalizacji pamięci następnych danych. Możemy łatwo zrozumieć, że połączona lista nigdy nie przechowuje danych sekwencyjnie; Raczej używa losowego mechanizmu przechowywania. Wskaźniki są kluczowymi elementami w lokalizacji lokalizacji danych w pamięci.

Dynamiczna tablica i powiązana lista

Omówiliśmy już, w jaki sposób oba mechanizmy przechowywania wkładają dane i możemy podać termin „tablica dynamiczna” dla wewnętrznego schematu przechowywania listy tablicy. Po prostu umieszcza fragmenty danych po drugiej - stąd nazwa - podczas gdy połączona lista używa listy wewnętrznej za pomocą wskazówek do śledzenia następnego elementu. Dlatego używa wewnętrznej listy powiązanej, takiego jak pojedynczo lub podwójnie połączona lista, aby pokazać nam następne dane.

Zużycie pamięci

Ponieważ lista tablic przechowuje tylko rzeczywiste dane, potrzebujemy miejsca tylko dla przechowywanych danych. I odwrotnie, na linkowanej liście używamy również wskaźników. Dlatego wymagane są dwie lokalizacje pamięci i możemy powiedzieć, że powiązana lista zużywa więcej pamięci niż lista tablic. Korzystną stroną listy powiązanej jest to, że nigdy nie wymaga ona ciągłej lokalizacji pamięci do przechowywania naszych danych, w przeciwieństwie do listy tablic. Wskaźniki są w stanie utrzymać pozycję następnego miejsca, a nawet możemy użyć mniejszych szczelin pamięci, które nie są ciągłe. Jeśli chodzi o użycie pamięci, wskaźniki odgrywają główną rolę na linii, podobnie jak ich skuteczność.

Rozmiar początkowej listy tablic i listy połączonej

Z listą tablic, nawet pusta lista wymaga rozmiaru 10, ale z powiązaną listą nie potrzebujemy tak ogromnej przestrzeni. Możemy utworzyć pustą listę połączoną o rozmiarze 0. Później możemy w razie potrzeby zwiększyć rozmiar.

Odzyskiwanie danych

Odzyskiwanie danych jest prostsze na liście tablic, ponieważ przechowuje sekwencyjnie. Wszystko, co robi, to zidentyfikować pierwszą lokalizację danych; Stamtąd dostęp do następnej lokalizacji jest sekwencyjnie, aby odzyskać resztę. Oblicza się jak pierwsza pozycja danych + „n”, gdzie „n” jest kolejnością danych na liście tablic. Połączona lista odnosi się do początkowego wskaźnika, aby znaleźć pierwszą lokalizację danych, a stamtąd odnosi się do wskaźnika powiązanego z każdym danymi, aby znaleźć następną lokalizację danych. Proces pobierania zależy głównie od wskaźników tutaj i skutecznie pokazują nam następną lokalizację danych.

Koniec danych

Lista tablic używa wartości zerowej do zaznaczenia końca danych, podczas gdy lista połączona używa w tym celu wskaźnika zerowego. Gdy tylko system rozpoznaje dane zerowe, lista tablic zatrzymuje następne pobieranie danych. W podobny sposób wskaźnik zerowy powstrzymuje system przed przejściem do następnego wyszukiwania danych.

Odwrotne przejście

Połączona lista pozwala nam przejść w odwrotne kierunki za pomocą Descendingiterator (). Jednak nie mamy takiego obiektu na liście tablic - odwrotne przejście staje się tutaj problemem.

Składnia

Spójrzmy na składnię Java obu mechanizmów przechowywania.

Tworzenie listy tablic:

List ArrayListSample = new ArrayList ();

Dodawanie obiektów do listy tablic:

ArrayListsamp.Dodaj („name1”);

ArrayListsamp.Dodaj („name2”);

W ten sposób będzie wyglądać wynikająca lista tablic - [Name1, Name2].

Połączone tworzenie listy:

List LinkedListsample = new LinkedList ();

Dodawanie obiektów do linkowanej listy:

Próbka LinkedLists.Dodaj („name3”);

Próbka LinkedLists.Dodaj („name4”);

W ten sposób będzie wyglądać wynikająca lista połączona - [Name3, Name4].

 Co jest lepsze do operacji GET lub wyszukiwania?

Lista tablic zajmuje O (1) czas na uruchomienie dowolnego wyszukiwania danych, podczas gdy lista połączona wymaga n) dla n^th Wyszukiwanie danych. Dlatego lista tablic zawsze wykorzystuje stały czas dla dowolnego wyszukiwania danych, ale na połączonej liście czasu potrzebny zależy od pozycji danych. Dlatego listy tablic są zawsze lepszym wyborem do operacji GET lub wyszukiwania.

Co jest lepsze do operacji wstawiania lub dodawania?

Zarówno lista tablic, jak i lista połączona, zajmują czas dodawania danych. Ale jeśli tablica jest pełna, lista tablic zajmuje znaczną ilość czasu na rozmiar i skopiowanie elementów do nowszego. W takim przypadku lista połączona jest lepszym wyborem.

Co jest lepsze do operacji usuwania?

Operacja usunięcia zajmuje prawie tyle samo czasu na liście tablic, jak i na listy połączonej. Na liście tablicy ta operacja ta usuwa dane, a następnie przesuwa pozycję danych w celu utworzenia nowszej tablicy - to zajmuje czas o (n). Na połączonej liście ta operacja przechodzi do konkretnych danych i zmienia pozycje wskaźnika, aby utworzyć nowszą listę. Czas na przejście i usunięcie jest tutaj również tutaj.

Który jest szybszy?

Wiemy, że lista tablic używa tablicy wewnętrznej do przechowywania rzeczywistych danych. Dlatego jeśli jakiekolwiek dane zostaną usunięte, wszystkie nadchodzące dane wymagają zmiany pamięci. Oczywiście wymaga to znacznej ilości czasu i spowalnia rzeczy. Taka przesunięcie pamięci nie jest wymagane na listy powiązanej, ponieważ wszystko to, co robi, to zmiana lokalizacji wskaźnika. Dlatego lista połączona jest szybsza niż lista tablic w dowolnym rodzaju przechowywania danych. Jest to jednak wyłącznie zależne od rodzaju operacji, i.mi. W przypadku operacji GET lub wyszukiwania lista połączona zajmuje znacznie więcej czasu niż lista tablic. Kiedy patrzymy na ogólną wydajność, możemy powiedzieć, że lista połączona jest szybsza.

Kiedy korzystać z listy tablicy i listy połączonej?

Lista tablic najlepiej nadaje się do mniejszych wymagań danych, w których dostępna jest pamięć ciągła. Ale kiedy zajmujemy się ogromnymi ilościami danych, dostępność pamięci ciągłej implementuje mechanizmy przechowywania danych, niezależnie od tego, czy jest to małe, czy ogromne. Następnie zdecyduj, który wybrać - lista tablic lub lista połączona. Możesz kontynuować listę tablic, gdy potrzebujesz przechowywania i pobierania danych. Ale lista może ci pomóc poza tym poprzez manipulowanie danymi. Po zdecydowaniu, jak często wymagana jest manipulacja danymi, ważne jest, aby sprawdzić, jaki rodzaj wyszukiwania danych zwykle wykonujesz. Kiedy jest po prostu zdobycie lub wyszukiwanie, lista tablic jest lepszym wyborem; W przypadku innych operacji, takich jak wstawianie lub usuwanie, śmiało powiązaną listę.

Spójrzmy na różnice w formie tabelarycznej.