Czym jest lista powiązana (LinkedList)?

Lista powiązana to liniowa struktura danych, w której elementy nie są przechowywane w sąsiadujących komórkach pamięci. Zamiast tego każdy element, zwany węzłem, zawiera dane i odwołanie (lub wskaźnik) do następnego węzła w sekwencji.

Istnieją różne typy list powiązanych:

• Lista jednokierunkowa: Każdy węzeł zawiera odwołanie tylko do następnego węzła.
• Lista dwukierunkowa: Każdy węzeł zawiera odwołania zarówno do następnego, jak i do poprzedniego węzła.
• Lista cykliczna: Ostatni węzeł odwołuje się do pierwszego, tworząc cykl.

Podstawowe operacje na liście powiązanej:

• Wstawianie: Dodanie nowego węzła do listy.
• Usuwanie: Usunięcie węzła z listy.
• Wyszukiwanie: Szukanie węzła po wartości.
• Przeglądanie: Sekwencyjny dostęp do wszystkich węzłów listy.

Zalety:

• Elastyczność w wstawianiu i usuwaniu elementów w dowolnej pozycji.
• Efektywne zarządzanie pamięcią, ponieważ elementy nie wymagają ciągłych bloków.

Wady:

• Wolny dostęp losowy do elementów (wymaga przeszukiwania sekwencyjnego).
• Wymaga dodatkowej pamięci do przechowywania odwołań.

Przykład struktury węzła w liście jednokierunkowej:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}