Байланыстырылған тізім - Linked list

«Динамикалық тізім» осында қайта бағытталады. Ешқашан аяқталмайтын мақалалар тізімін сипаттайтын Уикипедия нұсқаулығын қараңыз Уикипедия: WikiProject тізімдері.

Жылы Информатика, а байланыстырылған тізім бұл жадында физикалық орналасуымен реті берілмеген мәліметтер элементтерінің сызықтық жиынтығы. Оның орнына әр элемент ұпай келесіге. Бұл мәліметтер құрылымы коллекциясынан тұрады түйіндер бірге а жүйелі. Әрбір түйіннің ең негізгі түрінде мыналар бар: деректер және а анықтама (басқаша айтқанда, а сілтеме) кезектегі келесі түйінге. Бұл құрылым итерация кезінде кез-келген позициядан элементтерді тиімді енгізуге немесе жоюға мүмкіндік береді. Неғұрлым күрделі нұсқалар қосымша сілтемелерді қосады, бұл түйіндерді ерікті позицияларда неғұрлым тиімді енгізуге немесе жоюға мүмкіндік береді. Байланыстырылған тізімдердің жетіспеушілігі - қол жеткізу уақыты сызықтық (және қиын) құбыр ). Жылдам қол жетімділік, мысалы, кездейсоқ қол жеткізу мүмкін емес. Массивтер жақсысы бар кэш орны байланыстырылған тізімдермен салыстырғанда.

Singly-linked-list.svg
Түйіндері екі өрісті қамтитын байланысқан тізім: бүтін мән және келесі түйінге сілтеме. Соңғы түйін тізімнің соңын білдіру үшін қолданылатын терминаторға байланысты.

Байланыстырылған тізімдер ең қарапайым және кең таралған деректер құрылымдарының бірі болып табылады. Оларды бірнеше басқа кең тарату үшін қолдануға болады деректердің дерексіз түрлері, оның ішінде тізімдер, стектер, кезектер, ассоциативті массивтер, және S-өрнектер дегенмен, байланыстырылған тізімді негіз ретінде пайдаланбай, бұл деректер құрылымын тікелей енгізу сирек емес.

Байланыстырылған тізімнің әдеттегіден артықшылығы массив тізім элементтерін оңай бөлуге немесе алып тастауға болады, бұл бүкіл құрылымды қайта бөлусіз немесе қайта ұйымдастырусыз, себебі деректер элементтерін сақтау қажет емес іргелес массивті қайта құрылымдау кезінде жадта немесе дискіде жұмыс уақыты бұл әлдеқайда қымбат операция. Байланыстырылған тізімдер тізімнің кез-келген нүктесінде түйіндерді енгізуге және жоюға мүмкіндік береді және тізімнің өту кезінде жадта сілтеме қосылатын немесе жойылатын сілтемеге дейінгі сілтемені сақтай отырып, операциялардың тұрақты санымен жасауға мүмкіндік береді.

Екінші жағынан, қарапайым тізімдер өздігінен мүмкіндік бермейді кездейсоқ қол мәліметтерге немесе тиімді индекстеудің кез-келген түріне көптеген негізгі операциялар, мысалы: тізімнің соңғы түйінін алу, берілген деректерді қамтитын түйінді табу немесе жаңа түйінді енгізу керек орынды табу - көп жағдайда қайталануды қажет етуі мүмкін. немесе барлық тізім элементтері. Байланыстырылған тізімдерді пайдаланудың артықшылықтары мен кемшіліктері төменде келтірілген. Байланыстырылған тізім динамикалық, сондықтан тізімнің ұзақтығы қажет болған жағдайда ұлғаюы немесе азаюы мүмкін. Әр түйін міндетті түрде физикалық жадында алдыңғыға сәйкес келмейді.

Кемшіліктері

  • Олар қарағанда жадты көбірек пайдаланады массивтер өйткені олар пайдаланатын сақтау орны көрсеткіштер.
  • Байланыстырылған тізімдегі түйіндер басынан бастап ретімен оқылуы керек, өйткені байланыстырылған тізімдер табиғаты бойынша дәйекті қол жетімділік.
  • Түйіндер тізбектің жекелеген элементтеріне қол жеткізу үшін уақытты едәуір көбейтетін, әрине, а CPU кэші.
  • Қиындықтар тізбекте кері жүру кезінде пайда болады. Мысалы, бір-бірімен байланыстырылған тізімдер артқа жылжу үшін ауыр [1] және екі еселенген тізімдерді оқып-үйрену біршама жеңіл болғанымен, жады a үшін орын бөлу кезінде жұмсалады артқы көрсеткіш.

Тарих

Байланыстырылған тізімдер 1955–1956 жылдары жасалған Аллен Ньюелл, Клифф Шоу және Герберт А. Симон кезінде RAND корпорациясы бастапқы ретінде мәліметтер құрылымы олар үшін Ақпаратты өңдеу тілі. Авторлар IPL-ді бірнеше ерте дамыту үшін қолданды жасанды интеллект бағдарламалар, соның ішінде логикалық теория машинасы, Жалпы мәселелерді шешуші және компьютерлік шахмат бағдарламасы. Олардың жұмыстары туралы есептер 1956 ж. IRE Transaction Information Information теориясында және 1957-1959 жж. Бірнеше конференцияларда, соның ішінде 1957 және 1958 жж. Батыс бірлескен компьютерлік конференциясының материалдары және Ақпаратты өңдеу (алғашқы еңбектер жинағында) пайда болды. ЮНЕСКО Ақпаратты өңдеу жөніндегі халықаралық конференция) 1959 ж. Қазіргі тізбектелген тізбекті көрсететін көрсеткілері бар тізбелік түйіндерді бейнелейтін блоктардан тұратын қазіргі классикалық диаграмма Ньюэлл мен Шоудың Проктағы «Логикалық теория машинасын бағдарламалауда» пайда болады. WJCC, 1957 ж. Ақпан. Ньюэлл мен Саймон ACM-мен танылды Тюринг сыйлығы 1975 жылы «жасанды интеллектке, адамның таным психологиясына және тізімді өңдеуге негізгі үлес қосқаны» үшін.Проблемасы машиналық аударма үшін табиғи тіл өңдеу жүргізді Виктор Йнгве кезінде Массачусетс технологиялық институты (MIT) байланыстырылған тізімдерді өзінің COMIT бағдарламалау тілінде деректер құрылымы ретінде, компьютерлік зерттеулер саласында қолдана алады лингвистика. Бұл тіл туралы «Механикалық аудармаға арналған бағдарламалау тілі» атты есеп 1958 жылы Механикалық аудармада пайда болды.[дәйексөз қажет ]

