Double Linked List

Algoritma dan Struktur Data

Double Linked List

Oleh

Nama          : Gusnia Syukriyawati

NIM            : 115090607111036

Asisten        : 1. Eka Mahargiyak

: 2. Ahmad Azeri

Program Teknologi Informasi dan Ilmu Komputer

Universitas Brawijaya

Malang

2012

BAB I

Pendahuluan

I.1 Dasar Teori

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).

 
            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.

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

                          node *pHead = NULL;

Operasi Double Linked List 

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

Struktur Double Linked List

Ø  Node-node double 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 Double 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

Contoh Double Linked List :

ABSTRAKSI TIPE DATA DOUBLE 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().

            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.

BAB II

Pembahasan

II.1 Source Code

package Prak5;

class NodeDLL{

       int data;

       NodeDLL prev, next;

}

public class DoubleLinkedList {

       private NodeDLL pKepala, pEkor;

      

       public DoubleLinkedList (){

              pKepala = null;

              pEkor = null;

       }

      

       public void sisipDipKepala(int dt){

              NodeDLL baru = new NodeDLL();

              baru.data = dt;

             

              if (pKepala == null){

                     baru.prev = pKepala;

                     baru.next = pEkor;

                     pKepala = baru;

                     pEkor = baru;

              }

             

              else{

                     baru.next = pKepala;

                     pKepala.prev = baru;

                     pKepala = baru;

              }

       }

      

       public void sisipDipEkor(int data){

              NodeDLL baru = new NodeDLL();

              baru.data = data;

             

              if (pEkor == null){

                     baru.prev = pKepala;

                     baru.next = pEkor;

                     pKepala = baru;

                     pEkor = baru;

              }

             

              else{

                     baru.prev = pEkor;

                     pEkor.next = baru;

                     pEkor = baru;

              }

       }

      

       public void HapusData(int dt) {

            NodeDLL temp = new NodeDLL();

            temp.data = dt;

            NodeDLL a = pKepala;

            NodeDLL b = pKepala;

       

            while ((b.data != dt) && (b != null) ) {

                   a = b;

                   b = b.next;

            }

       

            a.next = b.next;

            b.prev = a;

            b = b.next;

      }

     

    public void SisipSetelahData(int dt, int n) {

            NodeDLL temp = new NodeDLL();       

            temp.data = n;

            NodeDLL a = pKepala;

            NodeDLL b = pKepala;

      

            while ((b.data != dt) && (b != null) ) {

                  b = b.next;

            }

      

            a = b.next;

            temp.next = a;      

            temp.prev = b;

       

            a.prev = temp;

            b.next = temp;     

      }

    public String find(int dt) {

             NodeDLL temp = new NodeDLL(); 

            temp.data = dt;

            NodeDLL a = pKepala;

            NodeDLL b = pKepala;

       

            int n = 1;

            String find=" ";

            

            while ((b.data != dt) && (b != null) ) {

                  b = b.next;

                  n++;

            }

       

            if (n > 0) {

                  find = ("\nData " + dt + " terdapat pada urutan ke " + n);

            }

       

            return find;

      }

   

       public void cetak(String kom){

              System.out.println(kom);

              NodeDLL p = pKepala;

             

             while (p != pEkor){

                     System.out.print(p.data + "->");

                     p = p.next;

              }

              System.out.println("...");

       }

      

       public static void main (String s[]){

             

              DoubleLinkedList dll = new DoubleLinkedList();

              dll.sisipDipKepala(10);

              dll.sisipDipKepala(20);

              dll.sisipDipKepala(30);

              dll.cetak("Isi DLL setelah data di pKepala");

             

              dll.sisipDipEkor(55);

              dll.sisipDipEkor(56);

              dll.sisipDipEkor(57);

              dll.cetak("\nIsi DLL setelah data di pEkor");

             

              dll.HapusData(10);

              dll.cetak("\nIsi DLL setelah mengahapus data 10");

             

              dll.SisipSetelahData(20, 23);

              dll.cetak("\nIsi DLL setelah menambah data 23 setelah data 20");

             

              System.out.println(dll.find(55));

       }

}

II.2 Output

BAB III

Penutup

III.1 Kesimpulan

1. Double Linked list selalu memiliki pointer petunjuk yang selalu menunjuk pada awal dari list yang disebut Head.

2. Double Linked list juga selalu memiliki pointer petunjuk menunjuk pada akhir dari list yang disebut Tail.

3. Double Linked List merupakan salah satu cara untuk mengatasi kelemahan single linked list yang hanya dapat bergerak dalam satu arah saja.

Daftar Pustaka 

 

http://mikeprastiwi.blogspot.com/ diakses pada tanggal 18 november 2012 pukul 19.37

lecturer.ukdw.ac.id/anton/download/TIstrukdata8.pdf  diakses pada tanggal 18 November 2012 pukul 18.00

hansmichael.com/download/SD09.pdf diakses  pada tanggal 18 November 2012