Tiesinis sąrašas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Tiesinis sąrašas (linked list), dar vadinamas sąrašu, yra viena esminių duomenų struktūrų, naudojamų programavime. Tiesinį sąrašą sudaro elementai, kurie seka vienas paskui kitą. Nuoseklumas pasiekiamas saugant nuorodas ar rodykles į sekantį ir/ar prieš tai einantį elementą. Pirmas tiesinio sąrašo elementas dažnai vadinamas galva, paskutinis – uodega. Sąrašas gali neturėti nei galvos, nei uodegos.

Yra keletas tiesinių sąrašų rūšių:

Vienpusis sąrašas 
Kiekvienas elementas „žino“ tiktai apie sekantį elementą. Atitinkamai uodega neturi sekančio.
Dvipusis sąrašas 
Modifikuotas vienpusis. Pridedama sąsaja su prieš tai einančiu elementu; Galva neturi prieš tai einančio.
Ciklinis sąrašas 
Gali būti vienpusis arba dvipusis – svarbiausia, kad toks sąrašas neturi nei galvos, nei uodegos.
Sąrašas su sergėtoju (sentinel list
Tai ciklinis sąrašas, kuriame egzistuoja elementas be duomenų, žymintis sąrašo baigtį.

Sąrašas gali būti realizuojamas masyvu, dvejais masyvais ir pasitelkiant programavimo kalboje numatytus susiejimo būdus (dažniausiai rodyklėmis, nuorodomis). Pastarasis būdas yra populiariausias dėl to, kad realizuojant masyvais sąraše sudėtingai ir neefektyviai realizuojamos įdėjimo tarp dviejų elementų ir elemento pašalinimo operacijos.

Sąrašuose neefektyvu saugoti mažus (atminties prasme) duomenis, dėl to kad pati sąrašo realizacija reikalauja papildomos atminties. Taip pat sąrašo apėjimas yra sunkiai kešuojamas. Sąrašai dažnai pasirenkami, kai svarbus išmetimo bei įterpimo operacijų greitis, bet ne paieškos.

Eilės ir Steko duomenų struktūros gali būti realizuojamos tiesiniu sąrašu.


 Crystal 128 mymac.png  Šiame straipsnyje naudojami diskutuotini terminai.
Daugiau apie kompiuterinius terminus skaitykite žodynėlyje.