[Praktikum Algoritma dan Struktur Data] Modul II - Double Linked List

MODUL  II

DOUBLE LINKED LIST

 

2.1.  TUJUAN

1.    Mahasiswa memahami dan dapat mengimplementasikan double linked list dalam program.

2.    Mahasiswa dapat membuat dan menggunakan berbagai operasi-operasi yang terdapat pada double linked list.

2.2.  DASAR TEORI

1.    Double Linked List

Double linked list adalah list biasa, hanya saja setiap elemen list-nya memuat 2 macam pointer, yang selalu menunjuk ke elemen sebelumnya dan yang lainnya ke elemen sesudahnya.

Gambar 2.1 Double linked list

Ada dua macam double linked list, yaitu :

a.    Double Linked List Circular

Circular artinya pointer next dan prev-nya menunjuk ke dirinya sendiri. Jadi, 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 1 field yang berisi data dengan pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

Deklarasi node :

Typedef struct Tnode {
  int data;
  Tnode *next;
  Tnode *prev;
};

b.    Double Linked List Non Cilcular

Non circular artinya pointer preview dan next-nya akan menunjuk pada NULL. Jadi double linked list non circular adalah double linked list yang memiliki 2 buah pointer yaitu pointer next dan prev. Pointer next menunjuk pada node setelahnya dan pointer preview menunjuk pada node sebelumnya.

Deklarasi node :

typedef struct Tnode {
  int data;
  Tnode *next;
  Tnode *prev;
};

2.    Operasi – Operasi yang Ada Pada Double Linked List

a.    Penciptaan

Penciptaan adalah memberikan nilai NULL terhadap variabel pointer awal dan variabel pointer akhir.

b.    Penyisipan

·      Penyisipan di depan atau awal

Operasi ini berguna untuk menambah satu simpul baru diposisi pertama. Langkah pertama untuk pembuatan data adalah membuat simpul baru dan mengisinya dengan data pada field  infonya. Pointer yang menunjuk pada simpul tersebut dipanggil dengan nama baru.

·      Penyisipan ditengah

Operasi penyisipan data  di tengah linked list adalah  suatu  operasi menambah data diposisi tertentu didalam linked list. Karena double linked list memiliki dua pointer sambungan, maka penyisipan bisa dilakukan sebelum data tertentu atau sesudah data tertentu, berbeda dengan single linked list yang hanya memiliki satu pointer sambungan yaitu sambungan kanan (next).

·      Penyisipan di belakang

Operasi ini berguna untuk menambahkan elemen baru di posisi akhir. Langkah pertama untuk penambahan data adalah pembuatan elemen baru dan pengisian nilai infonya. Pointer yang menunjuk ke data tersebut dipanggil dengan nama baru. Kondisi disetelah ada pembuatan elemen baru tersebut.

c.    Penghapusan

·      Penghapusan di awal, operasi iniberguna untuk menghapus data pada posisi pertama

·      Penghapusan di tengah, untuk melakukan proses penghapusan di tengah linked list.

·      Penghapusan di akhir, operasi ini berguna untuk menghapus data pada posisi terakhir.

3.    Algoritma Program dengan Double Linked List

a.    Add front :

1.    Membuat sebuah node baru berdata nilai.

2.    Jika head dan tail sama dengan NULL, maka node baru dijadikan head dan tail.

3.    Jika tidak, pointer next node baru tersebut ditujukan pada head, pointer before head dihubungkan dengan node baru dan kemudian head dipindahkan ke node baru.

4.    Setiap data ditambah, ukuran linked list juga ditambah, dan jika data dikurang, ukuran linked list dikurang.

b.    Add back :

1.    Membuat sebuah node baru berdata nilai.

2.    Menghubungkan pointer next tail dengan node baru, lalu pointer before node baru dengan tail, dan kemudian tail dipindahkan ke node baru.

c.    Insert after :

1.    Membuat sebuah node baru.

