ALGORITMA

Bab IV : DOUBLE LINKED LIST

DOUBLE LINKED LIST

Double linked list mempunyai dua pointer yang menunjuk ke node berikutnya dan sebelumnya, disebut juga dengan istilah :

1. next pointer dan

2. previous poniter

satu node untuk double linked list dapat digambarkan seperti :

prinsip kerjanya dalam suatu list dapat dilihat pada skesta dibawah ini :

NIL

NIL

terdapat tiga urutan node di atas, yaitu node(i-1), node(i), dan node (i+1), node tersebut kita umpamakan sebagai posisi dari suatu urutan list yang panjang dari 1 s/d n. Jadi i adalah posisi tertentu yang kita pilih secara acak. Node (i) sebagai patokan . pointer next menunjuk ke node berikutnya, yaitu node(i+1) dan pointer previous menunjuk kesebelumnya, yaitu node (i-1).

Tidak ada lagi node yang ditunjuk pointer previous di head atau node pertama dari double linked list ini. Akan tetapi pointer harus mendapatkan adrress agar definisi kita untuk node tersebut dapat dipenuhi. Kita dapat memberi nilai dengan konstanta NIL di C karena pointer prevoius meunjuk ke node yang tidak ada. Begitu pula dengan tail atau node yang terakhir, pointer next to next di node yang terakhir harus diberi nilai NIL.

Bentuk struktur data double linked list tidak banyak berbeda dengan single liked list, seperti ;

Struct list

{ data mydata

Struct list *next

Struct list*prev

} ; typedef list node

Terdapt deklarasi variable dalam struktur data list yang terdiri atas struktur, tapi terdapat dua cara penulisan yang beda. Pendeklarasian *next dan *prev adalah cara yang biasa, tapi pendeklarasian data mydata agak berbeda yang artinya adalah deklarasi variable yang namanya mydata dari typedata yang namanya adalah data. Jadi data adalah nama alias dari struct data yang telah didefinisikan sebelumnya seperti :

Struct identity

{ char *nama

Char *alamat

Int kodepost

Int telepon

} ; type identity data

Hal ini adalah pendefinisian langsung, yaitu suatu struktur data yang langsung didefinisikan dengan suatu nama, yang kita sebut juga datatype yang didefinisikan sendiri ( self defined data structure ), juga disebut abstract datatype. Perbedaan yang dijumpai double linked list sekarang hanya penambahan satu pointer variable *prev untuk menunjuk ke node yang sebelumnya, yaitu pada perintah : struct lis *prev. Gunakan algorithma yang sama dengan single linked list untuk membuat program pengolahan double linked list.

Algorithma :

Mendefinisikan struktur record untuk list dengan

Dua pointer *next dan *prev

Mendeklarasi head of list

Mendeklarasi tail of list

Head dan tail diinisialisasi dengan NIL;

Proses pengulangan

{ input data hingga benar;

Mencetak status head;

Menentukan node diletakkan di awal, akhir atau dalam list

Menampilkan hasil list yang diproses

}

Terdapat 3 fungsi dari algorithma diatas sebagai inti dari program kita yaitu :

Sethead_d, menyisipkan node di awal list

Settail_d, menyisipkan node di akhir list

Insert_d, menyisipkan node di dalam list

Bedakan penamaan dengan penambahan akhiran “_d” untuk menyatakan bahwa fungsi ini menggunakan struktur data double linked list.

· FUNGSI SETHEAD_D()

Fungsi sethead_d() adalah membuat double linked list baru jika belum ada linked list sama sekali dengan menggunakan data yang baru atau menyisipkan data yang baru ke awal list yang telah ada.

Kasus 1:

Buat double linked list yang baru seperti skesta di bawah ini :

Node sebleum mempunyai nilai poiter

Node setelah mendapatkan nilai poiter

