INF.04Algorytmika i Struktury Danych
Lista powiązana (Linked List)
Dynamiczna struktura danych złożona z węzłów (Node), gdzie każdy węzeł zawiera przechowywaną wartość oraz wskaźnik na kolejny element.
Rodzaje list powiązanych:
- Jednokierunkowa: Każdy węzeł przechowuje wartość i wskaźnik
nextdo następnego węzła. Ostatni wskazuje nanullptr/null. - Dwukierunkowa: Każdy węzeł posiada dwa wskaźniki:
next(następny) orazprev(poprzedni), co umożliwia nawigację w obu kierunkach.
Porównanie z tablicą statyczną:
- Wstawianie/usuwanie na początku: Lista O(1) vs Tablica O(n) (konieczność przesuwania elementów).
- Dostęp swobodny po indeksie: Tablica O(1) vs Lista O(n) (wymaga sekwencyjnego przejścia po wskaźnikach).
- Alokacja pamięci: Tablica wymaga ciągłego bloku pamięci, węzły listy mogą być rozproszone w stercie.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Lista powiązana (Linked List) lub rozpocznij trening.