Połączona lista to liniowa struktura danych, w której elementy nie są przechowywane w ciągłym miejscu, lecz są połączone za pomocą wskaźników. Lista połączona tworzy serię połączonych węzłów, w których każdy węzeł przechowuje dane i adres następnego węzła.
Struktura węzła: Węzeł na połączonej liście zazwyczaj składa się z dwóch komponentów:
Dane: Przechowuje rzeczywistą wartość lub dane powiązane z węzłem.
Następny wskaźnik: Przechowuje adres pamięci (odniesienie) następnego węzła w sekwencji.
Głowa i ogon: Dostęp do połączonej listy uzyskuje się poprzez węzeł główny, który wskazuje pierwszy węzeł na liście. Ostatni węzeł na liście wskazuje na NULL lub nullptr, wskazując koniec listy. Węzeł ten nazywany jest węzłem ogonowym.
Dlaczego potrzebna jest struktura danych listy połączonej?
Oto kilka zalet listy połączonej wymienionej poniżej. Pomoże Ci to zrozumieć, dlaczego warto ją znać.
- Dynamiczna struktura danych: Rozmiar pamięci można alokować lub zwalniać w czasie wykonywania w oparciu o operację wstawiania lub usuwania.
- Łatwość wstawiania/usuwania: Wstawianie i usuwanie elementów jest prostsze niż tablice, ponieważ po wstawieniu i usunięciu nie trzeba przesuwać żadnych elementów, wystarczy zaktualizować adres.
- Efektywne wykorzystanie pamięci: Jak wiemy lista połączona to dynamiczna struktura danych, której rozmiar zwiększa się lub zmniejsza w zależności od wymagań, co pozwala uniknąć marnowania pamięci.
- Realizacja: Za pomocą połączonej listy można wdrożyć różne zaawansowane struktury danych, takie jak stos, kolejka, wykres, mapy skrótów itp.
Przykład:
W systemie, jeśli utrzymujemy posortowaną listę identyfikatorów w tablicy id[] = [1000, 1010, 1050, 2000, 2040].
Jeżeli chcemy wstawić nowy ID 1005 to aby zachować porządek posortowania musimy przesunąć wszystkie elementy po 1000 (z wyłączeniem 1000).
Usunięcie jest również kosztowne w przypadku tablic, chyba że zostaną zastosowane specjalne techniki. Na przykład, aby usunąć 1010 w id[], wszystko po 1010 musi zostać przeniesione, ponieważ wykonuje się dużo pracy, co wpływa na wydajność kodu.
Rodzaje list połączonych :
Istnieją głównie trzy typy list połączonych:
- Lista z pojedynczym linkiem
- Podwójnie połączona lista
- Okrągła lista połączona
1. Lista z pojedynczym linkiem :
Na liście z pojedynczym łączem każdy węzeł zawiera odniesienie do następnego węzła w sekwencji. Przechodzenie przez pojedynczo połączoną listę odbywa się w kierunku do przodu.
Lista z pojedynczym linkiem
2. Lista podwójnie połączona :
Na podwójnie połączonej liście każdy węzeł zawiera odniesienia zarówno do następnego, jak i poprzedniego węzła. Umożliwia to przechodzenie zarówno do przodu, jak i do tyłu, ale wymaga dodatkowej pamięci dla odniesienia wstecznego.
Lista podwójnie połączona
3. Okrągła lista połączona :
Na liście połączonej cyklicznie ostatni węzeł wskazuje z powrotem na węzeł główny, tworząc strukturę kołową. Może być łączony pojedynczo lub podwójnie.
0,06 jako ułamek
Okrągła lista połączona
Operacje na listach połączonych
- Wprowadzenie : Dodanie nowego węzła do połączonej listy polega na dostosowaniu wskaźników istniejących węzłów, aby zachować odpowiednią kolejność. Wstawienie można wykonać na początku, na końcu lub w dowolnej pozycji na liście
- Usunięcie : Usunięcie węzła z połączonej listy wymaga dostosowania wskaźników sąsiednich węzłów, aby wypełnić lukę pozostawioną przez usunięty węzeł. Usunięcie można wykonać na początku, na końcu lub w dowolnej pozycji na liście.
- Badawczy : Wyszukiwanie określonej wartości na liście połączonej polega na przechodzeniu przez listę od węzła głównego aż do znalezienia wartości lub osiągnięcia końca listy.
Analiza złożoności listy połączonej :
- Złożoność czasowa: O(n)
- Przestrzeń pomocnicza: O(n)
Zalety list połączonych
- Rozmiar dynamiczny: Połączone listy mogą dynamicznie rosnąć lub zmniejszać się, ponieważ alokacja pamięci odbywa się w czasie wykonywania.
- Wstawianie i usuwanie: Dodawanie lub usuwanie elementów z połączonej listy jest wydajne, szczególnie w przypadku dużych list.
- Elastyczność: Połączone listy można łatwo reorganizować i modyfikować bez konieczności stosowania ciągłego bloku pamięci.
Wady list połączonych
- Losowy dostęp: W przeciwieństwie do tablic, listy połączone nie umożliwiają bezpośredniego dostępu do elementów według indeksu. Aby dotrzeć do określonego węzła, wymagane jest przejście.
- Dodatkowa pamięć: Listy połączone wymagają dodatkowej pamięci do przechowywania wskaźników w porównaniu do tablic.
Wniosek:
Listy połączone to wszechstronne struktury danych, które zapewniają dynamiczną alokację pamięci oraz wydajne operacje wstawiania i usuwania. Zrozumienie podstaw list połączonych jest niezbędne dla każdego programisty i entuzjasty informatyki. Dzięki tej wiedzy możesz wdrożyć listy połączone, aby rozwiązać różne problemy i poszerzyć wiedzę na temat struktur danych i algorytmów.