LISP, тізім процессоры үшін жасалған Джон Маккарти 1958 жылы ол MIT-да болған кезде және 1960 жылы оның дизайнын қағазға жариялады ACM байланысы, «Символдық өрнектердің рекурсивті функциялары және оларды машинамен есептеу, I бөлім». LISP-тің негізгі құрылымдарының бірі - байланыстырылған тізім.

1960 жылдардың басында байланыстырылған тізімдердің де, осы құрылымдарды негізгі деректерді ұсыну ретінде қолданатын тілдердің де утилитасы жақсы жолға қойылды. Берт Грин MIT Линкольн зертханасы 1961 жылы наурызда IRE Transaction in Electronics-тегі адам факторларымен операцияларда «Символдармен айла-шарғы жасау үшін компьютерлік тілдер» атты шолушы мақаласын жариялады, ол байланысты тізім тәсілінің артықшылықтарын жинақтады. Кейінірек Боброу мен Рафаэльдің «Тізімді өңдейтін компьютерлік тілдерді салыстыру» мақаласы 1964 жылы сәуірде ACM Communications басылымында пайда болды.

Әзірлеген бірнеше операциялық жүйелер Техникалық жүйелер бойынша кеңесшілер (бастапқыда Вест-Лафайет Индиана, кейінірек Чапел Хилл, Солтүстік Каролина) файлдық құрылым ретінде жеке байланыстырылған тізімдерді қолданды. Каталогтың жазбасы файлдың бірінші секторына бағытталды, ал файлдың келесі бөліктері бағыттауыштар арқылы орналасты. Осы техниканы қолданатын жүйелерге Flex қосылды (үшін Motorola 6800 CPU), mini-Flex (сол CPU) және Flex9 (Motorola 6809 CPU үшін). Калифорниядағы Smoke Signal Broadcasting компаниясы шығарған және ұсынған TSC жасаған нұсқа, дәл осылай қосарланған тізімдер қолданылды.

System 360/370 машиналары үшін IBM жасаған TSS / 360 операциялық жүйесі өздерінің файлдық жүйелерінің каталогы үшін қосарланған тізімді қолданды. Каталог құрылымы Unix-ке ұқсас болды, мұнда каталогта файлдар мен басқа каталогтар болуы және кез келген тереңдікке дейін кеңеюі мүмкін.

Негізгі түсініктер және номенклатура

Байланыстырылған тізімнің әр жазбасы көбінесе 'элемент' немесе 'деп аталадытүйін '.

Әр түйіннің өрісі келесі түйіннің адресін қамтиды, әдетте «келесі сілтеме» немесе «келесі сілтеме» деп аталады. Қалған өрістер «деректер», «ақпарат», «құндылық», «жүк» немесе «пайдалы жүктеме» өрістері ретінде белгілі.

Тізімнің «басы» оның алғашқы түйіні болып табылады. Тізімнің 'құйрығы' бастан кейінгі тізімнің қалған бөлігіне немесе тізімдегі соңғы түйінге қатысты болуы мүмкін. Жылы Лисп және кейбір туынды тілдерде келесі түйін 'деп аталуы мүмкінcdr '(айтылды мүмкін) тізімнің, ал түйіннің пайдалы жүктемесі «автомобиль» деп аталуы мүмкін.

Жалғыз байланысқан тізім

Жалғыз байланыстырылған тізімдерде деректер өрісі бар түйіндер, сондай-ақ түйіндер жолындағы келесі түйінді көрсететін «келесі» өрісі бар. Бір-бірімен байланыстырылған тізімдер бойынша орындалуы мүмкін әрекеттер кірістіруді, жоюды және өтуді қамтиды.

Singly-linked-list.svg
Түйіндері екі өрісті қамтитын жеке байланыстырылған тізім: бүтін мән және келесі түйінге сілтеме

Келесі код жекелеген байланыстырылған тізімнің соңына «мәні» бар жаңа түйінді қалай қосуға болатындығын көрсетеді:

