Doubly Linked List

Struktur Doubly Linked List

Ø  Node-node doubly linked list saling berkait melalui pointer. Bagian left sebuah node menunjuk node selanjutnya. Bagian right sebuah node menunjuk node sesudahnya.

Ø  pHead : pointer yang menunjuk node pertama

Ø  Setiap node terdiri atas

Ø  Left, yaitu pointer yang menunjuk ke node sebelumnya pada list

Ø  Data

Ø  Left, yaitu pointer yang menunjuk ke node sebelumnya pada list

Ø  Left node pertama bernilai NULL

Ø  Right node terakhir bernilai NULL

Struktur Sebuah Node Doubly Linked List

Ø  Setiap node terdiri atas

Ø  Left, yaitu pointer yang menunjuk ke node sebelumnya pada list

Ø  Data

Ø  Left, yaitu pointer yang menunjuk ke node sebelumnya pada list

Double Linked List (DLL) adalah suatu cara pengolahan data yang bekerja dengan record dalam jumlah besar, sehingga membutuhkan alokasi memori dinamis yang besar pula. DLL biasanya digunakan pada saat alokasi memori konvensional tidak lagi bisa diandalkan. Sedangkan bekerja dengan data yang besar tidak dapat dihindari lagi, karena tidak jarang pula, data besar tersebut memiliki hubungan yang erat.


Di dalam DLL tidak hanya sekadar menampilkan setiap record-nya, melainkan dapat pula menambahkan record, menghapus beberapa record sesuai keinginan pengguna, sampai mengurutkan record. Kondisi tersebut memungkinkan dimilikinya satu rantai data yang panjang dan saling berhubungan.
Pada Double Linked List, setiap node memiliki dua buah pointer ke sebelah kiri (prev) dan ke sebelah kanan (next). Gambar 1 memperlihatkan sebuah node dari Double Linked List.

Bertambah lagi komponen yang akan digunakan. Apabila dalam Single Linked List hanya memiliki head, curr dan node, maka untuk Double Linked List, ada satu penunjuk yang berfungsi sebagai akhir dari list: tail. Bagian kiri dari head akan menunjuk ke NULL. Demikian pula dengan bagian kanan dari tail. Setiap node saling terhubung dengan pointer kanan dan kiri. Gambar 2 memperlihatkan contoh Double Linked List.

struct node {
 

   //bagian data

    tipedata data 1;

    tipedata data 2;

    …

tipedata data n;

    //pointer ke node sebelum dan sesudahnya

    struct node *left;

    struct node *right;

};

typedef struct node node;

Sebelum membuat doubly linked list, perlu dideklarasikan dan diinisialisasikan pHead, yaitu pointer yang menunjuk node pertama dari double linked list

                          node *pHead = NULL;

Operasi Doubly Linked List 

1. Menambah sebuah node pada doubly linked list.
2. Menghapus sebuah node dari doubly linked list.
3. Mencari node pada doubly linked list.
4. List tranversal

Menambah Node Ke Doubly Linked List 

Tahap – tahap menambah node pada double linked list: 

•          Buat node baru yang akan ditambahkan.

•          Tentukan node sebelum tempat penyisipan (pCur).

•          Set left node baru menunjuk predencecor dan right node baru menunjuk succesor.

•          Set right predencecor dan left succesor menunjuk node baru .  

pCur dapat memiliki dua keadaan:

•          it can contain the address of a node (i.e. you are adding somewhere after the first node – in the middle or at the end)

•          it can be NULL (i.e. you are adding either to an empty list or at the beginning of the list)

•          pNew = (struct node *) malloc(sizeof(struct dllnode));  

•          pNew -> data = 84; 

•          pNew -> left = pCur;

•          pNew -> right = pCur -> right; 

•          pCur -> right  = pNew;  

Kode Untuk Menambah Node Ke Doubly-Linked List

//insert a node into a linked list

    struct node *pNew;

    pNew = (struct node *)  malloc(sizeof(struct node));

    pNew -> data = item;

    if (pCur == NULL){

         //add before first logical node or to an empty list

                   pNew -> left = pHead;

                   pNew -> right = pHead;

          pHead = pNew;

    }

    else {

                      if (pCur -> right == NULL) {

              //add at the end

pNew -> left = pCur;

pNew -> right = pCur -> right; 

pCur -> right  = pNew;

}

                      else {  //add in the middle

                                    pNew -> left = pCur;

                                pNew -> right = pCur -> right;

                                pCur -> right -> left = pNew;  

                                pCur -> right = pNew;

                     }

        }

   }

Menghapus Node Dari Doubly Linked List

