Skip to main content

Linked List II


Halo teman-teman,

Terima kasih sudah mau menyempatkan waktunya untuk mau melihat blog saya. Disini saya akan memberikan penjelasan mengenai Linked List II. Di blog ini saya akan membahas Linked List Single Circular, Linked List Doubly, dan Linked List Doubly Circular.

Saya harap blog saya dapat membantu teman-teman semua.
Terima kasih.

Single Linked List Circular


Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.

          Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular


Ilustrasi

-         Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data
-         Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.
Rangkaian Single Linked List tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan diakhiri dengan node yang mengarah ke pointer null yang akan menunjuk ke salah satu node kembali.


Single Linked List Circular tidak mempunyai pointer dua arah sehingga hanya bisa menunjuk ke satu arah. Pointer yang bisa menunjuk ke dua arah disebut Doubly Linked List yang akan dibahas di bagian selanjutnya.




Doubly Linked List

Pengertian Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu next dan prev. Dimana pointer next menunjuk ke node setelah dan node prev menunjuk ke node.
Pointer pembantu di dalam Double Linked List adalah head dan tail. Pointer ini akan digunakan dalam menunjuk elemen lain.

Ilustrasi

Pointer head akan menunjuk pada node pertama di dalam linked list dan pointer tail akan menunjuk pada node paling akhir di dalam linked list. Sebuah linked list dikatakan kosong apabila isi pointer head-nya adalah NULL. Pointer prev dari head akan selalu menunjuk NULL karena merupakan data pertama. Begitu pula dengan pointer next dari tail yang akan selalu NULL sebagai penanda data terakhir.
Beberapa operasi yang biasanya ada di dalam sebuah double linked list di antara lain :

1   1)     Push

Push merupakan operasi sebuah insert dimana di dalam linked list akan terdapat tiga jenis insert, yaitu insert melalui depan (pushDepan), insert melalui belakang (pushBelakang), ataupun insert melalui mid atau tengah dari linked list (pushTengah). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya dan pushBelakang berarti sebaliknya, dimana data yang paling baru dimasukkan akan berada di belakang data lainnya.

Representasinya :

o   pushDepan : 3,6,7,10 maka hasilnya adalah 10,7,6,3
o   pushBelakang : 3,6,7,10 maka hasilnya adalah 3,6,7,10.

Push Depan

void pushHead(int age, char name[]){
     //membuat blok data baru
     current = (struct human *)malloc(sizeof human);
     //mengisi data
     strcpy(current->name, name);
     current->age=age;
     //membuat penunjuk data lain menjadi NULL terlebih dahulu
     current->next = current->prev=NULL;

     //jika tidak ada data
     if(head==NULL){
              //maka akan jadi data pertama, head dan tail akan sama dengan data baru
              head=tail=current;
     //jika ada data
     }else{
              //pergantian head menjadi data terbaru
              head->prev=current;
              current->next=head;
              head=current;
     }
}

Push Belakang

void pushTail(int age, char name[]){
     //membuat blok data baru
     current = (struct human *)malloc(sizeof human);
     //mengisi data
     strcpy(current->name, name);
     current->age = age;
     //membuat penunjuk data lain menjadi NULL terlebih dahulu
     current->prev = current->next = NULL;

     //jika tidak ada data
     if(head==NULL){
              //maka akan jadi data pertama, head dan tail akan sama dengan data baru
              head=tail=current;
     //jika ada data
     }else{
              //pergantian tail menjadi data terbaru
              current->prev = tail;
              tail->next = current;
              tail = current;
     }
}

Push Tengah

void PushMid(int age, char name[]){
     //jika tidak ada data
     if(head==NULL){
              //pushHead
              pushHead(age,name);
     //jika umur yang akan dimasukkan lebih kecil dari umur data ke head
     }else if(age < head->age){
              //pushHead
              pushHead(age,name);
     //jika umur yang akan dimasukkan lebih kecil dari umur data ke tail
     }else if(age > tail->age){
              //pushTail
              pushTail(age,name);
     }else{
              //buat blok data
              current = (struct human *)malloc(sizeof human);
              //mengisi data
              strcpy(current->name, name);
              current->age = age;
              //buat penunjuk data sebelum/sesudahnya menjadi NULL terlebih dahulu
              current->next = current->prev = NULL;
             
              struct human *temp=head;
              //mencari posisi dimana data akan dimasukkan
              while(temp!=NULL && temp->age < current->age){
                        temp=temp->next;
              }
              //memasukkan data dan menunjuk alamat-alamat data selanjutnya/sebelumnya
              current->prev=temp->prev;
              current->next=temp;

              temp->prev->next=current;
              temp->prev=current;
     }
}

22)     Pop
Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki dua kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data paling belakang (akhir).