түйін addNode(түйін бас, int мәні) {    түйін темп, б; // temp және p екі түйінін жариялаңыз    темп = createNode(); // assume createNode = 0 мәні бар жаңа түйін жасайды және келесі NULL сілтеме жасайды.    темп->деректер = мәні; // түйіннің деректер бөлігіне элементтің мәнін қосу    егер (бас == ЖОҚ) {        бас = темп;     // байланыстырылған тізім бос болған кезде    }    басқа {        б = бас; // басты б-ге тағайындау         уақыт (б->Келесі != ЖОҚ) {            б = б->Келесі; // p соңғы түйін болғанша тізімді өтіңіз. Соңғы түйін әрдайым NULL-ге нұсқайды.        }        б->Келесі = темп; // Алдыңғы соңғы түйінді құрылған жаңа түйінге бағыттаңыз.    }    қайту бас;}

Екі еселенген тізім

Негізгі мақала: Екі еселенген тізім

«Екі еселенген байланыстырылған тізімде» әрбір түйінде келесі түйін сілтемесінен басқа, «алдыңғы» түйінге ретімен сілтеме жасайтын екінші сілтеме өрісі бар. Екі сілтеме «алға» («с») және «артқа» немесе «келесі» және «алдыңғы» («алдыңғы») деп аталуы мүмкін.

Doubly-linked-list.svg
Түйіндері үш өрісті қамтитын екі еселенген тізім: бүтін мән, келесі түйінге сілтеме және алдыңғы түйінге кері сілтеме

Ретінде белгілі әдіс XOR байланыстыру екі түйінді тізімді әр түйінде бір сілтеме өрісін қолдану арқылы жүзеге асыруға мүмкіндік береді. Алайда, бұл техника адрестерге биттік операциялар жасау мүмкіндігін қажет етеді, сондықтан кейбір жоғары деңгейлі тілдерде қол жетімді болмауы мүмкін.

Көптеген қазіргі заманғы операциялық жүйелер белсенді процестерге, ағындарға және басқа да динамикалық объектілерге сілтемелерді қолдау үшін қосарланған тізімдерді қолданады.[2] Үшін жалпы стратегия руткиттер анықтаудан жалтару дегеніміз - өздерін осы тізімдерден ажырату.[3]

Байланыстырылған тізім

«Көбейтін сілтеме тізімінде» әр түйінде екі немесе одан да көп сілтеме өрістері бар, әр өріс бірдей мәліметтер жазбаларының жиынтығын бірдей жиынтықтың әр түрлі ретімен қосу үшін қолданылады (мысалы, аты, бөлімі бойынша, туған күні бойынша, және т.б.). Екі еселенген тізімдер көбейтілген тізімнің ерекше жағдайлары ретінде қарастырылуы мүмкін, ал екі және одан да көп бұйрықтардың бір-біріне қарама-қарсы болуы қарапайым және тиімді алгоритмдерге әкеледі, сондықтан оларды әдетте жеке жағдай ретінде қарастырады.

Дөңгелек байланыстырылған тізім

Тізімнің соңғы түйінінде сілтеме өрісі көбінесе а нөл сілтеме, одан әрі түйіндердің жоқтығын көрсету үшін арнайы мән қолданылады. Аз кездесетін шарт - бұл тізімнің бірінші түйініне сілтеме жасау; бұл жағдайда тізім «айналмалы» немесе «айналмалы түрде байланыстырылған» деп аталады; әйтпесе, «ашық» немесе «сызықтық» деп аталады. Бұл соңғы көрсеткіш бірінші түйінді көрсететін тізім.

Circularly-linked-list.svg
Дөңгелек байланыстырылған тізім

Дөңгелек айналдырылған тізім жағдайында бірінші түйін сонымен қатар тізімнің соңғы түйінін көрсетеді.

Қарауылдық түйіндер

Негізгі мақала: Қарауыл түйіні

Кейбір іске асыруларда қосымша «қарауыл» немесе «манекенді» түйін алғашқы деректер жазбас бұрын немесе соңғысы қосылуы мүмкін. Бұл конвенция барлық сілтемелерді қауіпсіз түрде анықтауға болатындығына және кез-келген тізімде (тіпті элементтер элементтері жоқ) әрқашан «бірінші» және «соңғы» түйіндерге ие болуын қамтамасыз ете отырып, тізімді өңдеудің кейбір алгоритмдерін жеңілдетеді және жеделдетеді.

Бос тізімдер

Бос тізім - бұл мәліметтер жазбасы жоқ тізім. Әдетте бұл нөлдік түйіндермен бірдей. Егер қарауыл түйіндері қолданылып жатса, тізім тек қана қарауыл түйіндері болған кезде бос деп аталады.

Хэш байланыстыру

Сілтеме өрістері физикалық түрде түйіндердің бөлігі болмауы керек. Егер деректер жазбалары массивте сақталса және олардың индекстері бойынша сілтеме жасалса, сілтеме өрісі деректер жазбаларымен бірдей индекстермен бөлек массивте сақталуы мүмкін.

Тұтқалар тізімі

Бірінші түйінге сілтеме бүкіл тізімге қол жеткізуге мүмкіндік беретіндіктен, бұл сілтеме көбінесе тізімнің «адресі», «сілтегіші» немесе «тұтқасы» деп аталады. Байланыстырылған тізімдермен жұмыс жасайтын алгоритмдер мұндай тұтқаларды енгізу тізіміне алады және тұтқаларды алынған тізімдерге қайтарады. Шын мәнінде, мұндай алгоритмдердің аясында «тізім» сөзі «тізімнің тұтқасы» деген мағынаны білдіреді. Алайда, кейбір жағдайларда, оның бірінші және соңғы түйіндерін көрсететін, екі сілтемеден тұратын тұтқа тізіміне жүгіну ыңғайлы болуы мүмкін.

Баламаларды біріктіру

Жоғарыда келтірілген баламалар кез-келген тәсілмен ерікті түрде біріктірілуі мүмкін, сондықтан қарауылсыз дөңгелек қос тізбекті тізімдер, қарауылдармен дөңгелек дара байланыстырылған тізімдер және т.б.

Сауда-саттық

Компьютерлік бағдарламалау мен дизайндағы көптеген таңдау сияқты, ешқандай әдіс барлық жағдайларға сәйкес келмейді. Байланыстырылған тізім құрылымы бір жағдайда жақсы жұмыс істеуі мүмкін, ал екінші жағдайда қиындықтар тудыруы мүмкін. Бұл байланыстырылған тізім құрылымдарымен байланысты кейбір жалпы сауда-саттықтардың тізімі.

Байланыстырылған тізімдер мен динамикалық массивтерге қатысты

Мәліметтер тізімінің құрылымын салыстыру
Байланыстырылған тізімМассивДинамикалық массивТеңдестірілген ағашКездейсоқ кіру тізіміМассив ағашы
ИндекстеуΘ (n)Θ (1)Θ (1)Θ (журнал n)Θ (журнал n)[4]Θ (1)
Кірістіру / жою басындаΘ (1)ЖоқΘ (n)Θ (журнал n)Θ (1)Θ (n)
Кірістіру / жою соңындаWhen (1) соңғы болғанда элемент белгілі;
Θ (n) соңғы кезде элемент белгісіз		ЖоқΘ (1) амортизацияланғанΘ (журнал n)Жоқ [4]Θ (1) амортизацияланған
Кірістіру / жою ортасындаіздеу уақыты + Θ (1)[5][6]ЖоқΘ (n)Θ (журнал n)Жоқ [4]Θ (n)
Бос орын (орташа)Θ (n)0Θ (n)[7]Θ (n)Θ (n)Θ (√n)

A динамикалық массив - бұл барлық элементтерді жадқа тұрақты түрде бөлетін және элементтердің ағымдағы санының есебін жүргізетін мәліметтер құрылымы. Егер динамикалық жиымға арналған бос орын асып кетсе, ол қайта бөлінеді және (мүмкін) көшіріледі, бұл қымбат операция.

Байланыстырылған тізімдердің динамикалық массивтерге қарағанда бірнеше артықшылықтары бар. Тізімнің белгілі бір нүктесінде элементті енгізу немесе жою, егер біз оны түйінге индекстегенбіз (алып тасталатынға дейін немесе кірістіру нүктесіне дейін), бұл тұрақты уақыттағы жұмыс (әйтпесе онсыз) сілтеме ол O (n)), ал кездейсоқ жерлерде динамикалық массивке енгізу орташа алғанда элементтердің жартысын, ал нашар элементтердің барлығын жылжытуды қажет етеді. Массивтен элементті тұрақты уақытта оның орнын «бос» деп белгілеу арқылы «жоюға» болады, бірақ бұл бөлшектену бұл қайталануды орындауға кедергі келтіреді.

