Różnica między listą tablic a listą połączoną

Jak są przechowywane dane?

Lista tablic i lista połączonych są powszechnymi terminami, jeśli chodzi o przechowywanie i wyszukiwanie danych. Chociaż istnieje wiele urządzeń pamięci masowej, ostatecznie zależą one od mechanizmu pamięci masowej. Te dwa mechanizmy przechowywania umieszczają dane w urządzeniach pamięciowych i pobierają je w razie potrzeby. Przyjrzyjmy się, jak przechowują dane w swojej pamięci. Lista tablic używa pamięci sekwencyjnej, a dane są przechowywane jedna po drugiej. Jest to być może prostsza forma przechowywania - pozwala uniknąć nieporozumień. Tak, możemy pobrać następny element lub dane z następnej lokalizacji pamięci listy tablic; jest on jednak przechowywany za pomocą wskaźników na liście połączonych. Tutaj potrzebujemy dwóch lokalizacji pamięci do przechowywania - jednej dla danych, a drugiej dla wskaźnika. Wskaźnik wskazuje lokalizację pamięci następnych danych. Możemy łatwo zrozumieć, że lista połączona nigdy nie przechowuje danych sekwencyjnie; wykorzystuje raczej mechanizm losowego przechowywania. Wskaźniki są kluczowymi elementami w lokalizacji lokalizacji danych w pamięci.

Tablica dynamiczna i lista połączona

Omówiliśmy już, w jaki sposób oba mechanizmy pamięci masowej wprowadzają dane, i możemy podać termin „dynamiczna tablica” dla wewnętrznego schematu pamięci listy Array. Po prostu umieszcza fragmenty danych jeden po drugim - stąd nazwa - podczas gdy lista połączona używa wewnętrznej listy za pomocą wskaźników do śledzenia następnego elementu. Dlatego korzysta z wewnętrznej połączonej listy, takiej jak pojedynczo lub podwójnie połączona lista, aby wyświetlić nam kolejne dane.

Zużycie pamięci

Ponieważ lista Array przechowuje tylko rzeczywiste dane, potrzebujemy miejsca tylko na dane, które przechowujemy. I odwrotnie, na liście Powiązane również używamy wskaźników. Dlatego wymagane są dwie lokalizacje pamięci i możemy powiedzieć, że lista połączona zużywa więcej pamięci niż lista Array. Zaletą strony Listy połączonej jest to, że nigdy nie wymaga ciągłych lokalizacji pamięci do przechowywania naszych danych, w przeciwieństwie do listy Array. Wskaźniki są w stanie utrzymać pozycję następnej lokalizacji danych, a nawet możemy użyć mniejszych gniazd pamięci, które nie są ciągłe. Jeśli chodzi o wykorzystanie pamięci, wskaźniki odgrywają główną rolę na liście Połączonych, podobnie jak ich skuteczność.

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

W przypadku listy Array nawet pusta lista wymaga rozmiaru 10, ale w przypadku listy połączonej nie potrzebujemy tak dużej przestrzeni. Możemy utworzyć pustą listę z linkami o rozmiarze 0. Później możemy w razie potrzeby zwiększyć rozmiar.

Odzyskiwanie danych

Wyszukiwanie danych jest łatwiejsze na liście Array, ponieważ przechowuje je sekwencyjnie. Wszystko, co robi, to identyfikacja pierwszej lokalizacji danych; stamtąd można przejść do następnej lokalizacji, aby odzyskać resztę. Oblicza się jak pierwsza pozycja danych + „n”, gdzie „n” to kolejność danych na liście Array. Połączona lista odwołuje początkowy wskaźnik do znalezienia pierwszej lokalizacji danych, a stamtąd odwołuje wskaźnik powiązany z każdą z danych w celu znalezienia następnej lokalizacji 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 oznaczenia końca danych, podczas gdy lista połączona używa do tego celu wskaźnika zerowego. Gdy tylko system rozpozna dane zerowe, lista tablic zatrzymuje następne pobieranie danych. W podobny sposób wskaźnik zerowy powstrzymuje system przed przejściem do następnego pobierania danych.

Odwrócenie trasy

Lista połączona pozwala nam przechodzić w odwrotnych kierunkach za pomocą descendingiterator (). Jednak nie mamy takiego obiektu na liście Array - problemem jest odwrotne przechodzenie.

Składnia

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

Tworzenie listy tablic:

List arraylistsample = new ArrayList ();

Dodawanie obiektów do listy tablic:

Arraylistsample.add („nazwa1”);

Arraylistsample.add („nazwa2”);

Tak będzie wyglądać wynikowa lista tablic - [name1, name2].

Tworzenie listy połączonej:

List linkedlistsample = new linkedList ();

Dodawanie obiektów do listy połączonej:

Linkedlistsample.add („nazwa3”);

Linkedlistsample.add („name4”);

Tak będzie wyglądać wynikowa lista połączona - [name3, name4].

 Który jest lepszy dla operacji Get lub Search?