2.    Memeriksa data-data pada linked list sampai ketemu node berdata nilai dengan sebuah node sementara yang dihubungkan dengan head.

3.    Jika data sudah ditemukan, menyisipkan node baru ke bagian setelah data yang dicari, dengan cara menghubungkan pointer next node baru dengan pointer next node sementara.

4.    Mengarahkan pointer next node sementara ke node baru.

5.    Mengarahkan pointer before node baru ke node sementara.

d.   Insert before :

1.    Membuat sebuah node baru.

2.    Periksa data-data pada linked list sampai ketemu node berdata nilai dengan sebuah node sementara yang dihubungkan dengan tail.

3.    Jika data sudah ditemukan, hubungkan pointer before node baru dengan pointer before node sementara, mengarahkan pointer before node sementara ke node baru, mengarahkan pointer next node baru ke node sementara.

e.    Delete front :

1.    Menggunakan sebuah node sementara dan ditujukan pada head.

2.    Menggeser posisi head ke kanan.

3.    Memutuskan pointer next node sementara tadi dengan linked list, memutuskan pointer before head, dan menghapus node sementara.

f.     Delete back :

1.    Menggunakan sebuah node sementara dan ditujukan pada tail.

2.    Menggeser tail ke kiri.

3.    Memutuskan pointer next tail dan pointer before node sementara, lalu menghapus node sementara yang telah terpisah dari linked list.

g.    Delete all :

1.    Menghapus node dalam linked list satu persatu dari depan.

2.    Menggunakan sebuah node sementara dan ditujukan pada head.

3.    Menggeser posisi head ke kanan.

4.    Memutuskan pointer next node sementara tadi dengan linked list, memutuskan pointer before head, dan menghapus node sementara.

5.    Kembali ke langkah kedua hingga hanya tersisa head.

6.    Head terakhir kemudian dihapus sehingga data menjadi kosong.

h.    Cetak :

1.    Mengakses head dengan node sementara.

2.    Memeriksa kondisi, node sementara tidak sama dengan NULL atau tidak.

3.    Jika tidak sama, mencetak node sementara dan memindahkan node sementara tersebut ke node selanjutnya.

4.    Jika sama dengan NULL, berhenti mencetak.

 

2.3.  PERMASALAHAN

1.    Membuat program dengan double linked list berisi operasi-operasi berikut:

a.    Add front dan add back

b.    Insert after atau insert back

c.    Delete front dan delete back

d.   Delete all

2.4.  HASIL DAN PEMBAHASAN

a.     Source Code

#include <iostream> #include <stdlib.h> using namespace std;   class DLL {    private:       struct node    {       int data;       node *next;       node *before;    };    node *head,*tail;    int size;    public:    void dll()    { head=tail=NULL;       size=0;       };    void insertbefore(int a, int b)    {      node *tmp1,*tmp2;    tmp1=tmp2=head;      while(tmp1->data!=a)       {       tmp2=tmp1;       tmp1=tmp1->next;       }       node *tmp=new node;       tmp->data=b;       tmp->next=tmp2->next;       tmp->next->before=tmp;       tmp2->next=tmp;       tmp->before=tmp2;       size++;       cout<<" ";       }       void removeBack()       {       node *tmp;       tmp=tail;       tail=tail->before;       tail->next=tmp->before=NULL;       delete tmp;       size--;       cout<<" ";       }       void removeAll()       {       node *tmp;       int x=size;       for(int n=0;n<x;n++)       {                   if(size==1)             {                   tmp=head;                   head=tail=NULL;                   delete tmp;                   size--;             }             else             {             tmp=head;             head=head->next;             head->before=NULL;             tmp->next=NULL;             delete tmp;             size--;             }       } }       void insertAfter(int x,int nilai)       {                         node *tmp, *after;             tmp=new node;             tmp->data=nilai;             after= head;       while(after->data!=x)       {                   after=after->next;       }             tmp->next=after->next;             after->next->before=tmp;             tmp->before=after;             after->next=tmp;             size++;       }       void addBack (int nilai)       {                   node *tmp;             tmp=new node;             tmp->data=nilai;          tmp->next=NULL;             tmp->before=tail;             tail->next=tmp;             tail=tmp;             size++;          cout<<" ";       }       void addFront(int nilai)    {             node *tmp;          tmp=new node;             tmp->data=nilai;             if(size==0)             {                   head=tail=tmp;          }             else             {                   tmp->before=NULL;                   tmp->next=head;                   head->before=tmp;                   head=tmp;             }             size++;       }       void tampil()    {       node *tmp;       tmp=head;       if(size==0)       {             cout<<"data kosong";       }       else       {             for (int n=0;n<size;n++)             {                   cout<<tmp->data<<ends;                   tmp=tmp->next;             }       }    } }; void main() {    DLL a;    a.dll();    cout<<"Membuat Fungsi addfront\n";    a.addFront(1);    a.addFront(2);    a.addFront(3);    a.addFront(4);    a.addFront(5);    a.addFront(6);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi addback\n";    a.addBack(7);    a.addBack(8);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi insert after\n";    a.insertAfter(1,9);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi Insert Before\n";    a.insertbefore(3,10);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi remove Back\n";    a.removeBack();    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi remove All\n";    a.removeAll();    a.tampil();    cout<<endl;    system("pause"); }

 