Сонымен қатар, байланыстырылған тізімге көптеген элементтерді ерікті түрде енгізуге болады, тек жалпы жадпен шектеледі; ал динамикалық массив ақырында өзінің негізгі массивтік құрылымын толтырады және оны қайта бөлуге тура келеді - қымбат операция, тіпті егер жады фрагменттелген болса, мүмкін болмайды, дегенмен қайта бөлу құны кірістірулерден орташаланған болуы мүмкін және қайта бөлуге байланысты енгізу әлі де болады амортизацияланған O (1). Бұл элементтерді массивтің соңына қосуға көмектеседі, бірақ орташа позицияларға енгізу (немесе оларды алып тастау) сәйкес келуді сақтау үшін деректер жылжуына байланысты тыйым салынған шығындарды алып келеді. Көптеген элементтер алынып тасталған массивтің бос орын босқа кетпеуі үшін оның өлшемін өзгертуге тура келуі мүмкін.

Екінші жағынан, динамикалық массивтер (сонымен қатар тұрақты өлшемдер) массивтің мәліметтер құрылымы ) тұрақты уақытқа рұқсат етіңіз кездейсоқ қол байланыстырылған тізімдерге рұқсат етіледі дәйекті қол жетімділік элементтерге. Бір-бірімен байланыстырылған тізімдер, шын мәнінде, тек бір бағытта оңай өтеді. Бұл байланыстырылған тізімдерді қосымшалар үшін жарамсыз етеді, мысалы элементті индексі бойынша жылдам іздеу пайдалы, мысалы үйіндісі. Массивтер мен динамикалық массивтердегі кезекті қол жетімділік көптеген машиналардағы байланыстырылған тізімдерге қарағанда жылдамырақ, өйткені олар оңтайлы анықтама орны және осылайша деректерді кэштеуді жақсы пайдаланыңыз.

Байланыстырылған тізімдердің тағы бір кемшілігі - сілтемелер үшін қажет қосымша сақтау орны, бұл оларды көбінесе кішігірім деректер элементтерінің тізімдері үшін практикалық емес етеді. кейіпкерлер немесе логикалық мәндер, өйткені сілтемелерге арналған үстеме ақы деректердің өлшемінен екі немесе одан көп есе асып кетуі мүмкін. Керісінше, динамикалық массив үшін мәліметтердің өзі үшін орын ғана қажет (және басқару деректерінің өте аз мөлшері).[1 ескерту] Сондай-ақ, әр жаңа элемент үшін жадыны бөлек бөлу ақырын және драйваторлы, ысырапкерлігімен болуы мүмкін, проблеманы қолдану арқылы шешіледі жад пулдары.

Кейбір гибридтік шешімдер екі ұсыныстың артықшылықтарын біріктіруге тырысады. Тіркелмеген байланыстырылған тізімдер әрбір тізім түйінінде бірнеше элементтерді сақтаңыз, кэш өнімділігін арттырыңыз, ал сілтемелер үшін жадтың шығынын азайтыңыз. CDR кодтау сілтемелерді сілтеме жазбасының соңына дейін созылатын нақты мәліметтермен алмастыру арқылы екеуін де жасайды.

Динамикалық массивтер мен байланыстырылған тізімдерді қолданудың оң және теріс жақтарын көрсететін жақсы мысал - Джозефус мәселесі. Джозефус проблемасы - бұл адамдар тобын шеңберге тұрғызу арқылы жұмыс істейтін сайлау әдісі. Алдын ала белгіленген адамнан бастап, шеңбер бойымен санауға болады n рет. Бір рет nАдамға қол жеткізілді, оларды шеңберден шығарып, мүшелерді шеңберді жабу керек. Процесс тек бір адам қалғанға дейін қайталанады. Ол адам сайлауда жеңіске жетеді. Бұл динамикалық массивке қарсы байланыстырылған тізімнің күшті және әлсіз жақтарын көрсетеді, өйткені егер адамдар дөңгелек байланыстырылған тізімдегі байланыстырылған түйіндер ретінде қарастырылса, онда бұл байланыстырылған тізімнің түйіндерді қаншалықты оңай жоюға болатындығын көрсетеді (өйткені ол тек керек сілтемелерді әртүрлі түйіндерге қайта орналастырыңыз). Алайда, байланыстырылған тізім келесі жоюға болатын адамды табуда нашар болады және сол адамды тапқанға дейін тізім бойынша іздеу керек болады. Екінші жағынан, динамикалық массив түйіндерді (немесе элементтерді) жоюға нашар болады, өйткені ол барлық элементтерді тізімге жеке ауыстырмай бір түйінді алып тастай алмайды. Алайда, оны табу өте оңай nоларды шеңбердегі позициялары бойынша тікелей сілтеме жасай отырып, шеңбердегі адам.

The тізім рейтингі мәселе байланысты тізімді ұсынуды массивке тиімді түрлендіруге қатысты. Кәдімгі компьютер үшін маңызды емес болса да, бұл мәселені а параллель алгоритм күрделі және көптеген зерттеу объектілері болды.

A теңдестірілген ағаш жадқа қол жеткізудің ұқсас үлгілері мен байланыстырылған тізімге кеңістіктің үстеме кеңістігі бар, бұл индекстеуді анағұрлым тиімді жүргізуге мүмкіндік береді, кездейсоқ қол жеткізу үшін O (n) орнына O (log n) уақыт алады. Алайда кірістіру және жою операциялары тепе-теңдікті сақтау үшін ағаштармен жүргізілетін манипуляцияларға байланысты қымбатқа түседі. Ағаштардың өзін-өзі теңгерімді күйде ұстап тұру схемалары бар: AVL ағаштары немесе қызыл-қара ағаштар.

Жалғыз байланысты сызықтық тізімдер және басқа тізімдер

Қосарланған және дөңгелек тізімдердің жеке байланыстырылған сызықтық тізімдерге қарағанда артықшылығы бар, ал сызықтық тізімдер кейбір жағдайларда оларды артықшылық беретін артықшылықтар ұсынады.

Жалғыз байланысты сызықтық тізім - бұл рекурсивті деректер құрылымы, өйткені онда a сілтемесі бар кішірек сол типтегі объект. Сол себепті сызықтық тізімдер бойынша көптеген операциялар (мысалы.) біріктіру екі тізімді немесе элементтерді кері тәртіппен санауды) көбінесе кез-келген шешімге қарағанда өте қарапайым рекурсивті алгоритмдер бар. қайталанатын командалар. Бұл рекурсивті шешімдер қосарланған және дөңгелек байланыстырылған тізімдерге бейімделуі мүмкін болғанымен, процедуралар, әдетте, қосымша аргументтер мен күрделі жағдайларды қажет етеді.