Pop Head

void popHead(){
          //jika tidak ada data
          if(head==NULL){
                   printf("No Data\n");
          //jika hanya ada 1 data
          }else if(head==tail){
                   current=head;
                   head=tail=NULL;
                   free(current);
          //jika lebih dari 1 data
          }else{
                   current=head;
                   head=head->next;
                head->prev=NULL;
                   free(current);
          }
}

          Pop Belakang

void popTail(){
          //jika tidak ada data
          if(head==NULL){
                   printf("No Data\n");
          //jika hanya ada 1 data
          }else if(head==tail){
                   current=tail;
                   head=tail=NULL;
                   free(current);
          //jika lebih dari 1 data
          }else{
                   current=tail;
                   tail=tail->prev;
                tail->next=NULL;
                   free(current);
          }
}

          Pop Tengah

void popMid(int age){
          //inisialisasi flag sebagai penanda eksistensi data
          int temu=0;
          //jika tidak ada data
          if(head==NULL){
                   printf("No Data\n");
          //jika ada data
          }else{
                   current=head;
                   //mencari posisi data
                   while(current!=NULL){
                             //pengecekan data,jika sesuai, ubah flag dan langsung break looping
                             if(current->age==age){
                                      temu=1;
                                      break;
                             }
                             current=current->next;
                   }
                   //jika data ketemu
                   if(temu==1){
                             //jika hanya data yang ditemukan adalah Head
                             if(current==head){
                                      popHead();
                             //jika hanya data yang ditemukan adalah Tail
                             }else if(current==tail){
                                      popTail();
                             //jika hanya data yang ditemukan bukan Head dan bukan Tail
                             }else{
                                      current->prev->next=current->next;
                                      current->next->prev=current->prev;
                                      free(current);
                             }
                   }else{
                             printf("Data Not Found\n");
                   }
          }
}


Circular Doubly Linked List

Memiliki kesamaan dengan Doubly Linked List, namun jumlah pointer di setiap node berjumlah 2 (dua) pointer.



Comments

Post a Comment

Popular posts from this blog

AVL Tree

AVL Tree adalah Binary Tree yang sudah dapat melakukan self-balancing terhadap node di dalam tree-nya Dalam AVL Tree, terdapat 3 komponen utama yaitu: Key / Data yang bersifat unik Level ( perhitungan dari root sampai node / leaf terjauh ) Balance Factor ( perbedaan level dari anak kiri dan anak kanan ) Dalam Gambar, yang diberi warna biru muda memiliki: Key = 75 Level = 3 ( dihitung dari key 100, key 50, dan key 75 ) Balance Factor = 0, yang dilihat dari level anak kiri 75 yaitu, 65 dan anak kanan 75 yaitu, 85, maka 1-1 = 0 Balance Factor dapat dilihat sebagai berikut :  Leaves selalu memiliki balance factor 0 dan level 1 karena leaves adalah node terujung dan tidak memiliki anak  Dari leaves ke induknya, maka balance factor dan level dihitung dengan ketentuan:  Level Induk = [Level tertinggi anak] + 1 Balance Factor = [Level anak kiri] - [Level anak kanan] Sebuah node tidak boleh memiliki Balance Factor lebih dari 1. Jika terdapat node yang memiliki n
Post a Comment
Read more

Heap & Tries

Heap Heap adalah struktur data yang berbentuk pohon yang merupakan jenis dari binary tree. Heap juga mempunyai karakter dimana masing-masing node mempunyai maksimum dua children sebagaimana terdapat di dalam binary tree. Heap juga merupakan complete binary tree yang memenuhi sifat - sifat heap. Heap Property Min Heap dimana setiap key dalam node bernilai lebih kecil dari children-nya Max Heap dimana setiap key dalam node bernilai lebih besar dari children-nya Min Heap Setiap key dalam node bernilai lebih kecil dari key children-nya. Key yang bernilai paling kecil berada di root. Key yang bernilai paling besar berada di salah satu dari node leaves. Heap bisa diimplementasikan menggunakan linked list, namun lebih mudah diimplementasikan dengan menggunakan array Applications of Heaps Heap Sort Selection Algorithm Graph Algorithm Selection Algorithm menemukan key minimum atau maksimum, mencari median, dan menentukan elemen k ter
Post a Comment
Read more

Summary of Data Structures ( 1st Semester )

Single Linked List Circular Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.            Single :  artinya field pointer-nya hanya satu buah saja dan satu arah. Circular :  artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular Ilustrasi -           Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data -           Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head. Rangkaian Single Linked List tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan diakhiri dengan node yang mengarah ke pointer null yang akan menunjuk ke salah satu node kembali. Double Linked L
Post a Comment
Read more