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
baguhinPang-isang listahang pinagdugtong(Singly linked list)
baguhinrecord 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)
baguhinPang-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
baguhinForwards
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
baguhinfunction 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
baguhinfunction 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)
baguhinSa 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