Сьпіс

Сьпіс (у праграмаваньні) — структура зьвестак, якая зьмяшчае лінейна ўпарадкаванае мноства элемэнтаў. Кожны элемэнт мае спасылку на зьвесткі і адну ці дзьве спасылкі на наступны і папярэдні элемэнты. У сьпіс можна дадаваць/выдаляць элемэнты ў любым месцы за пастаянны час, але немагчымы адвольны доступ, толькі пасьлядоўны.

Варыянты

Просты адназьвязаны сьпіс

Адназьвязаны сьпіс — найпрасьцейшы варыянт. У мове Lisp, дзе сьпісы — асноўная структура зьвестак, такі сьпіс уяўляе сабой пару: галава (спасылка на зьвесткі: head) і хвост (працяг сьпісу: tail, або іншымі словамі, спасылка на наступны элемэнт: next), які можа быць пустым (роўны null). Гэта выглядае ў кропачнай натацыі:

( галава . хвост )

Адназьвязны сьпіс з трыма элемэнтамі A, null, 21 можа быць запісаны: (A . (null . (21 . null))) ці ў скарочаным выглядзе: (A null 21). Графічна гэта паказана на наступным малюнку (перакрэсьлены квадрат азначае пустую спасылку — null):

Каб указаць адназьвязны сьпіс, напрыклад, перадаць у якасьці парамэтру ў працэдуру, дастаткова пазначыць адрас яго першага элемэнту. Усе іншыя элемэнты можна атрымаць паступова, калі рухацца па спасылках, пачынаючы ад першага.

Двузьвязаны сьпіс

Двузьвязаны сьпіс — больш складаны варыянт адназьвязанага сьпісу. Кожны элемэнт мае дзьве спасылкі — ня толькі на наступны элемэнт (next), але і на папярэдні (prev). Той жа самы сьпіс (A null 21):

У такім сьпісе магчымы рух у абодвух напрамках: ад першага да апошняга элемэнту і наадварот.

Цыклічны сьпіс

У цыклічным сьпісе апошні элемэнт мае спасылку не на null, а на першы, ствараючы цыкль, колца. Цыклічным можа быць і двузьвязаны сьпіс, у такім разе дадаткова і prev-спасылка першага элемэнту ўказвае на апошні элемэнт. Каб указаць адназьвязны цыклічны сьпіс пазначаюць адрас апошняга элемэнта, таму што празь яго можна лёгка атрымаць першы, пры гэтым застаецца магчымасьць хутка дадаваць новыя элемэнты пасьля апошняга ці перад першым.

Элемэнты-вартавыя

Часам сьпісы маюць спэцыяльныя дапаможныя элемэнты-вартавыя перад першым і/ці пасьля апошняга. Яны не зьмяшчаюць зьвесткі, але прызначаны для спрашчэньня ці паскарэньня апрацоўкі сьпісу. Наяўнасьць такіх элемэнтаў гарантуе, што кожны элемэнт мае наступніка/папярэдніка, і што ў кожным сьпісе, нават пустым, ёсьць першы і апошні элемэнт.

Параўнаньні

Сьпіс адрозьніваецца ад масіваў тым, што дазваляе дадаваць і выдаляць элемэнты (масівы, акрамя дынамічных — звычайна статычныя, колькасьць элемэнтаў у іх нязьменна), устаўляць новыя элемэнты паміж ужо існуючых бяз руханьня іншых элемэнтаў, але доступ да элемэнтаў сьпісу — толькі пасьлядоўны, а не па індэксе, як у масіве.