Сызықтық байланыстырылған тізімдер де мүмкіндік береді құйрықты бөлісу, ішкі тізімнің жалпы қорытынды бөлігін екі түрлі тізімнің терминалдық бөлігі ретінде пайдалану. Атап айтқанда, егер тізімнің басында жаңа түйін қосылса, бұрынғы тізім жаңасының құйрығы ретінде қол жетімді болып қалады - қарапайым мысал деректердің тұрақты құрылымы. Тағы да, бұл басқа нұсқаларға сәйкес келмейді: түйін ешқашан екі түрлі дөңгелек немесе қосарланған тізімдерге жатпауы мүмкін.

Атап айтқанда, ақырғы күзет түйіндері бір-бірімен байланысқан дөңгелек емес тізімдер арасында бөлінуі мүмкін. Сол күзет түйіні үшін де қолданылуы мүмкін әрқайсысы осындай тізім. Жылы Лисп, мысалы, әрбір тиісті тізім арнайы түйінге сілтемемен аяқталады нөл немесе (), кімнің Автокөлік және CDR сілтемелер өзін көрсетеді. Осылайша, Lisp процедурасы қауіпсіз түрде жүзеге асырылуы мүмкін Автокөлік немесе CDR туралы кез келген тізім.

Сәнді нұсқалардың артықшылығы көбінесе алгоритмдердің тиімділігімен емес, күрделілігімен шектеледі. Дөңгелек тізімді, атап айтқанда, сызықтық тізіммен, бірінші және соңғы түйіндерді көрсететін екі айнымалымен бірге, қосымша шығынсыз еліктеуге болады.

Екі жақты және жеке байланыстырылған

Екі байланыстырылған тізімдерге бір түйінге көбірек орын қажет (егер біреу қолданбаса) XOR байланыстыру ), және олардың қарапайым операциялары қымбатырақ; бірақ оларды манипуляциялау көбінесе оңай, өйткені олар тізімге екі бағытта да жылдам әрі қарапайым дәйекті қол жеткізуге мүмкіндік береді. Екі еселенген байланыстырылған тізімде тек сол түйіннің мекен-жайы берілген операциялардың тұрақты санына түйінді енгізуге немесе жоюға болады. Мұны жеке байланыстырылған тізімде жасау үшін біреуінің болуы керек меңзердің мекен-жайы сол түйінге, ол бүкіл тізімнің дескрипторы (бірінші түйін жағдайында) немесе сілтеме өрісі алдыңғы түйін. Кейбір алгоритмдер екі бағытта қол жетімділікті қажет етеді. Екінші жағынан, қосарланған тізімдер құйрықты бөлуге мүмкіндік бермейді және оларды пайдалану мүмкін емес деректердің тұрақты құрылымдары.

Дөңгелек байланыстырылған және сызықтық байланысты

Дөңгелек байланыстырылған тізім табиғи түрде дөңгелек болатын массивтерді ұсынудың табиғи нұсқасы болуы мүмкін, мысалы. а бұрыштары көпбұрыш, бассейні буферлер пайдаланылатын және шығарылатын ФИФО («бірінші кіру, бірінші шығу») реті немесе болуы керек процестер жиынтығы уақыт бөлісті жылы айналма тәртіп. Бұл қосымшаларда кез-келген түйінге бағыттаушы бүкіл тізімнің тұтқасы ретінде қызмет етеді.

Дөңгелек тізіммен көрсеткіш соңғы түйінге бір сілтеме арқылы бірінші түйінге оңай қол жеткізуге мүмкіндік береді. Осылайша, тізімнің екі жағына да қол жетімділікті қажет ететін қосымшаларда (мысалы, кезекті жүзеге асыруда) дөңгелек құрылым құрылымды құрылымның екеуінің орнына бір көрсеткішпен басқаруға мүмкіндік береді.

Дөңгелек тізімді әр уақытта соңғы түйіннің адрестерін беру арқылы тұрақты уақытта екі дөңгелек тізімге бөлуге болады. Операция сол екі түйіннің сілтеме өрістерінің мазмұнын ауыстырудан тұрады. Екі бірдей тізімдегі кез-келген екі түйінге бірдей операцияны қолдану екі тізімді бір тізімге қосады. Бұл қасиет кейбір алгоритмдер мен мәліметтер құрылымын айтарлықтай жеңілдетеді, мысалы төрт қырлы және беткей.

Бос үшін қарапайым көрініс дөңгелек тізім (егер мұндай нәрсе мағынасы болса) - бұл тізімнің түйіндері жоқ екенін көрсететін нөлдік көрсеткіш. Бұл таңдау болмаса, көптеген алгоритмдер осы ерекше жағдайды тексеріп, оны бөлек қарастыруы керек. Керісінше, босты белгілеу үшін нөлді қолдану сызықтық тізім табиғи болып табылады және көбінесе ерекше жағдайларды жасайды.

Қарауылдық түйіндерді пайдалану

Қарауыл түйіні әрбір элемент үшін келесі немесе алдыңғы түйіндердің болуын, тіпті бос тізімдерде де кем дегенде бір түйін болуын қамтамасыз ете отырып, белгілі бір тізім операцияларын жеңілдетуі мүмкін. Сондай-ақ, тізім соңындағы тексерулерді жою үшін тиісті деректер өрісімен тізімнің соңында қарауыл түйінін пайдалануға болады. Мысалы, тізімді сканерлеу кезінде берілген мәні бар түйінді іздейді х, күзетшінің деректер өрісін орнатыңыз х цикл ішінде тізімнің соңын тексеруді қажет етпейді. Тағы бір мысал - екі сұрыпталған тізімдерді біріктіру: егер олардың күзетшілерінде деректер өрістері + ∞ деп орнатылған болса, келесі шығыс түйінін таңдау үшін бос тізімдер үшін арнайы өңдеу қажет емес.

Алайда, қарауыл түйіндері қосымша кеңістікті пайдаланады (әсіресе көптеген қысқа тізімдер қолданылатын қосымшаларда) және олар басқа операцияларды қиындатуы мүмкін (мысалы, жаңа бос тізімді құру).

Алайда, егер дөңгелек тізім тек сызықтық тізімді имитациялау үшін қолданылса, әрбір тізімге, соңғы және алғашқы деректер түйіндерінің арасында, бір қарауыл түйінін қосу арқылы, кейбір қиындықтардан аулақ бола аласыз. Осы конвенциямен бос тізім тек келесі түйін сілтемесі арқылы өзін көрсететін күзет түйінінен тұрады. Содан кейін тізімнің тұтқасы, егер тізім бос болмаса, күзетшінің алдында мәліметтердің соңғы түйініне нұсқауыш болуы керек; немесе қарауылдың өзіне, егер тізім бос болса.