b.    Hasil run program

Gambar 2.4 Screenshot program double linked list 

2.5.  ANALISA

void insertBefore(int x,int nilai)    {       tmp=new node;       node *tmp,*before;       tmp->data=nilai;       before=head;       while(before->data!=x){       before=before->next;

·      “void insertBefore(int x,int nilai)” merupakan fungsi dengan nama “insertbefore” dengan parameter “x” dan “nilai”. Digunakan untuk menyisipkan node baru sebelum node yang dikehendaki.

·      “node *tmp,*before”, menggunakan nama “tmp” dan “before” untuk node.

·      “tmp->data=nilai” membuat “tmp->data” sama dengan parameter “nilai”. “before=head” membuat node “before” menjadi “head”.

·      “while(before->data!=x)”, jika “before->data” tidak sama dengan “x”, maka akan menjalankan statement “before=before->next”, yaitu node “before” akan tetap berpindah hingga kondisinya terpenuhi.

void removeBack(){       node *tmp;       tmp=tail;       tail=tail->before;       tail->next=tmp->before=NULL;       delete tmp;       size--;

·      “void removeBack()” yaitu fungsi untuk menghapus node dari belakang tanpa menggunakan parameter.

·      “tmp=tail” yaitu membuat “tmp” menjadi “tail”.

·      “tail=tail->before” yaitu memindahkan “tail” bergeser kearah depan.

·      “tail->next=tmp->before=NULL”, digunakan untuk memutuskan kedua pengait pada node.

·      “delete tmp”, untuk menghapus node dan “size—“ untuk mengurangi jumlah node.

void removeAll(){       node *tmp;       int x=size;       for(int n=0;n<x;n++)       {       if(size==1){             tmp=head;             head=tail=NULL;             delete tmp;             size--;       }       else{             tmp=head;             head=head->next;             head->before=NULL;             tmp->next=NULL;             delete tmp;             size--;}           }       }

·      “void removeAll()”, merupakan fungsi untuk mnghapus semua node.

·       ”int x=size”, mendeklarasikan “x” sama dengan “size”.

·        “for(int n=0;n<x;n++)” merupakan jenis perulangan yang digunakan. Jika size-nya sama dengan 1, maka “tmp” akan berada di head, dan nilai head dan tail-nya NULL. Setelah itu “delete tmp” maka size-nya akan berkurang.

·       Namun jika size-nya tidak sama dengan 1, maka “tmp” akan tetap berada pada head dan head-nya yang akan berpindah. Kemudian buat “tmp->next=NULL” dan “tmp->next=NULL” untuk memutuskan pengait ke node. Selanjutnya hapus node “tmp”.

void insertAfter(int x,int nilai){       node *tmp, *after;       tmp=new node;       tmp->data=nilai;       after= head;       while(after->data!=x){           after=after->next;       }          tmp->next=after->next;          after->next->before=tmp;          tmp->before=after;          after->next=tmp;          size++;}

·       “void insertAfter(int x,int nilai)”, merupakan fungsi untuk meyisipkan node setelah node yang dikehendaki.

·       “tmp=new node”, membuat node baru dengan nama “tmp”.

·       “tmp->data=nilai”, mendeklarasikan variabel “tmp” sama dengan parameter nilai, dan memindahkan variabel “after” menjadi head dengan cara “after= head”.

·       “while(after->data!=x)”, merupakan sebuah perulangan jika “after->data” tidak sama dengan “x”  maka “after=after->next” akan tetap berlanjut hingga kondisi tersebut tidak terpenuhi.

·       Untuk menyisipkan node menggunakan statement “tmp->next=after->next, after->next->before=tmp, tmp->before=after, after->next=tmp” statement diatas digunakan untuk memutus dan menyambungkan node pada letak yang diinginkan.

Void addBack (int nilai)       {        node *tmp;        tmp=new node;       tmp->data=nilai;        tmp->next=NULL;       tmp->before=tail;       tail->next=tmp;       tail=tmp;       size++;       }

·      “void addBack (int nilai)” merupakan fungsi untuk menambahkan node dari belakang.

·      Membuat node baru dan “tmp->data=nilai” yaitu menjadikan “tmp” sama dengan parameter nilai.

·      “tmp” akan di NULL-kan dengan “tmp->next=NULL” dan memindahkan tail menjadi “tmp”.

Void addFront(int nilai)    {       node *tmp;       tmp=new node;       tmp->data=nilai;       if(size==0){          head=tail=tmp;}       else{           tmp->before=NULL;           tmp->next=head;           head->before=tmp;           head=tmp;}           size++;}

·       “void addFront(int nilai)” merupakan fungsi untuk menambahkan node di depan.

·       Membuat node baru dan “tmp->data=nilai” yaitu menjadikan “tmp” sama dengan parameter nilai.

·       Jika size-nya sama 0, maka head dan tail sama dengan “tmp”. Jika tidak, maka “tmp->before” di NULL-kan.

·       “tmp->next” menjadi head dan “head->before” sama dengan “tmp”. Selanjutnya head akan dipindahkan ke “tmp”.

void main() {    DLL a;    a.dll();    cout<<"Membuat Fungsi addfront\n";    a.addFront(1);    a.addFront(2);    a.addFront(3);    a.addFront(4);    a.addFront(5);    a.addFront(6);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi addback\n";    a.addBack(7);    a.addBack(8);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi insert after\n";    a.insertAfter(1,9);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi Insert Before\n";    a.insertbefore(3,10);    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi remove Back\n";    a.removeBack();    a.tampil();    cout<<endl;    cout<<"Membuat Fungsi remove All\n";    a.removeAll();    a.tampil();    cout<<endl;    system("pause");}

·      Script tersebut merupakan fungsi utama yang akan digunakan untuk melakukan pemanggilan fungsi-fungsi yang berada di dalam class.

2.6.  KESIMPULAN

Berdasarkan praktikum yang dilakukan dapat disimpulkan bahwa :

1.    Perbedaan double linked list dengan single linked list hanya terletak pada pointer penunjuk. Double linked list mempunyai dua ponter yaitu before dan next sedangkan single linked list hanya mempunyai satu pointer yaitu next saja.

2.    Operasi-operasi pada double linked list yaitu seperti pembuatan node baru, penyisipan dan penghapusan node. Operasi pada double linked list sama saja dengan operasi-operasi yang dilakukan pada single linked list hanya saja double linked list mempunyai pointer balik berupa before.