Tiesinis sąrašas

Tiesinis sąrašas (linked list), dar vadinamas sąrašu – 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.
 Žiedinis 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.

Duomenų struktūros