Linked List

  • Circular Single Linked List
Circular Single Linked List sebenarnya adalah dasar dari Single Linked List namun yang membedakannya ada pada bagian tail. Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. Rangkaian Single Linked List tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke NULL. Namun, pada Circular Single Linked List node terakhirnya mengandung pointer yang mengarahkan kepada node pertama sehingga akan membentuk seperti looping. Maka, pada list ini tidak terdapat NULL. Lebih sederhananya, Circular Single Linked List adalah Single Linked List yang tidak mengandung NULL

Untuk ilustrasinya dapat dilihat dari gambar berikut:

  • Doubly Linked List
Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua data yang terurut linear atau sekuensial dengan dua buah pointer yaitu next dan previous. Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasa disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua buah variasi linked list yaitu circular dan non-circular seperti pada Single Linked List yang sudah kita pelajari sebelumnya. Pembeda dari kedua tersebut juga adalah pada Circular Double Linked List tidak mempunyai nilai NULL. 

Contoh non-circular :


Contoh circular :


  • Doubly Linked List : Insert
Insert juga merupakan salah satu operasi yang dapat dilakukan pada Double Linked List. Sama seperti Single Linked List, insert ini berarti memasukkan node ke dalam linked list yang ada. Pertama, kita harus menentukan lokasi dimana node ini akan dimasukkan dan memberi value pada node ini. Setelah itu, kita akan menghubungkan node kepada linked list yang ada. Ada banyak cara untuk melakukan insert yaitu di depan head, di belakang tail, atau di antara head dan tail.
  • Doubly Linked List : Delete
Delete ini juga merupakan salah satu operasi pada Double Linked List. Pada operasi ini berfungsi untuk menghapus node pada suatu linked list.
Ada 4 kondisi yang perlu diperhatikan jika akan melakukan operasi delete :
vNode yang dihapus adalah satu-satunya node pada linked list tersebut.
vNode yang dihapus adalah bagian head.
vNode yang dihapus adalah bagian tail.
vNode yang dihapus adalah bukan head maupun tail.

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Pada dasarnya AVL Tree ini adalah Binary Search Tree namun yang lebih seimbang atau balance karena pasti total node kiri dan kanan selisih tingginya tidak akan lebih dari 1. Sedangkan di BST bisa saja tinggi node kiri dan kanan tidak seimbang sehingga bisa menyebabkan proses pencarian, insert, maupun delete lebih lama yaitu n sedangkan dengan AVL Tree proses pencarian,insert, atau delete menjadi log n. Contoh hasil BST jika dengan insert 2, 5, 7, 8, 13: Contoh hasil AVL Tree jika dengan insert yang sama: Untuk menyeimbangkan node tersebut, AVL Tree menggunakan rotasi atau rotation. Rotation ini dibagi menjadi 2 yaitu single rotation dan double rotation. rotation ini terjadi akibat perbedaan selisih tinggi node kiri dan kanan yang lebih dari 1. Contoh single rotation Contoh double rotation
Baca selengkapnya

HEAP and TRIES

Gambar
HEAP Heaps adalah binary tree yang nodenya dapat direpresentasikan dalam sebuah array. Type of Heap A. Max Heap Max yang berarti parentnya lebih besar daripada childnya. Elemen terbesar pada Max Heap terdapat di root tree dan semakin kebawah artinya semakin kecil. B. Min Heap Min yang berarti parentnya lebih kecil daripada childnya. Elemen terbesar pada Min Heap terdapat di root tree dan semakin kebawah artinya semakin besar. Heap dapat diimplementasikan menggunakan linked list tapi lebih mudah menggunakan array. C. Min Max Heap Ini adalah case unik atau spesial dari heap. Max dan min bergantian pada setiap level. Urutan level dari heap berupa min(dimulai dari root) lalu max lalu min lagi dan seterusnya. Pada bagian min akan selalu ganjil dan max akan selalu genap. Di dalam heap terdapat 2 metode yaitu insertion dan deletion. Max Heap Insertion step 1 : membuat node baru di akhir dari heap step 2 : memasukkan nilai baru ke node tersebut ste...
Baca selengkapnya

Summary

Gambar
Linked List Pada pertemuan kedua kelas besar kemarin saya belajar mengenai cara membuat linked list di C. Setelah saya mempelajarinya kemarin, saya juga mencoba membuat linked list buatan saya sendiri. Berikut codingan linked list saya : #include<stdio.h> #include<stdlib.h> #include<string.h> struct Node{ int test; char nama[1000]; struct Node *next; }*head,*curr,*tail,*temp1,*temp2; void pushhead(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ curr->next = head; head = curr; } } void pushtail(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ tail->next = curr; curr->next=NULL; tail = curr; } } void poptail(){ curr=head; while(curr->next->nex...
Baca selengkapnya