Połączona struktura danych to zbiór danych ułożonych w formacie podobnym do listy. Każdy element odniesienia na liście jest określany jako węzeł. Każdy węzeł jest połączony z następnym 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 Najpopularniejszym typem powiązanej struktury danych jest połączona lista.
Węzeł połączonej struktury danych zawiera na ogół dwie informacje — odniesienie do aktualnie przechowywanych danych i odniesienie do następnego węzła na liście. Połączona lista jest przeszukiwana krok po kroku. przez każdy z węzłów danych, zaczynając od pierwszego lub nagłówka listy.Nie ma sposobu, aby znaleźć informacje na połączonej liście bez sekwencyjnego przechodzenia przez węzły od początku do końca.
Większość połączonych struktur danych będzie używać jak najmniej pamięci podczas wykonywania programu. Jeśli połączona lista zostanie utworzona z tylko 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 do struktury danych tablicy, w której rozmiar całej tablicy musi być zadeklarowany i przydzielony na początku programu i nie można go zmienić .
Połączone listy płacą za efektywne wykorzystanie zasobów pamięci, ponieważ wymagają większej mocy obliczeniowej.Znalezienie określonej części danych na połączonej liście wymaga za każdym razem przeglądania całej listy, więc dostęp do informacji może być wolniejszy. środek listy.Usuwanie lub zmiana kolejności danych na połączonej liście również może być bardziej intensywne obliczeniowo niż zarządzanie tablicą, w której elementy można łatwo wymieniać.
Połączona struktura danych nie musi mieć tylko jednego odniesienia do następnego węzła; może mieć kilka. Niektóre połączone listy mają dwa odniesienia do węzłów, jedno do następnego węzła na liście, a drugie do poprzedniego węzła. Są one znane jako listy podwójnie połączone. Może to sprawić, że poruszanie się po listy w obu kierunkach znacznie szybciej, ale kosztem zwiększonego wykorzystania pamięci dla struktury danych.
Możliwe jest, że połączone listy mogą mieć trzy lub więcej odniesień do innych węzłów na liście. Tworzy to strukturę podobną do drzewa z całymi gałęziami węzłów odradzających się z jednego. Struktury nazywane są listami wielokrotnie połączonymi.Powielanie połączonymi listami jest szczególnie przydatny w przypadku złożonych algorytmów sortowania używanych do strukturyzowania danych.Drzewa wyszukiwania są możliwe głównie dzięki wykorzystaniu połączonych struktur danych do tworzenia wielu gałęzi o zmiennej długości.