Saistīts saraksts

Vikipēdijas raksts

Saistīts saraksts (angliski linked list, krieviski связанный список) - lineāra datu struktūra, kurā katrs elements (mezgls) glabā datus un rādītaju. Rādītājs (adrese) norāda uz nākamo elementu. Pēdējā mezglā rādītājs ir tukšs - nenorāda ne uz vienu elementu. Saistīto sarakstu bieži vien sauc vienkārši par sarakstu.

Vienkāršs saistīts saraksts ar 3 elementiem
Vienkāršs saistīts saraksts ar 3 elementiem

Var būt divkārši saistīts vai divvirziena saraksts, kuram katrā mezglā ir divi rādītaji, kur viens norada uz iepriekšējo mezglu, bet otrs - uz nākamo.

Var būt cikliskie vai gredzenveida saraksti, kuros pēdējā mezgla rādītājs norāda uz saraksta pirmo mezglu.

[izmainīt šo sadaļu] Sarakstu salīdzinājums ar masīviem

[izmainīt šo sadaļu] Priekšrocības

  • viegli pievienot un dzēst elementus, tikai pārliekot rādītājus uz vajadzīgo mezglu
  • datora atmiņas izdalīšana (un atbrīvošana) notiek tikai tad, kad notiek jaunu elementu pievienošana vai dzēšana

[izmainīt šo sadaļu] Trūkumi

  • grūti noteikt elementa kārtas numuru (indeksu) - lai to izdarītu, ir jāiziet visam sarakstam cauri līdz vajadzīgajam mezglam
  • rādītajam tiek tērēta papildus atmiņa

Sk. arī 'Datu masīvs'.