STRUKTUR DATA “LINKED LIST”

B.Linked List ( Definisi )

          Pengertian Lingked List adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan ke elemen yang lain melalui pointer. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian.Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yang diperlukan.Masing-masing komponen sering disebut dengan simpul. Setiap simpul pada dasarnya dibagi atas dua bagian. Bagian pertama disebut dengan Isiyaitu bagian yang berisi nilai yang disimpan oleh simpul. Bagian kedua disebut bagian Pointer, yaitu berisi alamat dari simpul berikutnya dan atau sebelumnya.

       Linked List dapat disajikan dengan 2 bagian besar yaitu, Singly List dan Doubly List. Baik Singly List maupun Doubly List dapat juga disajikan secara melingkar (circular).

·         SINGLY LINKED LIST

                Merupakan Linked List yang paling sederhana. Setiap simpul dibagi menjadi dua bagian yaitu bagian Isi dan bagian Pointer. Bagian Isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian Pointer merupakan bagian yang berisi alamat dari simpul berikutnya.

                   simpul pertama dihubungkan ke simpul kedua melalui bagian simpul pertama. Bagian Pointer simpul kedua dihubungkan ke simpul ketiga.Demikian seterusnya hingga simpul terakhir. Bagian Pointer simpul terakhir tidak dihubungkan ke simpul lain yang disebut sebagai NULL.

Singly Linked List terbagi atas 2 yaitu :

Ø  Non Circular Singly Linked List

Ø  Circular Singly Linked List

Deklarasi Singly Linked List

            Typedef struct node *simpul;

            Struct node

                        {

                         Type_data Isi;

                        Simpul Next;

                        }; 

A.     Operasi pada Singly Linked List

a.      Menambah Simpul

                 Operasi yang digunakan untuk menyisipkan simpul di posisi tertentu.Penyisipan simpul dapat dilakukan di posisi depan, penyisipan simpul dibelakang, penyisipan simpul di antara dua simpul (simpul tengah).

b.      Menghapus Simpul

            Maksudnya adalah operasi menghapus suatu simpul dari suatu Linked List. Dalam melakukan penghapusan simpul, ada yang perlu diperhatikan, bahwa Linked List tidak boleh kosong dan Linked List tidak boleh terputus. Sama halnya dengan penyisipan, penghapusan simpul juga dapat dilakukan terhadap simpul depan, simpul belakang, dan simpul tengah.

c.       Mencetak Isi Simpul

   Nilai masing-masing simpul dapat dicetak mulai dari isi simpul pertama atau simpul depan hingga simpul belakang dengan fungsi berikut ini.

            void Cetak(simpul L)

{

 Simpul bantu;

 if (L == NULL)

            cout << “Linked List Kosong. . . . “ << endl;

 else

            {

             bantu=L;

             cout<<”Isi Linked List : “;

             while (bantu->Next != NULL)

              {

                Cout << bantu -> Isi << “-->”;

              }

            }

}   

·         Doubly Linked List

       Doubly Linked List merupakan Linked List dimana setiap simpul dibagi   menjadi tiga bagian yaitu bagian isi, bagian pointer kiri,danbagian pointer kanan.Bagian isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian pointer kiri merupakan bagian yang berisi alamat dari simpul sebelumnya dan bagian pointer kanan merupakan bagian yang berisi alamat dari simpul berikutnya

Double Linked list terbagi atas 2 :

       •      Non Circular Doubly Linked List

       •      Circular Doubly Linked List

·         Deklarasi Doubly Linked List

            typedef struct node *simpul;

            struct node

                                    {

                                    char Isi;

                                     simpul kanan;

                                     simpul kiri;

                                    };

A.     Operasi Pada Doubly Linked List

a.      Penyisipan Simpul

                Penyisipan simpul adalah operasi penyisipan suatu simpul baru ke             dalam suatu Doubly Linked List. Penyisipan dapat dilakukan di posisi             depan,tengah, dan belakang.

b.      Penghapusan Simpul

     Operasi menghapus suatu simpul dari suatu Linked List pada Doubly Linked List hampir sama dengan penghapusan simpul Singly Linked List, yaitu Linked List (DL) tidak boleh dalam keadaan kosong. Penghapusan simpul juga dapat dilakukan terhadap simpul depan, simpul belakang, dan simpul tengah.

c.       Pencetakan Simpul

                void Cetak(simpul DL)

                {

                 if(DL == NULL)

                                cout << “Linked List Kosong . . . . “ <<endl;

                else

                                {

                                                 cout << “Isi Linked List : “;

                                while (DL != NULL)

                                                {

                                                 Cout << DL->Isi<<” “;

                                                                DL=DL->kanan;

                                                }

                                }

                } 

d.      Mencetak Linked List Secara Mundur

              Mencetak mundur artinya mencetak elemen Linked List mulai dari elemen   simpul belakang ke depan.

void Cetak_Mundur(simpul DL)

{

 if(DL != NULL)

 {

   Cetak_Mundur(DL->kanan);

   cout << DL->Isi<<” “;

 }

}

STRUKTUR DATA " TREE"

G.TREE (DEFINISI)

Kumpulan node yang saling terhubung satu sama lain dalam suatu  kesatuan yang

membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu  cara

merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip

sebuah pohon, walaupun pohon tersebut  hanya tampak sebagai kumpulan node-node  dari atas ke bawah. Suatu struktur data yang tidak linier yang

menggambarkan  hubungan yang hirarkis (one-to-many) dan tidak linier antara

