Co to jest połączona struktura danych?
Połączona struktura danych jest zbiorem danych ułożonych w formie listy. Każdy element danych na liście jest nazywany węzłem. Każdy węzeł jest połączony z następnym elementem na liście przez odniesienie do adresu pamięci tego kolejnego węzła. Połączone struktury danych są używane zamiast tablicy, gdy liczba węzłów na liście jest nieznana lub może wzrosnąć lub zmniejszyć się w trakcie wykonanie programu Najczęstszym typem struktury danych połączonych jest lista połączona.
Węzeł połączonej struktury danych zawiera na ogół dwie informacje - odniesienie do rzeczywistych przechowywanych danych i odniesienie do następnego węzła na liście. Połączoną listę można przeglądać lub przeszukiwać krokowo przez każdy z węzłów danych, zaczynając od pierwszego lub na początku listy. Nie ma sposobu na znalezienie informacji na połączonej liście bez sekwencyjnego przechodzenia między węzłami od początku do końca.
Większość połączonych struktur danych zużywa jak najmniej pamięci podczas wykonywania programu. Jeśli lista połączona zostanie utworzona tylko z jednym węzłem i nie zostaną dodane żadne inne węzły, lista ta zajmie pamięć wymagana tylko dla jednego węzła. Jest to wyraźny kontrast ze strukturą danych tablicy, w której rozmiar całej tablicy musi być zadeklarowany i przydzielony na początku programu i nie można go zmienić .
Listy połączone płacą za efektywne wykorzystanie zasobów pamięci, wymagając większej mocy obliczeniowej. Znalezienie określonego elementu danych na liście połączonej wymaga każdorazowego przeglądania całej listy, aby dostęp do informacji był wolniejszy środek listy Usuwanie lub zmiana kolejności danych na połączonej liście może być również bardziej wymagające obliczeniowo niż zarządzanie tablicą, w której elementy można łatwo zamieniać.
Połączona struktura danych nie musi mieć tylko jednego odwołania do następnego węzła; może mieć kilka. Niektóre listy połączone mają dwa odwołania do węzłów, jeden do następnego węzła na liście i jeden do poprzedniego węzła. Są to tak zwane listy podwójnie połączone. listy w dowolnym kierunku znacznie szybciej, jednak kosztem zwiększonego zużycia pamięci dla struktury danych.
Możliwe jest, że listy połączone mają trzy lub więcej odniesień do innych węzłów na liście. To tworzy strukturę podobną do drzewa z całymi gałęziami węzłów odradzającymi się z jednego. Te typy danych struktury nazywane są listami wielokrotnie połączonymi. Listy z wieloma linkami są szczególnie przydatne w przypadku złożonych algorytmów sortowania, które są wykorzystywane do strukturyzacji danych. Drzewa wyszukiwania są możliwe w dużej mierze ze względu na użycie połączonych struktur danych aby utworzyć wiele gałęzi o zmiennej długości.