•          Setiap node pada doubly linked list dapat dihapus. Jika doubly linked list tidak memiliki node lagi, maka pHead bernilai NULL .

•          Untuk menghapus node baru :

–        Cari node yang akan dihapus (pCur).

–        Set right dari predencecor pCur agar menunjuk succesor pCur

–        Set left dari succesor pCur agar menunjuk predencecor pCur

–        Hapus node yang ditunjuk pCurmenggunakan free function.

Kode Untuk Menghapus Sebuah Node Pada Doubly Linked List.

//delete a node from a linked list

if (pCur -> left == NULL){

         //deletion is on the first node of the list

                   pHead = pCur -> right;

                   pCur -> right -> left = NULL;

{

else {

         //deleting a node other than the first node of the list

        pCur -> left -> right = pCur -> right;

                  pCur -> right -> left = pCur -> left;

}

free(pCur).

Pencarian Data Pada Doubly-Linked List

•          Proses tambah node dan hapus node membutuhkan pencarian node tempat disisipkan dan yang akan dihapus.

//search the nodes in a linked list

pCur = pHead;

//search until the target value is found or the end of the list is reached

while (pCur != NULL && pCur -> data != target) {

      pCur = pCur -> right;

}

//determine if the target is found or ran off the end of the list

if (pCur != NULL)

   found = 1;

else

   found = 0;

  
ABSTRAKSI TIPE DATA DOUBLY LINKED LIST
Abstraksi tipe data Double Linked List sedikit berbeda dengan Single Linked List, yaitu tinggal menambahkan pointer prev dan harus diawali dengan pembuatan struct tnode.

Kemudian, mendeklarasikan beberapa node yang akan digunakan sebagai head, tail, node aktif (curr) dan node sementara (node) seperti berikut:

Sama seperti pada pembuatan Single Linked List, dalam pembuatan Double Linked List ini, akan membuat sebuah perulangan sebanyak 5 kali untuk mengisikan nilai 0 sampai 4 ke dalam field x untuk masing-masing node.


Secara umum, kode yang dibuat hampir sama dengan pembuatan Single Linked List. Hanya bedanya, pada Double Linked List, pointer kiri dan kanan dihubungkan dengan suatu node.

Pertama-tama, tentunya perlu diuji apakah head bernilai NULL yang artinya belum ada satu node pun yang tercipta. Apabila demikian, maka node yang dibuat akan menjadi head. Node aktif (curr) pun diset sesuai node yang dibuat. Dan sebagai konsekuensi dari Double Linked List, maka diatur pointer prev pada head menunjuk ke NULL.

Untuk menguji keberhasilan Double Linked List, awal list sampai akhir list akan dicetak dengan deklarasi:

Dan karena apa yang dibentuk adalah Double Linked List, maka juga mencetak dari tail sampai head, dengan deklarasi:

Untuk membebaskan memori teralokasi, dilakukan dengan pemanggilan fungsi free(). Kode selengkapnya:

Operasi pada linked list tidak hanya pembuatan dan pencetakan. Suatu saat, mungkin perlu untuk menghapus node yang terletak di tengah-tengah list. Atau bahkan mungkin perlu menyelipkan node di tengah-tengah node.

 MACAM-MACAM DOUBLE LINKED LIST

1. DOUBLE LINKED LIST CIRCULAR (DLLC)
a. Definisi
Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Circular pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

b. Bentuk Node DLLC
Pengertian:
Double : field pointer-nya terdiri dari dua buah dan dua arah, yaitu prev dan next.
Linked List : node-node tersebut saling terhubung satu sama lain.
Circular : pointer next dan prev-nya menunjuk ke dirinya sendiri.

Ilustrasi Double Linked List Circular
Ø Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya.
Ø Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri.
Ø Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

c. Pembuatan Double Linked List Circular
Deklarasi node, dibuat dari struct berikut ini:
Penjelasan:
Ø Pembuatan struct bernama TNode yang berisi 3 field, yaitu field data bertipe integer dan field next dan prev yang bertipe pointer dari Tnode.
Ø Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

Pembuatan Node Baru:
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, pointer prev dan next menunju ke dirinya sendiri.

d. Double Linked List Circular Menggunakan Head
§ Menggunakan 1 pointer head.
§ Head selalu menunjuk node pertama.

Deklarasi Pointer Head:
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:

e. Penambahan Data
Penambahan Data di Depan:
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head-nya.

Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Dibutuhkan pointer bantu yang digunakan untuk prev) yang akan digunakan untuk mengikat®menunjuk node terakhir (head list dengan node terdepan.


SUMBER : PRAKTIKUM STRUKTUR DATA



Free Template Blogger collection template Hot Deals SEO