Mustaqil ishi mavzu: Chiziqli bog’langan ma’lumotlar

Funksiya insertAfter (Tugun tugun, Tugun newNode) // tugundan keyin newNode joylashtiring newNode.next: = node.next node.next: = newNode
Ro'yxatning boshiga qo'shish alohida funktsiyani talab qiladi. Bu yangilanishni talab qiladi birinchi tugun.
Funksiya insertBeginning (Ro'yxat ro'yxat, Tugun newNode) // joriy birinchi tugundan oldin tugunni joylashtiring newNode.next: = list.firstNode list.firstNode: = newNode
Xuddi shunday, bizda tugunni olib tashlash funktsiyalari mavjud keyin berilgan tugun va ro'yxatni boshidan tugunni olib tashlash uchun. Diagramma avvalgisini namoyish etadi. Muayyan tugunni topish va olib tashlash uchun avvalgi elementni yana kuzatib borish kerak.

Funksiya removeAfter (Tugun tugun) // tugundan oldingi tugunni olib tashlang obsoleteNode: = node.next node.next: = node.next.next eskirgan tugunni yo'q qilish
Funksiya olib tashlashBeginning (Ro'yxat ro'yxat) // birinchi tugunni olib tashlash eskirganNode: = list.firstNode list.firstNode: = list.firstNode.next // o'chirilgan tugundan o'tmish eskirgan tugunni yo'q qilish
E'tibor bering removeBeginning () to'plamlar list.firstNode ga bekor ro'yxatdagi so'nggi tugunni olib tashlashda.
Biz orqaga qaytishimiz mumkin emasligi sababli oldin yoki olib tashlashdan oldin operatsiyalarni amalga oshirish mumkin emas. Ro'yxatga ma'lum bir tugundan oldin qo'shilish uchun ro'yxatdan o'tishni talab qiladi, bu eng yomon ish vaqti O (n) bo'ladi.
Ro'yxat tuzilmasining bir qismi sifatida dumga havola qilinmasa, bitta bog'langan ro'yxatni boshqasiga qo'shish samarasiz bo'lishi mumkin, chunki biz dumini topish uchun butun birinchi ro'yxatni bosib o'tib, so'ngra ikkinchi ro'yxatni bunga qo'shishimiz kerak. Shunday qilib, agar ikkita chiziqli bog'langan ro'yxat har birining uzunligi bo'lsa  , ro'yxat qo'shilishi mavjud asimptotik vaqt murakkabligi ning  . Lisp tillar oilasida ro'yxat qo'shilishi qo'shib qo'ying protsedura.
Bog'langan ro'yxat operatsiyalarining ko'pgina maxsus holatlarini ro'yxatning old qismiga qo'g'irchoq element kiritish orqali yo'q qilish mumkin. Bu ro'yxat boshlanishi uchun maxsus holatlar mavjud emasligini ta'minlaydi va ikkalasini ham ko'rsatadi insertBeginning () va removeBeginning () keraksiz. Bunday holda, ro'yxatdagi birinchi foydali ma'lumotlar bu erda topiladi ro'yxat.
Algoritmlar
Buni taxmin qilaylik someNode - bu bo'sh bo'lmagan doiraviy yakka bog'langan ro'yxatdagi ba'zi bir tugunlar, bu kod ushbu ro'yxat bilan boshlanib takrorlanadi someNode: