Tiesinis sąrašas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
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.
 |
Šiame straipsnyje naudojami diskutuotini terminai. Daugiau apie kompiuterinius terminus skaitykite žodynėlyje. |