elemen-elemennya.

Deklarasi Pohon

Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun  struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam  setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang  kanan, dan informasi yang akan disimpan dalamsimpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner disajikan sebagai berikut:

Sesuai dengan gambar 7.1, maka deklarasi list yang sesuai adalah:

typedef char TypeInfo;

typedef struct Simpul *Tree;

struct Simpul {

TypeInfo Info;

tree Kiri, /* cabang kiri */

Kanan; /* cabang kanan */

};

 ISTILAH DALAM TREE

1. JENIS-JENIS TREE

BINARY TREE

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub

pohon dan kedua subpohon harus terpisah.

Kelebihan struktur Binary Tree :

• Mudah dalam penyusunan algoritma sorting
• Searching data relatif cepat
• Fleksibel dalam penambahan dan penghapusan data

1. KUNJUNGAN PADA POHON BINER

Sebuah pohon biner memiliki operasi  traversal  yaitu suatu kunjungan pada

suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan

memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.

Terdapat tiga jenis kunjungan pada pohon biner, yaitu :

1. PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

Prosedur untuk melakukan traversal secara PREORDER adalah sebagai berikut:

1. INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kanan.

Prosedur untuk melakukan traversal secara INORDER adalah sebagai berikut:

1. POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

–  Cetak isi simpul yang dikunjungi

BERIKUT MERUPAKN CONTOH PROGRAMNYA

#include<stdio.h>//header file

#include<conio.h>

/* Deklarasi struct */

typedef struct Node{

      int data;    //data pada tree

      Node *kiri;  //penunjuk node anak kiri

      Node *kanan; //penunjuk node anak kanan

};

/* Fungsi untuk memasukkan data ke dalam tree */

void tambah(Node **root, int databaru){

      if((*root) == NULL){       //jika pohon/subpohon masih kosong

            Node *baru;//node “baru” dibentuk…

            baru = new Node;//berdasarkan struct “Node”

            baru->data = databaru; //data node baru diisi oleh variabel databaru

            baru->kiri = NULL;//penunjuk kiri node baru masih kosong

            baru->kanan = NULL;//penunjuk kanan node baru masih kosong

            (*root) = baru; //node pohon (root) diletakkan pada node baru

            (*root)->kiri = NULL;//penunjuk kiri node root masih kosong

            (*root)->kanan = NULL; //penunjuk kanan node root masih kosong

            printf(“Data bertambah!”);

      }

      else if(databaru < (*root)->data)//jika databaru kurang dari data node root…

            tambah(&(*root)->kiri, databaru);//tambahkan databaru pada subpohon kiri

      else if(databaru > (*root)->data)//jika databaru lebih dari data node root…

            tambah(&(*root)->kanan, databaru); //tambahkan databaru pada subpohon kanan

      else if(databaru == (*root)->data)//jika databaru sama dengan data node root

            printf(“Data sudah ada!”);//databaru tidak dapat ditambahkan pada tree

}

/* Fungsi untuk menampilkan data secara pre-order

   (data ditampilkan dari node induk, node anak kiri, lalu node anak kanan)

*/

void preOrder(Node *root){

      if(root != NULL){//jika pohon/subpohon tidak kosong

            printf(“%d “, root->data);//menampilkan data node yang dikunjungi

      preOrder(root->kiri);//mengunjungi node anak kiri

      preOrder(root->kanan); //mengunjungi node anak kanan

      }

}

/* Fungsi untuk menampilkan data secara in-order

   (data ditampilkan dari node anak kiri, node induk, lalu node anak kanan)

*/

void inOrder(Node *root){

      if(root != NULL){//jika pohon/subpohon tidak kosong…

      inOrder(root->kiri);//mengunjungi node anak kiri

      printf(“%d “, root->data);//menampilkan data node yang dikunjungi

      inOrder(root->kanan);//mengunjungi node anak kanan

      }

}

              

/* Fungsi untuk menampilkan data secara post-order

   (data ditampilkan dari node anak kiri, node anak kanan, lalu node induk)

*/

void postOrder(Node *root){

     if(root != NULL){//jika pohon/subpohon tidak kosong

     postOrder(root->kiri); //mengunjungi node anak kiri

     postOrder(root->kanan);//mengunjungi node anak kanan

     printf(“%d “, root->data); //menampilkan data node yang dikunjungi

     }

}

main(){

     int pil, c;

     Node *pohon, *t;

     pohon = NULL;

     do{

           int data;

           printf(“MENU\n”);

           printf(“1. Tambah\n”);

           printf(“2. Lihat Pre-Order\n”);

           printf(“3. Lihat In-Order\n”);

           printf(“4. Lihat Post-Order\n”);

           printf(“5. Exit\n”);

           printf(“Pilihan : “); scanf(“%d”, &pil);

           switch(pil){

           case 1 :

                printf(“Data baru : “);

                scanf(“%d”, &data);

                tambah(&pohon, data);

                break;

           case 2 :

                if(pohon != NULL)

                     preOrder(pohon);

                else

                     printf(“Masih kosong!”);

                break;

           case 3 :

                if(pohon != NULL)

                     inOrder(pohon);

                else

                      printf(“Masih kosong!”);

                break;

           case 4 :

                if(pohon != NULL)

                     postOrder(pohon);

                else

                     printf(“Masih kosong!”);

                break;

           }

           getch();

           printf(“\n”);

     }

     while(pil != 5);

}

HASIL