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` sa`null` 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**
      
      node := node.next

*Backwards*
  node := list.lastNode
  **while** node ≠ **null**
      
      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

Kategorya:Estruktura ng datos