Listahang pinagdugtong

Sa 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.

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.

Mga operasyon

Pang-isang listahang pinagdugtong(Singly linked list)

record Node {
    data; // ang data(impormasyon) na iniimbak sa nodo
    Node next // Ang reperensiya sa kasunod na nodo, null para sa huling nodo
 }

 record List {
     Node firstNode // tumutukoy sa unang nodo ng listahan; null para sa walang laman na listahan
 }

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:

 node := list.firstNode
 while node not null
     (do something with node.data)
     node := node.next

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.

 function insertAfter(Node node, Node newNode) // pagpapasok ng newNode pagkatapos ng node(nodo) 
     newNode.next := node.next
     node.next    := newNode

Ang pagpasok ng nodo sa simula ng listahan ay nangangailangan ng hiwalay na punsiyon. Ito ay nangangailangan ng pagbabago(update) ng firstNode.

 function insertBeginning(List list, Node newNode) // pagpasok ng nodo sa harap(o bago) ng kasalukuyang unang nodo(node)
     newNode.next   := list.firstNode
     list.firstNode := newNode

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.

 function removeAfter(node node) // pag-alis ng nodo pagkatapos(o kasunod) ng nodong ito
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode

 function removeBeginning(List list) // pag-alis ng unang node
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next // itutok sa lagpas ng binurang nodo 
     destroy obsoleteNode

Pansinin na ang removeBeginning() ay nagtatakda ng list.firstNode sanull kung aalisin ang huling nodo sa listahan.

Dahil sa hindi natin makakatahak(iterate) ng pabalik, ang isang mahusay na insertBefore or removeBefore ay hindi posible.

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 $n$, ang pagdudugtong ng listahan ay may asimptotikong kompleksidad ng panahon na $O(n)$. Sa pamilyang Lisp ng mga wikang pangkompyuter, ang pagdudugtong ng listahan ay ibinibigay ng kodang append na metodo(procedure).

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.

Pang-dobleng listahang pinagdugtong(Doubly linked list)

Pang-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.

Ang isang pang-dobleng listahang pinagdugtong na ang mga nodo ay naglalaman ng tatlong field: isang halagang intedyer, kaugnayan(link) sa sumusunod na nodo at kaugnayan(link) sa nakaraang nodo.

record DoublyLinkedNode {
    prev // reperensiya sa nakaraang nodo
    next // reperensiya sa kasunod na nodo
    data // reperensiya sa data o impormasyon'
 }

 record DoublyLinkedList {
     Node firstNode   // tumututok sa unang nodo ng listahan
     Node lastNode    // tumututok sa huling nodo ng listahan
 }

Pagtahak ng listahan

Forwards

 node := list.firstNode
 while node ≠ null
     <do something with node.data>
     node := node.next

Backwards

 node := list.lastNode
 while node ≠ null
     <do something with node.data>
     node := node.prev

Pagpasok ng nodo

 function insertAfter(List list, Node node, Node newNode)
     newNode.prev := node
     newNode.next := node.next
     if node.next == null
         list.lastNode := newNode
     else
         node.next.prev := newNode
     node.next := newNode

 function insertBefore(List list, Node node, Node newNode)
     newNode.prev := node.prev
     newNode.next := node
     if node.prev == null
         list.firstNode := newNode
     else
         node.prev.next := newNode
     node.prev    := newNode

Pag-alis ng nodo

 function remove(List list, Node node)
   if node.prev == null
       list.firstNode := node.next
   else
       node.prev.next := node.next
   if node.next == null
       list.lastNode := node.prev
   else
       node.next.prev := node.prev
   destroy node

Sirkular na listahang pinagdugtong(Circularly linked list)

Sa 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.

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.

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:

 function iterate(someNode)
   if someNode ≠ null
     node := someNode
     do
       do something with node.value
       node := node.next
     while node ≠ someNode

Pansinin na ang pagsubok na "while node ≠ 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.

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.

 function insertAfter(Node node, Node newNode)
     if node = null
       newNode.next := newNode
     else
       newNode.next := node.next
       node.next := newNode

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

 insertAfter(L, newNode)
 L := newNode

Upang ipasok ang "newNode" sa beginning(simula) ng listahan, maaaring isagawa ang

 insertAfter(L, newNode)
 if L = null
   L := newNode