Sebuah double linked list , minimal harus mempunyai dua node pembantu, yaitu head dan tail sebagai identifikasi bahwa list itu ada awal dan akhirnya. Double linked list yang baru mempunyai satu node, artinya data head dan data tail adalah sama. Periksa head dari list untuk mengetahui bahwa pada double linked list belum ada node. Nilai head = NIL, artinya list masih kosong. NIL adalah konstanta yang dipakai pada C untuk menyatakan bahwa recordnya maih kosong.

Kasus 2 :

Menyisipkan node di double linked list yang sudah ada, dapat digambarkan di skesta di bawah ini :

Menambah node act dan akan dihubungkan ke head

Pointer dimanipulasi

Actànext = head

Actà prev = NIL

Headàprev = act

Node setelah pointerdimanipulasi dan head = act

Head = act

Algortihma sethead_d():

Mendeklarasi struktur record list

Deklarasi variable namenode

Deklarasi variable untuk node dengan actualnode.

Mengalokasi memori untuk record list

Cek apakah sudah ada list ?

Jika belum ada, maka initialisasi head dengan ;

- Namehead = namenode.

- Pointer next head = NIL

- Pointer prev head = NIL

- Tail = head

Jika sudah ada, maka

- Pointer next node actual = head

- Pointer prev node actual = NIL

- Pointer prev = node actual

- Namaactualnode = node actual

- Head = actualnode

Fungsi sethead dalam C dapat ditulis seperti :

Sethead(char*namenode)

{ mylist *act_node;

Act_node=(mylist*)malloc ( sizeof(structlist));

If( act_node))

{ printf(“Allocation error\n”);

Exit(1);

}

If (head = = NIL)

{ head = act_node;

Strcpy(head->name,namenode)

Head->next = NIL;

Head->prev = NIL;

Tail = head;

Return

}

Else

{ act_node->next = head;

Act_node->prev = NIL

Head->prev = act_node

Strcpy(act_node->name, namenode

Head = act_node

}

}

Sebelum kita mulai dengan aksi, langkah pertama yang perlu dilakukan saat manipulasi list adalah mencek status list tersebut.

Gunakan perintah if(head=NIL) untuk mencetak apakah sudah ada list yang di create, kalau belum ada list, head !=NIL, maka aksi yang dilakukan adalah membuat list yang baru dengan data yang baru. Dimasukan dan simpan di act_node. Head dan tail dideklarasi sama dengan act_node. Kita menginstruksikan agar head mendapat nilai dari node act_node di dalam perintah head=act_node

Head adalah variable yang dideklarasi secara global . yaitu dideklarasikan di awal program dan diluar fungsi-fungsi. Act_node adalah variable lokal yang di definisikan di dalam fungsi. Lokal variable masa berlakunya selama fungsi yang dipanggil aktif dan akan hilang sendirinya kalau fungsi tersebut sudah selesai aksinya.

Langkah selanjutnya, initialisasi data item yang terdapat didalam head. Head mendapatkan nama yaitu dengan meng-copy data yang baru di input dari variable “namenode” dengan perintah ;

Strcpy(headàname, namenode)

Selanjutnya pointer next dan prev diinitialisasi dengan NIL, dengan perintah headànext = NIL, dan headàprev = NIL, sampai tahap ini kita sudah mempunyai satu node untuk list, yang lengkap dengan datanya dan node ini adalah head. Karena baru mempunyai satu node head, head adalah sama dengan node tail. Langkah selanjutnya menginitialisasi tail dengan head dengan perintah tail=head.

Alternatif lain, jika sudah ada list , maka sisipkan node yang baru tersebut di awal list, artinya data yang baru kita masukkan akan dijadikan head dari list. Langkah pertama yang dilakukan dalam membuat node menjadi head adalah menentukan pointer next supaya menunjuk ke head yang ada sekarang dengan perintah act_nodeànext = head; pointer prev harus diinitialisasi dengan address NIL karena menjadi head lakukan dengan perintah act_node à = NIL

