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 , 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). 

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. 

<center><small>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.</small></center>

 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

Estruktura ng datos