Дәл осы трюкті екі рет байланысқан сызықтық тізімді оңтайландыру үшін қолдануға болады, оны бір қарауыл түйіні бар дөңгелек қосарланған тізімге айналдырады. Алайда, бұл жағдайда тұтқасы жалған түйіннің өзіне арналған жалғыз көрсеткіш болуы керек.[8]

Байланыстырылған тізім әрекеттері

Байланыстырылған тізімдерді өз орнында басқарған кезде, алдыңғы тапсырмаларда жарамсыз болған мәндерді пайдаланбауға тырысу керек. Бұл байланыстырылған тізім түйіндерін енгізу немесе жою алгоритмдерін біршама нәзік етеді. Бұл бөлім береді псевдокод жеке, қосарланған және дөңгелек байланыстырылған тізімдерден түйіндерді қосу немесе жою үшін. Бүкіл уақытта біз қолданамыз нөл тізімнің соңындағы маркерге немесе қарауыл, ол бірнеше тәсілдермен жүзеге асырылуы мүмкін.

Сызықтық байланыстырылған тізімдер

Жалғыз байланысты тізімдер

Біздің түйін деректер құрылымында екі өріс болады. Біз сондай-ақ айнымалыны сақтаймыз firstNode ол әрқашан тізімдегі бірінші түйінді көрсетеді немесе болып табылады нөл бос тізім үшін.