Head dari list sekarang menjadi node di posisi ke 2 dan pointer prev untuk head sekarang harus menunjuk ke act_node, dengan perintah head_prev = act_node. Setelah kita mengubah posisi pointer yang terkait berarti tugas kita sudah hampir selesai. Sekarang urutan dari listnya sudah benar, tentukan head yang baru dengan perintah head = act_node.

· FUNGSI SETAIL_D()

Fungsi settail_d adalah menyisipkan data yang baru ke akhir list yang telah ada, seperti dibawah ini ;

Pointer dimanipulasi

Tailànext = act

Actànext = NIL

Actàprev = tail

Node setelah pointer dimanipulasi dan tail = act

Tail = act

Langkah awal yang dilakukan adalah pointer tail “tail->next” yang sebelumnya mempunyai nilai NIL. mendapatkan nilai adrress dari record yang baru yaitu node dengan nama act. Karena kita akan menjadikan node act menjadi tail, maka pointernya act -> next harus diberi nilai NIL dan menunjuk ke node kosong, sedangkan pointer act->prev menunjuk ke tail

Langkah terakhir adalah mendeklarasikan node act menjadi tail.

Perhatikan fungsi sttail ditulis dengan C ;

Settail(char*namenode)

{ mylist *act_node;

Act_node =(mylist*)malloc(sizeof(struclist));

If(!(act_node))

{ printf(“Allocation error\n”);

Exit (1);

}

Tail ->next = act_node

Strcpy(act_node->name, namenode);

Act_node->next = NIL;

Act->prev = tail;/**/

Tail = act_node

}

Fungsi settail di atas jika dibanding dengan fungsi sethead, keduanya mempunyai teknik yang sama, hanya berlainan arahnya. Kita temukan perintah tailànext = act_node didalam fungsi settail yang artinya pointer dari node tail mendpat address yang menunjuk ke node yang baru ditambahkan yaitu act_node. Perintah strcpy(act_node àname namenode) artinya menginitialisasi nama node yang baru dengan nama yang baru dimasukkan. Perintah act_node à next =NIL artinya menginitialisasi pointer next dari node yang baru dengan address NIL. hal ini menginitialisasi pointer prev dari node yang baru dengan tail. Hal itu berarti menunjuk ke node tail yang sekarang menjadi urutan kedua dan akhir.

Terakhir ,perintah tail = act_node mendeklarasi kan bahwa yang menjadi node tail sekarang adalah node yang baru, yaitu act_node.

· FUNGSI INSERT_D()

Fungsi insert_d adalah menyisipkan node yang baru di antara 2 node yang telah ada di suatu double linked list. Mirip dengan tehnik yang pakai di single linked list. Hal yang perlu diperhatikan adalah sekarang kita harus memperhatikan 2 pointer . prinsip kerjanya dapat digambarkan seperti di bawah ini ;

node act akan disisipkan dalam list

Memanipulasi pointer dengan node sebelumnya

Act->prev = temp

Temp->next = act

Memanipulasi pointer dengan node berikutnya

Act->next = tempnext

Tempnext->prev = act

Setelah pointer dimanipulasi

Fungsi insertdapat ditulis dengan C

Settail(char*namenode)

{ mylist *act_ode;

Mylist *tempnode;

Act_node = (mylist *)malloc(sizeof(structlist));

If(!(act_node))

{ printf(“Allocation error\n”);

Exit(1);

}

Tempnode = head;

While (tempnode)

{ if(strcmp(tempnodeànextàname,name)>0)

{ act_node->next = tempnode->next;

Act_node->prev = tempnode

Tempnext->next = act_node;

Tempnext->prev = act_node

Strcpy(act_node->name, namenode);

Return

}

Tempnode = tempnode->next

}

}

