b'\n_START_ARTICLE_\nListahang pinagdugtong\n_START_PARAGRAPH_\nSa agham pangkompyuter, ang listahang pinagdugtong (linked list) ay isang estruktura ng datos na binubuo ng isang pangkat ng mga nodo (node) na sama-samang kumakatawan sa isang sekwensiya (sequence o sunod sunod na bagay). Sa pinakasimpleng anyo, ang bawat nodo ay binubuo ng datum(o data, impormasyon) at isang reperensiya sa kasunod na nodo sa sekwensiya. Ang mas komplikadong uri ng listahang pinagdugtong ay nagdaragdaga ng karagadagang mga dugton. Ang estrukturang ito ay pumapayag na makapagsagawa ng isang mahusay na insersiyon(pagpasok) o pag-alis(removal) ng mga elemento mula sa anumang posisyon ng sekwensiya. _NEWLINE_Ang isang listahang pinagdugtong na ang mga nodo nito ay naglalaman ng dalawang field: ang halagang intedyer at dugtong(link) sa kasunod nsa nodo. Ang huling nodo ay nakadugtong sa isang terminador na tumutukoy ng wakas ng listahan.\n_START_SECTION_\nPang-isang listahang pinagdugtong(Singly linked list)\n_START_PARAGRAPH_\nrecord List {_NEWLINE_     Node firstNode // tumutukoy sa unang nodo ng listahan; null para sa walang laman na listahan_NEWLINE_ }_NEWLINE_Ang pagtahak(traversal) ng pang-isang listahang pinagdugtong ay nagsisimula sa unang nodo at pagsunod sa next(kasunod) na dugtong(link) hanggang sa makarating sa dulo:_NEWLINE_ node\xc2\xa0:= list.firstNode_NEWLINE_ while node not null_NEWLINE_     (do something with node.data)_NEWLINE_     node\xc2\xa0:= node.next_NEWLINE_Ang sumusunod na koda ay nagpapasok(insert) ng nodo pagkatapos ng isang umiiral na nodo sa pang-isang pinagdugtong na listahan. Ang diagrama ay nagpapakita kung paano ito nangyayari. Ang pagpasok ng nodo sa bago ng isang umiiral na nodo ay hindi direktang maisasagawa. Imbis nito, kailangang alamin ang nakaraan nodo at magpasok ng nodo pagkatapos nito. _NEWLINE__NEWLINE_  _NEWLINE_ function insertAfter(Node node, Node newNode) // pagpapasok ng newNode pagkatapos ng node(nodo) _NEWLINE_     newNode.next\xc2\xa0:= node.next_NEWLINE_     node.next    := newNode_NEWLINE_Ang pagpasok ng nodo sa simula ng listahan ay nangangailangan ng hiwalay na punsiyon. Ito ay nangangailangan ng pagbabago(update) ng firstNode._NEWLINE_ function insertBeginning(List list, Node newNode) // pagpasok ng nodo sa harap(o bago) ng kasalukuyang unang nodo(node)_NEWLINE_     newNode.next   := list.firstNode_NEWLINE_     list.firstNode\xc2\xa0:= newNode_NEWLINE_Gayundin, meron tayong mga punsiyon para sa pag-alis ng nodo(node) pagkatapos(after) ng isang ibinigay n nodo at para sa pag-aalis ng nodo mula sa una ng listahan. Ang diagrama ay nagpapakita ng una. Upang mahanap at maalis ang isang partikular na node, kailangan alamin ang nakaraang(previous) elemento. _NEWLINE_ function removeAfter(node node) // pag-alis ng nodo pagkatapos(o kasunod) ng nodong ito_NEWLINE_     obsoleteNode\xc2\xa0:= node.next_NEWLINE_     node.next\xc2\xa0:= node.next.next_NEWLINE_     destroy obsoleteNode_NEWLINE_ function removeBeginning(List list) // pag-alis ng unang node_NEWLINE_     obsoleteNode\xc2\xa0:= list.firstNode_NEWLINE_     list.firstNode\xc2\xa0:= list.firstNode.next // itutok sa lagpas ng binurang nodo _NEWLINE_     destroy obsoleteNode_NEWLINE_Pansinin na ang removeBeginning() ay nagtatakda ng list.firstNode sanull kung aalisin ang huling nodo sa listahan.  _NEWLINE_Dahil sa hindi natin makakatahak(iterate) ng pabalik, ang isang mahusay na insertBefore or removeBefore ay hindi posible. _NEWLINE_Ang pagdudugtong ng isang listahang pinagdugtong sa isa pa ay hindi maaaring hindi mahusay na maisasagawa malibang ang reperensiya sa buntos ay pinapanatiling bahagi ng estruktura ng listahan dahil kailangan nating tahakin ang buong listahan upang mahanap ang buntot at pagkatapos ay idudugtong ang ikalawang listahan dito. Kaya kung ang dalawang linyar na listahang pinagdugtong ay may bawat habang , ang pagdudugtong ng listahan ay may asimptotikong kompleksidad ng panahon na . Sa pamilyang Lisp ng mga wikang pangkompyuter, ang pagdudugtong ng listahan ay ibinibigay ng kodang append na metodo(procedure). _NEWLINE_Marami sa mga espesyal na kaso ng mga operasyon ng listahang pinagdugton ay maaaring alisn sa pamamagitan ng pagsasama ng elementong dummy sa harap ng listahan. Ito ay sumisiguro na walang mga espesyal na kaso para sa simula ng listahan at gumagawa sa parehong insertBeginning() at removeBeginning() na hindi na kailangan. Sa kasong ito, ang unang magagamit na data sa listahan ay matatagpuan sa  list.firstNode.next.\n_START_SECTION_\nPang-dobleng listahang pinagdugtong(Doubly linked list)\n_START_PARAGRAPH_\nPang-dobleng listahang pinagdugtong(Doubly linked list) ay binubuo ng hanay ng magkakasunod na pinagdugtong(linked) na nodo(node). Ang bawat nodo ay naglalaman ng dalawang reperensiya na tumutukoy sa nakaraan(previous) at kasunod(next) na nodo ng kasalukuyang nodo. Ang nakaraan at kasunod ng simula at huling mga nodo ay nakatutok sa isang terminador gaya ng nodong sentinel o pantutok na null(null pointer) upang magkapagsagawa ng pagtahak(traversal). Kung isa lang ang nodong sentinel, ang listahan ay sirkular sa pamamagitan ng nodong sentinel. _NEWLINE_record DoublyLinkedNode {_NEWLINE_    prev // reperensiya sa nakaraang nodo_NEWLINE_    next // reperensiya sa kasunod na nodo_NEWLINE_    data // reperensiya sa data o impormasyon\'_NEWLINE_ }_NEWLINE_ record DoublyLinkedList {_NEWLINE_     Node firstNode   // tumututok sa unang nodo ng listahan_NEWLINE_     Node lastNode    // tumututok sa huling nodo ng listahan_NEWLINE_ }\n_START_SECTION_\nPagtahak ng listahan\n_START_PARAGRAPH_\nnode\xc2\xa0:= list.firstNode_NEWLINE_ while node \xe2\x89\xa0 null_NEWLINE_     <do something with node.data>_NEWLINE_     node\xc2\xa0:= node.next_NEWLINE_Backwards_NEWLINE_ node\xc2\xa0:= list.lastNode_NEWLINE_ while node \xe2\x89\xa0 null_NEWLINE_     <do something with node.data>_NEWLINE_     node\xc2\xa0:= node.prev\n_START_SECTION_\nPagpasok ng nodo\n_START_PARAGRAPH_\nfunction insertAfter(List list, Node node, Node newNode)_NEWLINE_     newNode.prev\xc2\xa0:= node_NEWLINE_     newNode.next\xc2\xa0:= node.next_NEWLINE_     if node.next == null_NEWLINE_         list.lastNode\xc2\xa0:= newNode_NEWLINE_     else_NEWLINE_         node.next.prev\xc2\xa0:= newNode_NEWLINE_     node.next\xc2\xa0:= newNode_NEWLINE_ function insertBefore(List list, Node node, Node newNode)_NEWLINE_     newNode.prev\xc2\xa0:= node.prev_NEWLINE_     newNode.next\xc2\xa0:= node_NEWLINE_     if node.prev == null_NEWLINE_         list.firstNode\xc2\xa0:= newNode_NEWLINE_     else_NEWLINE_         node.prev.next\xc2\xa0:= newNode_NEWLINE_     node.prev    := newNode\n_START_SECTION_\nPag-alis ng nodo\n_START_PARAGRAPH_\nfunction remove(List list, Node node)_NEWLINE_   if node.prev == null_NEWLINE_       list.firstNode\xc2\xa0:= node.next_NEWLINE_   else_NEWLINE_       node.prev.next\xc2\xa0:= node.next_NEWLINE_   if node.next == null_NEWLINE_       list.lastNode\xc2\xa0:= node.prev_NEWLINE_   else_NEWLINE_       node.next.prev\xc2\xa0:= node.prev_NEWLINE_   destroy node\n_START_SECTION_\nSirkular na listahang pinagdugtong(Circularly linked list)\n_START_PARAGRAPH_\nSa isang Sirkular na listahang pinagdugtong, ang lahat ng mga nodo(node) ay pinagdudugtong sa isang tuloy tuloy na pag-ikot na hindi gumagamit ng null. Para sa mga listahang may harap(front) at likod(back) gaya ng queue, ang huling nodo sa listahan ay iniimbakan ng isang reperensiya. Ang mga elemento ay maaaring idagdag sa huli ng listahan at alisin sa harapan ng listan sa isang konstanteng panahon. Ang isang sirkular na listahang pinagdugtong ay maaaring pang-isa o pang-doble._NEWLINE_Ang parehong uri ng sirkular na listahang pinagdugtong ay nakikinabang sa kakayahang matahak ang buong listahan na nagsisimula sa anumang ibinigay na nodo. Ito ay pumapayag na maiwasan ang pag-iimbak ng firstNode at lastNode, bagaman kung ang listahan ay walang laman, kailangan ng isang espesyal na representasyon para sa walang laman na listahan gaya ng gaya ng bariabulong lastNode na tumututok sa isang nodo sa listahan o  null kung ito ay walang laman. Ating gagamitin ang gayong lastNode dito.  Ang representasyong ito ay malaking pinapasimple ang pagdadagdag at pag-aalis ng mga nodo sa isang walang lamang listahan ngunit ang mga walang laman na listahan ay isang uri ng espesyal na kaso. _NEWLINE_Ipagpalagay na ang isang someNode ay isang nodo sa isang hindi-walang laman na sirkular na pang-isang listahang pinagdugton, ang kodang ito ay tumatahak sa listahan na nagsisimula sa someNode:_NEWLINE_ function iterate(someNode)_NEWLINE_   if someNode \xe2\x89\xa0 null_NEWLINE_     node\xc2\xa0:= someNode_NEWLINE_     do_NEWLINE_       do something with node.value_NEWLINE_       node\xc2\xa0:= node.next_NEWLINE_     while node \xe2\x89\xa0 someNode_NEWLINE_Pansinin na ang pagsubok na  "while node \xe2\x89\xa0 someNode" ay kailangan nasa dulo ng loop(ikot). Kung ang pagsubok ay inilipat sa simula ng ikot, ang paraan(procedure) ay mabibigo sa tuwing ang listahan ay may isang nodo lamang. _NEWLINE_Ang punsiyong(procedure) ito ay nagpapasok ng nodong "newNode" sa isang sirkular na pang-isang listahang piangdugton pagkatapos ng isang ibinigay na nodo. Kung ang nodo ay null, ito ay nagpapalagay na ang listahan ay walang laman. _NEWLINE_ function insertAfter(Node node, Node newNode)_NEWLINE_     if node = null_NEWLINE_       newNode.next\xc2\xa0:= newNode_NEWLINE_     else_NEWLINE_       newNode.next\xc2\xa0:= node.next_NEWLINE_       node.next\xc2\xa0:= newNode_NEWLINE_Ipagpalagay na ang "L" ay isang bariabulong nakatutok sa huling nodo ng isang sirkular na pang-isang listahang pinagdugtong(o null kung ang listahan ay walang laman). Upang idugtong ang "newNode" sa end ng listahan, maaaring isagawa ang _NEWLINE_ insertAfter(L, newNode)_NEWLINE_ L\xc2\xa0:= newNode_NEWLINE_Upang ipasok ang "newNode" sa beginning(simula) ng listahan, maaaring isagawa ang_NEWLINE_ insertAfter(L, newNode)_NEWLINE_ if L = null_NEWLINE_   L\xc2\xa0:= newNode'