Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Зв'язаний список у програмуванні — одна з найважливіших структур даних, у якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять до складу елементів списку та вказують на наступний за цим елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (у двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають низку переваг порівняно з масивами. Зокрема, у них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елемента, що в разі зі зв'язаними списками неможливо та потребує послідовного перебору всіх елементів, які передують цьому.
Різновиди зв'язаних списків
Однобічно зв'язані списки
Однобічно зв'язаний список з трьох елементів
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що цей елемент — останній у списку.
Двобічно зв'язаний список
Двобічно зв'язаний список
У двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка).
Кільцевий список
Кільцевий однобічно зв'язаний список
У кільцевому списку перший та останній елемент зв'язані. Тобто поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.
Застосування списків
Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їхній основі можуть будуватися складніші структури даних на кшталт дерева. На базі списків також можуть бути реалізовані стеки та черги.
Переваги та недоліки
Загалом, якщо необхідно оперувати з динамічними множинами, де присутні інтенсивні операції з додавання або видалення елементів, існують досить переконливі аргументи для використання саме зв'язаних списків.
Зв'язані списки та масиви
Списки мають деякі переваги над масивами. Вони досить ефективні щодо операцій додавання або видалення елементу на початку, або в кінці списка, виконуючи їх за постійний час O(1), тоді як масиви для цього потребують часу O(n) (окрім видалення останнього елемента), тобто час зростає з ростом кількості елементів масиву. Водночас додавання/видалення довільного елемента залежить від розміру списку і складність такого алгоритму O(n).
У списках також не існує проблеми «розширення», яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність помістити в нього додаткові елементи. Так само фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з огляду використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ до будь-якого елемента. Однобічно зв'язані списки, натомість, потребують проходження всіх попередніх елементів. Це призводить до складнощів застосування списків у задачах, де необхідно швидко знаходити елемент за його індексом, наприклад в алгоритмах сортування. Кешування списків у таких випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.
Двобічне та однобічне зв'язування
Двобічне зв'язування потребує більше пам'яті на елемент та більших обчислювальних затрат на виконання елементарних операцій. Але такими списками легше маніпулювати, тому що вони дозволяють проходження по списку в обох напрямах, що є необхідною умовою функціонування деяких алгоритмів.
Джерела
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 10.2 Зв'язані списки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zv yazanij spisok u programuvanni odna z najvazhlivishih struktur danih u yakij elementi linijno vporyadkovani ale poryadok viznachayetsya ne nomerami elementiv a vkazivnikami yaki vhodyat do skladu elementiv spisku ta vkazuyut na nastupnij za cim element v odnozv yazanih abo odnobichno zv yazanih spiskah abo na nastupnij ta poperednij elementi u dvozv yazanih abo dvobichno zv yazanih spiskah Spisok maye golovu pershij element ta hvist ostannij element Zv yazani spiski mayut nizku perevag porivnyano z masivami Zokrema u nih nabagato efektivnishe za chas O 1 tobto nezalezhno vid kilkosti elementiv vikonuyutsya proceduri dodavannya ta viluchennya elementiv Natomist masivi nabagato krashi v operaciyah yaki potrebuyut bezposerednogo dostupu do kozhnogo elementa sho v razi zi zv yazanimi spiskami nemozhlivo ta potrebuye poslidovnogo pereboru vsih elementiv yaki pereduyut comu Riznovidi zv yazanih spiskivOdnobichno zv yazani spiski Dokladnishe Odnobichno zv yazanij spisok Odnobichno zv yazanij spisok z troh elementiv V odnobichno zv yazanomu spisku yakij ye najprostishim riznovidom zv yazanih spiskiv kozhnij element skladayetsya z dvoh poliv data abo danih ta vkazivnika next na nastupnij element Yaksho vkazivnik ne vkazuye na inshij element inakshe next NULL to vvazhayetsya sho cej element ostannij u spisku Dvobichno zv yazanij spisok Dokladnishe Dvobichno zv yazanij spisok Dvobichno zv yazanij spisok U dvobichno zv yazanomu spisku element skladayetsya z troh poliv vkazivnika na poperednij element prev polya danih data ta vkazivnika next na nastupnij element Yaksho prev NULL to v elementa nemaye poperednika tobto vin ye golovoyu spisku yaksho next NULL to v nogo nemaye nastupnika hvist spiska Kilcevij spisok Kilcevij odnobichno zv yazanij spisok U kilcevomu spisku pershij ta ostannij element zv yazani Tobto pole prev golovi spiska vkazuye na hvist spiska a pole next hvosta spiska vkazuye na golovu spiska Zastosuvannya spiskivSpiski intensivno zastosovuyutsya v programuvanni yak samostijni strukturi Takozh na yihnij osnovi mozhut buduvatisya skladnishi strukturi danih na kshtalt dereva Na bazi spiskiv takozh mozhut buti realizovani steki ta chergi Perevagi ta nedolikiZagalom yaksho neobhidno operuvati z dinamichnimi mnozhinami de prisutni intensivni operaciyi z dodavannya abo vidalennya elementiv isnuyut dosit perekonlivi argumenti dlya vikoristannya same zv yazanih spiskiv Zv yazani spiski ta masivi Spiski mayut deyaki perevagi nad masivami Voni dosit efektivni shodo operacij dodavannya abo vidalennya elementu na pochatku abo v kinci spiska vikonuyuchi yih za postijnij chas O 1 todi yak masivi dlya cogo potrebuyut chasu O n okrim vidalennya ostannogo elementa tobto chas zrostaye z rostom kilkosti elementiv masivu Vodnochas dodavannya vidalennya dovilnogo elementa zalezhit vid rozmiru spisku i skladnist takogo algoritmu O n U spiskah takozh ne isnuye problemi rozshirennya yaka rano chi pizno vinikaye v masivah fiksovanogo rozmiru koli vinikaye neobhidnist pomistiti v nogo dodatkovi elementi Tak samo fiksovanij masiv z yakogo bulo vidaleno bagato elementiv abo voni prosto ne vikoristovuyutsya ye duzhe neefektivnim z oglyadu vikoristannya pam yati Funkcionuvannya spiskiv mozhlivo v situaciyi koli pam yat komp yutera fragmentovana todi yak masivi perevazhno potrebuyut neperervnoyi oblasti dlya zberigannya Z inshogo boku masivi dozvolyayut bezposerednij dostup do bud yakogo elementa Odnobichno zv yazani spiski natomist potrebuyut prohodzhennya vsih poperednih elementiv Ce prizvodit do skladnoshiv zastosuvannya spiskiv u zadachah de neobhidno shvidko znahoditi element za jogo indeksom napriklad v algoritmah sortuvannya Keshuvannya spiskiv u takih vipadkah majzhe ne daye efektu Inshim ochevidnim nedolikom spiskiv ye neobhidnist razom z korisnoyu informaciyeyu dodatkovogo zberezhennya informaciyi pro vkazivniki sho poznachayetsya na efektivnosti vikoristannya pam yati cimi strukturami Dvobichne ta odnobichne zv yazuvannya Dvobichne zv yazuvannya potrebuye bilshe pam yati na element ta bilshih obchislyuvalnih zatrat na vikonannya elementarnih operacij Ale takimi spiskami legshe manipulyuvati tomu sho voni dozvolyayut prohodzhennya po spisku v oboh napryamah sho ye neobhidnoyu umovoyu funkcionuvannya deyakih algoritmiv DzherelaTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 10 2 Zv yazani spiski Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4