Cara pengaturan penyisipan node pada program diatas menggunakan perintah berulang, yaitu while untuk mencari posisi node yang tepat posisi bergeser dari head terus sampai node yang dicari ketemu. Node yang ketemu adalah tempnode. Perintah tempnode = tempnodeànext mengeser dari posisi tempnode ke posisi yang berikutnya yaitu tempnode->next.

Lakukan aksi berikut untuk memanipulasi arah pointer

Perintah act_node à next = tempnode ànext artinya pointer next actnode ditunjuk ke tempnode yang berikutnya. Perintah act_nodeà next = tempnode artinya pointer prev act_node nord yang kanan disisipkan ditujukan ke arah tempnode. Perintah tempnodeànext = act_node artinya mengarahkan poniter tempnode ke node yang akan disisipkan, act_node.

Terakhir perintah tempnextàprev = act_node artinya mengarahkan pointer prev dari tempnodenext, yaitu tempnextà prev ke node yang akan disisipkan.

· DELETE DOUBLE LINKED LIST

Delete double linked list maksudnya menghapus suatu node dengan dua pointer, yaitu next dan prev yang terdapat di dalam double linked list . kita harus menentukan posisi node yang akan dihapus sebelum melakukan aksi ini.

Tehnik delete dengan double linked list lebih mudah dibandingkan dengan single linked list. Kita dapat menelusuri list dengan arah ke depan dan ke belakang menggunakan next dan prev, sedangkan pada single linked list hanya dapat ke depan saja. Kemungkinan posisi node yang akan kita temukan pada suatu list adalah :

1. Delete header

2. Delete tail

3. Delete inlist

Menentukan posisi node dengan pencarian (searcing) dilakukan mulai dari awal list (head) sampai akhir list (tail)

Tehnik delete dapat dibedakan dalam 3 kasus yaitu :

1. Delete header

2. Delete tail

3. Delete inlist

· DELETE HEADER

Delete header adalah menghapus salah satu node yang berfungsi sebagai header dari dalam suatu double linked list.

Sebelum nodeyang akan dihapus adalah node A

Tahap awal , memutuskan hubungan pointer pointer

Node B dijadikan head dan node A dihapus

Perhatikan saat menghapus (delete) header dari suatu double linked list adalah suatu list harus mempunyai header adalah syarat mutlak. Kita harus menentukan satu node pengganti yang dideklarasi menjadi pengganti header kalau headernya akan kita hapus. Cara yang paling mudah adalah dengan memilih node yang ditunjuk oleh header(head->next) sebagai header pengganti dan dilakukan dengan perintah

Head = head ànext

Sekarang head baru adalah node-> prev yang menunjuk ke head lama, artinya pointer previous harus diinitialisasi dengn NIL, yaitu dengan perintah

Head à prev = NIL;

Dari skesta diatas,node A dijadikan header, yaitu pada proses tahap pertama artinya :

Head ànext adalah node A

Jadi, kita menentukan bahwa node A dijadikan sebagai header dengan deklarasi head = head->next.

Sebelumnya, pointer previous untuk node A harus diberi nilai NIL dengan perintah

Aànext = NIL

· DELETE TAIL

Delete tail adalah menghapus salah satu node yang berfungsi sebagai tail dari dalam suatu double linked list.

Node E yang akan dihapus adalahTail

Tahap awal ,memutuskan hubungan pointer pointer antara tail dengan node D

Node d dijadikan tail dan node E dihapus

Paling mudah adalah dengan memilih node yang menunjuk ke tail (node->next = tail ) sebagai tail pengganti dan pointernya diinitialisasi menjadi NIL.

Node à next = NIL

Dan node tersebut dijadikan tail

Tail = node;

Sketsa diatas dapat dilakukan untuk

D à next = NIL

Dan untuk menentukan tail

Tail D

· DELETE INLIST

Delete inlist adalah menghapus salah satu node yang berfungsi dari dalam suatu double linked list yang bukan serbagai head atau tail

Node B adalah yang akan dihapus

Tahap awal, pointer A diarahkan ke C dan sebaliknya

