Kas yra susietas sąrašas (LinkedList)?

Susijęs sąrašas yra linijinė duomenų struktūra, kurioje elementai nėra saugomi šalia esančiose atminties ląstelėse. Vietoj to, kiekvienas elementas, vadinamas mazgu, turi duomenis ir nuorodą (arba rodyklę) į sekantį mazgą sekoje.

Yra įvairių tipų susiję sąrašai:

• Vienpusis susijęs sąrašas: Kiekvienas mazgas turi tik nuorodą į sekantį mazgą.
• Dvipusis susijęs sąrašas: Kiekvienas mazgas turi nuorodas tiek į sekantį, tiek į ankstesnį mazgą.
• Apskritas susijęs sąrašas: Paskutinis mazgas nuoroda į pirmąjį, sudarant ciklą.

Pagrindinės operacijos:

• Įterpimas: Naujo mazgo pridėjimas į sąrašą.
• Šalinimas: Mazgo pašalinimas iš sąrašo.
• Paieška: Mazgo paieška pagal reikšmę.
• Perėjimas: Seklinis prieigos prie visų sąrašo mazgų.

Privalumai:

• Lankstumas įterpiant ir šalinant elementus bet kurioje pozicijoje.
• Efektyvus atminties valdymas, nes elementai nereikalauja nuoseklių blokų.

Trūkumai:

• Lėtas atsitiktinis prieigos prie elementų (reikalingas sekos perėjimas).
• Reikalinga papildoma atmintis nuorodų saugojimui.

Pavyzdys struktūros mazgo paprastame susijusiame sąraše:

class Node {
    int data;
    Node next;

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