Lista tablic zajmuje O (1) czas na uruchomienie wyszukiwania danych, podczas gdy lista połączona zajmuje u O (n) dla n^th wyszukiwanie danych. Dlatego lista tablic zawsze używa stałego czasu do wyszukiwania danych, ale na liście połączonej czas ten zależy od pozycji danych. Dlatego listy tablic są zawsze lepszym wyborem dla operacji pobierania lub wyszukiwania.

Który jest lepszy dla operacji wstawiania lub dodawania?

Zarówno lista macierzy, jak i lista połączona wymagają czasu O (1) na dodanie danych. Ale jeśli tablica jest pełna, lista Array zajmuje dużo czasu, aby zmienić jej rozmiar i skopiować elementy do nowszej. W takim przypadku lista Powiązane jest lepszym wyborem.

Który jest lepszy dla operacji usuwania?

Operacja usuwania zajmuje prawie tyle samo czasu na liście Array i liście Linked. Na liście Array ta operacja usuwa dane, a następnie przesuwa pozycję danych w celu utworzenia nowszej tablicy - zajmuje to O (n) czasu. Na liście połączonej ta operacja przechodzi do określonych danych i zmienia pozycje wskaźnika, tworząc nowszą listę. Tutaj również czas przejścia i usunięcia wynosi O (n).

Który jest szybszy?

Wiemy, że lista Array używa wewnętrznej tablicy do przechowywania rzeczywistych danych. Dlatego jeśli jakiekolwiek dane zostaną usunięte, wszystkie nadchodzące dane wymagają przesunięcia pamięci. Oczywiście wymaga to dużo czasu i spowalnia proces. Takie przesunięcie pamięci nie jest wymagane na liście Połączonych, ponieważ wystarczy zmienić położenie wskaźnika. Dlatego lista połączona jest szybsza niż lista tablic w jakimkolwiek magazynie danych. Jest to jednak całkowicie zależne od rodzaju operacji, tj. W przypadku operacji Get lub Search lista połączona zajmuje znacznie więcej czasu niż lista Array. Gdy spojrzymy na ogólną wydajność, możemy powiedzieć, że lista Połączonych jest szybsza.

Kiedy używać listy tablic i listy połączonej?

Lista tablic najlepiej nadaje się do mniejszych wymagań dotyczących danych, gdy dostępna jest ciągła pamięć. Ale gdy mamy do czynienia z ogromnymi ilościami danych, dostępność ciągłej pamięci implementuje mechanizmy przechowywania danych, niezależnie od tego, czy są one małe, czy ogromne. Następnie zdecyduj, który wybrać - listę macierzy lub listę połączoną. Możesz skorzystać z listy tablic, gdy potrzebujesz tylko przechowywania i pobierania danych. Ale lista może pomóc ci poza tym, manipulując danymi. Gdy zdecydujesz, jak często wymagana jest manipulacja danymi, ważne jest, aby sprawdzić, jaki typ pobierania danych zazwyczaj wykonujesz. Gdy jest to tylko Pobierz lub Szukaj, lepszym wyborem jest Lista Array; w przypadku innych operacji, takich jak wstawianie lub usuwanie, przejdź do listy połączonych.

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

S.Nie	Pojęcia	Różnice
		Lista tablic	Połączona lista
1	Moda na przechowywanie danych	Korzysta z sekwencyjnego przechowywania danych	Wykorzystuje niesekwencyjne przechowywanie danych
2)	Schemat pamięci wewnętrznej	Utrzymuje wewnętrzny szyk dynamiczny	Utrzymuje połączoną listę
3)	Zużycie pamięci	Wymaga miejsca w pamięci tylko na dane	Wymaga miejsca w pamięci na dane, a także na wskaźniki
4	Rozmiar początkowej listy	Potrzebuje miejsca na co najmniej 10 przedmiotów	Nie potrzebuje miejsca, a nawet możemy stworzyć pustą listę połączeń o rozmiarze 0.
5	Odzyskiwanie danych	Oblicza jak pierwsza pozycja danych + „n”, gdzie „n” to kolejność danych na liście Array	Przejście od pierwszego lub ostatniego do wymaganego wymaganego danych
6	Koniec danych	Wartości Null oznaczają koniec	Wskaźnik zerowy oznacza koniec
7	Odwrócenie trasy	Nie pozwala na to	Pozwala na to przy pomocy descendingiterator ()
8	Składnia tworzenia listy	List arraylistsample = new ArrayList ();	List linkedlistsample = new linkedList ();
9	Dodawanie obiektów	Arraylistsample.add („nazwa1”);	Linkedlistsample.add („nazwa3”);
10	Pobierz lub wyszukaj	Zajmuje czas O (1) i jest lepszy w działaniu	Zajmuje czas O (n), a wydajność zależy od pozycji danych
11	Wstaw lub dodaj	Zużywa czas O (1), z wyjątkiem sytuacji, gdy tablica jest pełna	Zużywa czas O (1) w każdych okolicznościach
12	Usunięcie lub usunięcie	Zajmuje czas O (n)	Zajmuje czas O (n)
13	Kiedy użyć?	Gdy w grę wchodzi wiele operacji pobierania lub wyszukiwania; dostępność pamięci powinna być wyższa nawet na początku	Gdy jest wiele operacji wstawiania lub usuwania, a dostępność pamięci nie musi być ciągła