A-> next->next

C->prev->prev

Setelah Node B dihapus

Cara yang paling mudah untuk menghapus node dari dalam double linked list adalah memutuskan hubungan pointernya saja dan kita harus memperhatikan dua pointer, yaitu next dan prev. Lakukan dengan membuat next pointer dari suatu node yang menunjuk ke node yang akan dihapus menjadi menunjuk ke node yang akan dihapus menjadi menunjuk ke node yang berikutnya dari node yang akan dihapus itu.

Dengan perintah ;

Node à next = node à next à next

Kita mendekteksi pointer untuk node yang berikutnya menjadi pointer node satu sebelumnya. Prev dapay kita lakukan dengan teknik yang sama seperti :

Node à prev = node à prev à prev

Node yang dihapus adalah B. Kita harus memperhatikan dua pointe, yaitu next dan prev.

Proses manipulasi pointer NEXT

A à next adalah B

B à next adalah C

Dan A à next à next adalah C

Jadi B à next sama dengan A à next à next

Yang kita inginkan adalah menjadikan pointer A à next menjadi B à next , kita tidak dapat melakukan perintah A à next = B à next, karena node yang kita baca kita berada di posisi A dan node B velum dikenal oleh sistem.

Jadi, triknya dapat kita lakukan dengan perintah

A à next = Aà nextà next

Artinya, kita mengubah arah pointer node A à next dari B ke C

Proses Manipulasi pointer PREV

Tentukan pointer prev dan node C. Ingat,posisi kita sekarang adalah pada node A., tetapi kita inginkan memanipulasi pointer prev dari node C. Lakukan perintah berikut ;

Node à prev = node à prev à prev

Nilai A à next adalah C, jadi dapat menggunakan varaible A à next untuk menggantian C.

Perintah manipulasi previous pointer node à prev = node à prev à prev dapat memanfaatkan kecanggihan struktur data rekursiv dengan keampuhan pointernya dengan menggunakan perintah ;

A à next à prev = A à next à prev à prev

Pada umumnya , fungsi delete ditulis dalam satu fungsi delete yang dapat memperhatikan ke 3 kasus tersebut

Algoritma delete double linked list ;

Mendeklarasikan variable pembantu struktur record node yang akan dihapus dengan nama delnode.

Menginitialisasi delnode dengan node yang akan dihapus.

Cek apakah node yang akan dihapus adalah header ?

Jika header maka :

Cek lagi apakah masih berupa list dengan node tunggal ( header-> next ==NIL)?

Jika benar, maka return header.

Jika salah,maka ;

Menentukan header baru dengan node yang berikutnya dengan return header.

Mencari node -> next sampai ketemu.

Cek apakah node -> next adalah tail?

Jika node adalah tail, maka:

Node pointer yang menunjuk ke tail dinitialisasi dengan NIL

Node tersebut dijadikan tail.

Jika bukan tail, maka mengubah arah pointer ke yang berikutnya.

Hapus data node dari record.

Fungsi delete secara umum dapat kita tulis dengan C seperti di bawah ini :

List*delete(list*node)

{list*del_node /*Deklarasi node akan dihapus */

Del_node=node; /*initialisasi dengan yang dibaca */

If(node== header) /*Node adalah header */

{ if (header->next ==NIL) /*Node tunggal */

Return header;

Else /*Node jamak */

{ header ->next = node->next /*menentukan pointer baru*/

Return header;

}

}

Else /*Node bukan header */

{ while (node=node ->next) /*Mencari Node */

{ node = node -> next; /*ke posisi berikutnya */

If node (node -> next )

{ node -> next-prev = node-prev;}

If (node->next=tail) /*cek node dan initialisasi kalau tail */

{ node->next = NIL

Tail = node;

Return tail ;

}

Node->next = node ->next->next-; /*menentukan next pointer */

Free(del_node) /*menghapus dari record */

}

Return header;

}