жазба Түйін{    деректер; // Деректер түйінде сақталады    Түйін Келесі // A анықтама[2] келесі түйінге, соңғы түйін үшін нөл}
жазба Тізім{    Түйін firstNode // тізімнің бірінші түйініне нұсқайды; бос тізім үшін нөл}

Байланыстырылған тізімнің өтуі қарапайым, бірінші түйіннен басталып, әрқайсысы бойынша жүреді Келесі соңына дейін сілтеме:

түйін: = list.firstNodeуақыт түйін нөл емес    (node.data көмегімен бірдеңе жасаңыз)    түйін: = node.next

Төмендегі код жеке байланыстырылған тізімдегі бар түйіннен кейін түйінді енгізеді. Диаграмма оның қалай жұмыс істейтінін көрсетеді. Бұрыннан бұрын түйінді енгізу тікелей мүмкін емес; оның орнына алдыңғы түйінді қадағалап, одан кейін түйінді енгізу керек.

CPT-LinkedLists-addingnode.svg
функциясы insertAfter (Түйін түйін, Түйін newNode) // түйіннен кейін newNode кірістіру    newNode.next: = node.next    node.next: = newNode

Тізімнің басында енгізу үшін бөлек функция қажет. Бұл жаңартуды қажет етеді firstNode.

функциясы insertBeginning (Тізім тізім, Түйін newNode) // ағымдағы бірінші түйінге дейін түйінді енгізу    newNode.next: = list.firstNode    list.firstNode: = newNode

Сол сияқты, бізде түйінді жоюға арналған функциялар бар кейін берілген түйін және тізімнің басынан түйінді жою үшін. Диаграмма біріншісін көрсетеді. Белгілі бір түйінді табу және жою үшін алдыңғы элементті қайтадан қадағалап отыру керек.

CPT-LinkedLists-deletingnode.svg
функциясы removeAfter (Түйін түйін) // осыдан өткен түйінді алып тастаңыз    ескіргенNode: = node.next    node.next: = node.next.next    ескіргенNode жою
функциясы removeBeginning (Тізім тізім) // бірінші түйінді алып тастаңыз    ескіргенNode: = list.firstNode    list.firstNode: = list.firstNode.next // жойылған түйінді көрсетіңіз    ескірген түйінді жою

Байқаңыз removeBeginning () жиынтықтар list.firstNode дейін нөл тізімдегі соңғы түйінді алып тастағанда.

Біз артқа қарай қайталай алмайтындықтан, тиімді кірістіруБұрын немесе Алдында алып тастаңыз операциялар мүмкін емес. Тізімге белгілі бір түйінге дейін кіру үшін тізімнен өту керек, бұл O (n) жұмыс уақыты ең нашар болады.

Тізім құрылымының бөлігі ретінде құйрыққа сілтеме жасалмаса, бір байланыстырылған тізімді екіншісіне қосу тиімсіз болуы мүмкін, өйткені біз құйрықты табу үшін бірінші тізімді түгел айналып өтіп, содан кейін екінші тізімді осыған қосуымыз керек. Осылайша, егер екі сызықтық байланыстырылған тізімдер әрқайсысының ұзындығы болса , тізім қосу бар уақыттың асимптотикалық күрделілігі туралы . Лисп тілдер тобында тізімнің қосымшасы қосу рәсім.

Байланыстырылған тізім операцияларының көптеген ерекше жағдайларын тізімнің алдыңғы жағына жалған элемент енгізу арқылы жоюға болады. Бұл тізімнің басталуы үшін арнайы жағдайлардың болмауын қамтамасыз етеді және екеуін де көрсетеді insertBeginning () және removeBeginning () қажет емес. Бұл жағдайда тізімдегі алғашқы пайдалы деректер мына жерден табылады тізім.firstNode.Келесі.

Дөңгелек байланыстырылған тізім

Дөңгелек байланыстырылған тізімде барлық түйіндер қолданылмай, үздіксіз шеңбермен байланысқан нөл. Алдыңғы және артқы жағы бар тізімдер үшін (кезек сияқты) тізімдегі соңғы түйінге сілтеме сақталады. The Келесі соңғы түйіннен кейінгі түйін - бұл бірінші түйін. Элементтер тізімнің артына қосылып, алдыңғы қатардан тұрақты уақытта алынып тасталуы мүмкін.

Шеңбер сілтемелі тізімдер дара немесе қосалқы байлануы мүмкін.

Дөңгелек байланыстырылған тізімдердің екі түрі де кез-келген түйіннен басталатын толық тізімді өту мүмкіндігін пайдаланады. Бұл көбінесе сақтаудан аулақ болуға мүмкіндік береді firstNode және lastNode, егер тізім бос болуы мүмкін болса, бізге бос тізім үшін арнайы ұсыныс керек, мысалы lastNode тізімдегі кейбір түйінді көрсететін айнымалы нөл егер ол бос болса; біз осындай а lastNode Мұнда. Бұл ұсыныс бос емес тізіммен түйіндерді қосуды және жоюды айтарлықтай жеңілдетеді, бірақ бос тізімдер бұл жағдайда ерекше жағдай болып табылады.

Алгоритмдер

Мұны қарастырсақ someNode - бұл бос емес дөңгелек тізбектегі кейбір түйіндер, бұл код осы тізімнен басталып, бастап басталады someNode:

функциясы қайталау (someNode)    егер кейбір түйін ≠ нөл        түйін: = кейбірNode    істеу        node.value көмегімен бірдеңе жасаңыз        түйін: = node.next    уақыт түйін ≠ кейбірNode

Байқаңыз, тест »уақыт түйін ≠ someNode «циклдің соңында орналасуы керек. Егер тест циклдің басына жылжытылса, тізімде тек бір түйін болған кезде процедура сәтсіз болады.

Бұл функция «жаңа түйін» түйінін берілген «түйіннен» кейін дөңгелек байланыстырылған тізімге қосады. Егер «түйін» нөл болса, онда ол тізім бос деп есептейді.

функциясы insertAfter (Түйін түйін, Түйін newNode)    егер түйін = нөл    // тізімдер бос        newNode.next: = newNode    басқа        newNode.next: = node.next        node.next: = newNode    жаңарту lastNode қажет болса айнымалы

«L» - бұл дөңгелек байланыстырылған тізімнің соңғы түйініне бағытталған айнымалы (немесе тізім бос болса, нөл) деп есептейік. «NewNode» -ті қосу үшін Соңы тізімнің біреуін жасай алады

insertAfter (L, newNode)L: = newNode

«NewNode» енгізу үшін басы тізімнің біреуін жасай алады

insertAfter (L, newNode)егер L = нөл    L: = newNode

Бұл функция O (1) уақытында берілген «түйін» түйінінің алдына «newVal» мәнін енгізеді. Біз «түйін» мен келесі түйін арасында жаңа түйін жасаймыз, содан кейін «түйін» мәнін сол жаңа түйінге енгіземіз және «newVal» «түйінге» орналастырамыз. Осылайша, тек а. Бар дөңгелек байланыстырылған жеке тізім firstNode айнымалы O (1) уақытта алдыңғы және артқа енгізе алады.

функциясы КірістіруБұрын (Түйін түйін, жаңаVal)    егер түйін = нөл    // тізімдер бос        newNode: = жаңа Түйін (деректер: = newVal, келесі: = newNode)    басқа        newNode: = жаңа Түйін (деректер: = node.data, келесі: = node.next)        node.data: = newVal        node.next: = newNode    жаңарту firstNode қажет болса айнымалы

Бұл функция нөлдік түйінді O (1) уақыт ішінде 1-ден үлкен өлшемдер тізімінен алып тастайды. Ол келесі түйіндегі деректерді түйінге көшіреді, содан кейін түйіндерді орнатады Келесі келесі түйінді аттап өту үшін меңзер.

функциясы алып тастау (Түйін түйін)    егер түйін ≠ нөл және тізім өлшемі> 1        жойылдыМәлімет: = түйін.мәлімет        node.data: = node.next.data        node.next = node.next.next        қайту жойылды

Түйіндер жиымының көмегімен байланыстырылған тізімдер

Кез келген түрін қолдамайтын тілдер анықтама сілтемелерді массив индекстерімен ауыстыру арқылы әлі де сілтеме жасай алады. Тәсілін сақтау керек массив туралы жазбалар, мұнда әрбір жазбада массивтің келесі (және мүмкін алдыңғы) түйінінің индексін көрсететін бүтін өрістер бар. Массивтегі барлық түйіндерді қолдану қажет емес. Егер жазбаларға қолдау көрсетілмесе, параллель массивтер орнына жиі қолдануға болады.

Мысал ретінде көрсеткіштердің орнына массивтерді қолданатын келесі сілтеме тізбесін қарастырыңыз:

жазба Кіру {    бүтін Келесі; // жиымдағы келесі жазба индексі    бүтін алдыңғы; // алдыңғы жазба (егер екі сілтеме болса)    жіп аты;    нақты теңгерім;}

Байланыстырылған тізімді осы құрылымдардың жиымын құру арқылы және бірінші элементтің индексін сақтау үшін бүтін айнымалы құруға болады.

бүтін listHeadКіру Жазбалар [1000]

Элементтер арасындағы сілтемелер келесі (немесе алдыңғы) ұяшықтың массив индексін берілген элемент шегінде Келесі немесе Алдыңғы өріске орналастыру арқылы жасалады. Мысалға:

КөрсеткішКелесіАлдыңғыАты-жөніБаланс
014Джонс, Джон123.45
1−10Смит, Джозеф234.56
2 (тізімHead)4−1Адамс, Адам0.00
3Елемеңіз, Игнатий999.99
402Басқа, Анита876.54
5
6
7

Жоғарыдағы мысалда, ListHead тізімдегі бірінші жазбаның орны 2-ге тең болады. 3 пен 5-тен 7-ге дейінгі тізім тізімге кірмейтініне назар аударыңыз. Бұл ұяшықтар тізімге кез-келген қосымшалар үшін қол жетімді. Құру арқылы ListFree бүтін айнымалы, а тегін тізім қол жетімді ұяшықтарды бақылау үшін жасалуы мүмкін. Егер барлық жазбалар қолданылып жатса, онда жаңа жазбалар тізімде сақталмас бұрын массивтің өлшемін үлкейту керек немесе кейбір элементтерді жою қажет болады.

Келесі код тізімді айналып өтіп, атаулар мен шоттағы қалдықтарды көрсетеді:

i: = listHeadуақыт мен ≥ 0 // тізім бойынша цикл    i, Records [i] .name, Records [i] .balance басып шығару // баспа жазбасы    i: = жазбалар [i] .кейінгі

Таңдау алдында, бұл тәсілдің артықшылықтарына мыналар жатады:

  • Байланыстырылған тізім жылжытылады, яғни оны қалауыңыз бойынша жадқа көшіруге болады, сонымен қатар ол тез және тікелей болуы мүмкін серияланған дискіде сақтау немесе желі арқылы тасымалдау үшін.
  • Массив индекстері кішігірім тізім үшін көптеген архитектурадағы толық көрсеткішке қарағанда айтарлықтай аз орын алады.
  • Анықтама орны түйіндерді жадыда сақтау және оларды мезгіл-мезгіл қайта құру арқылы жақсартуға болады, бірақ оны жалпы дүкенде де жасауға болады.
  • Аңқау динамикалық жад бөлгіштер бөлінген әр түйін үшін үстеме қойманың шамадан тыс мөлшерін жасай алады; бұл тәсілде бір түйінге ешқандай шығындар бөлінбейді.
  • Алдын ала бөлінген жиымнан жазбаны алу әр түйін үшін динамикалық жадыны бөлуді қолданудан гөрі жылдамырақ, себебі жадыны динамикалық бөлу үшін қажетті өлшемдегі бос жадының блогын іздеу қажет.

Бұл тәсілдің бір басты кемшілігі бар: ол түйіндер үшін жеке жад кеңістігін жасайды және басқарады. Бұл келесі мәселелерге әкеледі:

  • Бұл іске асырудың күрделілігін арттырады.
  • Толық болған кезде үлкен массивті өсіру қиын немесе мүмкін емес, ал жалпы жад пулында жаңа байланыстырылған тізімнің түйініне орын табу оңайырақ болуы мүмкін.
  • Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear (O (n)) instead of constant time (although it's still an амортизацияланған constant).
  • Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.

For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.

Тілдерді қолдау

Көптеген бағдарламалау тілдері сияқты Лисп және Схема have singly linked lists built in. In many функционалды тілдер, these lists are constructed from nodes, each called a cons немесе cons cell. The cons has two fields: the автомобиль, a reference to the data for that node, and the cdr, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.

In languages that support деректердің дерексіз түрлері or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using сілтемелер бірге жазбалар.

Internal and external storage

When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage, or merely to store a reference to the data, called сыртқы жад. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better анықтама орны, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).

External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Although with internal storage the same data can be placed in multiple lists by including multiple Келесі references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.

In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.

Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the Келесі (және prev if double linked list) references in the same location. After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.

Example of internal and external storage

Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:

жазба мүше { // member of a family    мүше next;    жіп firstName;    бүтін жас;}жазба отбасы { // the family itself    отбасы next;    жіп lastName;    жіп address;    мүше мүшелер // head of list of members of this family}

To print a complete list of families and their members using internal storage, we could write:

aFamily := Families // start at head of families listуақыт aFamily ≠ нөл // loop through list of families    print information about family    aMember := aFamily.members // get head of list of this family's members    уақыт aMember ≠ нөл // loop through list of members        print information about member        aMember := aMember.next    aFamily := aFamily.next

Using external storage, we would create the following structures:

жазба түйін { // generic link structure    түйін next;    көрсеткіш деректер // generic pointer for data at node}жазба мүше { // structure for family member    жіп firstName;    бүтін жас}жазба отбасы { // structure for family    жіп lastName;    жіп address;    түйін мүшелер // head of list of members of this family}

To print a complete list of families and their members using external storage, we could write:

famNode := Families // start at head of families listуақыт famNode ≠ нөл // loop through list of families    aFamily := (family) famNode.data // extract family from node    print information about family    memNode := aFamily.members // get list of family members    уақыт memNode ≠ нөл // loop through list of members        aMember := (member)memNode.data // extract member from node        print information about member        memNode := memNode.next    famNode := famNode.next

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (түйін), and this language does not have parametric types.

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.

Speeding up search

Finding a specific element in a linked list, even if it is sorted, normally requires O(n) time (сызықтық іздеу ). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.

In an unordered list, one simple heuristic for decreasing average search time is the алдыңғы эвристикалық, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "индекс " a linked list using a more efficient external data structure. For example, one can build a қызыл-қара ағаш немесе хэш-кесте whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

Random access lists

A random access list is a list with support for fast random access to read or modify any element in the list.[9] One possible implementation is a skew binary random access list пайдаланып skew binary number system, which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index.[9] Random access lists can be implemented as persistent data structures.[9]

Random access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations.[9]

A simple extension to random access lists is the min-list, which provides an additional operation that yields the minimum element in the entire list in constant time (without[түсіндіру қажет ] mutation complexities).[9]

Байланысты деректер құрылымдары

Екеуі де стектер және кезектер are often implemented using linked lists, and simply restrict the type of operations which are supported.

The өткізіп жіберу is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.

A екілік ағаш can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node.

Ан unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved кэш performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.

A хэш-кесте may use linked lists to store the chains of items that hash to the same position in the hash table.

A үйінді shares some of the ordering properties of a linked list, but is almost always implemented using an array. Instead of references from node to node, the next and previous data indexes are calculated using the current data's index.

A self-organizing list rearranges its nodes based on some heuristic which reduces search times for data retrieval by keeping commonly accessed nodes at the head of the list.

Ескертулер

  1. ^ The amount of control data required for a dynamic array is usually of the form , қайда is a per-array constant, is a per-dimension constant, and is the number of dimensions. және are typically on the order of 10 bytes.

Әдебиеттер тізімі

  1. ^ Skiena, Steven S. (2009). The Algorithm Design Manual (2-ші басылым). Спрингер. б. 76. ISBN  9781848000704. We can do nothing without this list predecessor, and so must spend linear time searching for it on a singly-linked list.
  2. ^ а б «Мұрағатталған көшірме». Архивтелген түпнұсқа 2015-09-23. Алынған 2015-07-31.CS1 maint: тақырып ретінде мұрағатталған көшірме (сілтеме)
  3. ^ http://www.cs.dartmouth.edu/~sergey/me/cs/cs108/rootkits/bh-us-04-butler.pdf
  4. ^ а б c Крис Окасаки (1995). «Таза функционалды кездейсоқ қол жетімді тізімдер». Функционалды бағдарламалау тілдері және компьютерлік сәулет бойынша жетінші халықаралық конференция материалдары: 86–95. дои:10.1145/224164.224187.
  5. ^ 1-ші күн - Бярн Строуструп: C ++ 11 стилі кезінде GoingNative 2012 қосулы channel9.msdn.com 45-минуттан немесе фольга 44-тен
  6. ^ Нөмірдің қысылуы: Неге сіз ешқашан, ешқашан, ешқашан кодтағы сілтемелер тізімін ешқашан қолданбауыңыз керек кезінде kjellkod.wordpress.com
  7. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Мунро, Дж .; Демейн, ED (1999), Оңтайлы уақыт пен кеңістіктегі өлшемді массивтер (CS-99-09 техникалық есебі) (PDF), Ватерлоо университетінің информатика кафедрасы
  8. ^ Ford, William; Topp, William (2002). Data Structures with C++ using STL (Екінші басылым). Prentice-Hall. 466-467 бет. ISBN  0-13-085850-1.
  9. ^ а б c г. e Okasaki, Chris (1995). Purely Functional Random-Access Lists (PS). In Functional Programming Languages and Computer Architecture. ACM Press. 86-95 бет. Алынған 7 мамыр, 2015.

Әрі қарай оқу

Сыртқы сілтемелер