Кіріспе
Байланысты тізім деректері құрылымы Компьютерлік ғылымда қосарланған тізім - бұл бірімен бірі бірі бірімен бірі біріктірілген жазбалар жиынтығынан тұратын, түйіндер деп аталатын, бірімен бірі бірі біріктірілген деректердің құрылымы. Әрбір торапта үш өріс бар: екі сілтеме өрісі (тораптар тізбесіндегі алдыңғы және келесі торапқа сілтемелер) және бір деректер өрісі. Бастапқы және соңғы түйіндердің алдыңғы және келесі сілтемелері тізімді аралауды жеңілдету үшін белгілі бір терминаторға, әдетте күзетші түйінге немесе нөлге сілтейді. Егер тек бір ғана күзетші түйін болса, онда тізім күзетші түйін арқылы дөңгелек жолмен байланыстырылады. Оны бірдей деректер элементтерінен құрылған, бірақ қарама-қарсы реттілік ретімен екі жеке байланысты тізім ретінде тұжырымдауға болады. Екі түйіндік сілтеме тізімді екі бағытта да өтуге мүмкіндік береді. Екі есе байланыстырылған тізімдегі түйінді қосу немесе алып тастау бірден байланыстырылған тізімдегі бірдей операцияларға қарағанда көбірек сілтемелерді өзгертуді талап ететін болса да, операциялар қарапайым және ықтимал тиімдірек (бірінші түйіндерден басқа түйіндер үшін), өйткені өту кезінде алдыңғы түйінді қадағалаудың қажеті жоқ немесе алдыңғы түйінді табу үшін тізімді аралаудың қажеті жоқ, сондықтан оның сілтемесі өзгертілуі мүмкін.
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders. The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
Номенклатура және оны жүзеге асыру
Барлық практикалық қолданбалар үшін қосарланған тізімнің бірінші және соңғы тораптарына бірден қол жетімді (яғни, өтусіз қол жетімді және әдетте басы мен құйрығы деп аталады) және сондықтан тізімді тізімнің басынан немесе соңында, сәйкесінше, тізімді аралауға мүмкіндік береді: мысалы, тізімді басынан аяғына дейін немесе аяғынан аяғына дейін, тізімде нақты деректер мәні бар торапты іздеу. Екі есе байланысқан тізімнің кез келген түйіні алынғаннан кейін, берілген түйінді бастап тізімнің жаңа қиылысын бастау үшін, кез келген бағытта (бастапқы немесе соңғы жағына қарай) пайдалануға болады. Екі есе байланысқан тізім тораптарының сілтеме өрістері жиі келесі және алдыңғы немесе алдыңғы және артқа деп аталады. Сілтеме өрістерінде сақталған сілтемелер әдетте сілтеме ретінде іске асырылады, бірақ (бірлі-жарым байланыстырылған деректер құрылымында сияқты) олар сонымен қатар түйіндер тұратын массивке адрес ауытқулары немесе индекстері болуы мүмкін.
Түйінді өшіру
Екі рет байланыстырылған тізімдердегідей, "removeAfter" және "removeBefore" "remove(list, node" арқылы жүзеге асырылуы мүмкін. prev) " және "remove(list, node. келесісі)
Асимметриялық қос байланысты тізім
Асимметриялық қосарланған тізім бірден байланысты тізім мен тұрақты қосарланған тізімнің арасында орналасқан. Ол кейбір ерекшеліктерін бірден байланысты тізіммен (бір бағыттағы өту) және басқаларын екі есе байланысты тізіммен (өзгертудің оңайлығы) бөліседі. Бұл әр түйіннің алдыңғы сілтемесі алдыңғы түйінге емес, өзіне сілтеме жасайтын тізім. Бұл түйіндер арасында аз айырмашылық жасаса да (бұл алдыңғы түйіннің ішіндегі ауытқуды көрсетеді), ол тізімнің басын өзгертеді: Бұл бірінші түйінге firstNode сілтемесін оңай өзгертуге мүмкіндік береді. Түйін тізімде болғанша, оның алдыңғы сілтемесі ешқашан нөлге тең болмайды.
It is a list where each node's previous link points not to the previous node, but to the link to itself. While this makes little difference between nodes (it just points to an offset within the previous node), it changes the head of the list: It allows the first node to modify the firstNode link easily. As long as a node is in a list, its previous link is never null.