Chrystopher's Blog

Sesi 2 :

Implementasi Linked List

Linked list adalah struktur data yang terdiri dari urutan data record sehingga masing-masing record ada field yang berisi referensi ke record berikutnya dalam urutan.

Linked List:

1. Single Linked List
   Untuk membuat list, kita harus mendefinisikan struktur node untuk listnya.
   Misalkan kita ingin membuat daftar integer.

   struct tnode {
   int value;
   struct tnode *next;
   };
   struct tnode *head = 0; —> head = pointer menuju elemen pertama dalam linked list
   

   Single Linked List : Insert
   Untuk menyisipkan value baru, pertama kita harus mengalokasikan node baru secara dinamis dan memberikan value padanya dan kemudian menghubungkannya dengan linked list yang ada.
   Misalkan kita ingin menambahkan simpul baru di depan kepala.

   struct tnode *node =
   (struct tnode*) malloc(sizeof(struct tnode));
   node -> value = x;
   node -> next  = head;
   head = node;

   Operator -> memiliki arti yang sama seperti :

   (*node).value = x;
   (*node).next  = head;

   
   Tambahkan node baru di depan head. Asumsikan sudah ada linked list yang berisi : 10, 35, 27.

   Single Linked List : Delete
   Untuk menghapus value, pertama-tama kita harus menemukan lokasi dari node yang menyimpan value yang ingin kita hapus, hilangkan, dan hubungkan linked list yang tersisa.
   Misalkan value yang ingin kita hapus adalah x dan asumsikan x ada di linked list dan bernilai unik (tidak sama dengan yang lain).

   Ada 2 kondisi yang harus kita perhatikan : jika x ada di node head atau x tidak ada di node head.

   struct tnode *curr = head;

   // jika x berada di node head

   if ( head -> value == x ) {
   head = head -> next;
   free(curr);
   }

   // jika head berada di node tail (ekor)

   else if(tail -> value == x){
   while(curr -> next!=tail) curr = curr -> next;
   free(tail); tail = curr;
   tail -> next = NULL;
   }

   // jika x tidak berada di node head, temukan lokasinya

   else {
   while ( curr -> next -> value != x ) curr = curr -> next;
   struct tnode *del = curr->next;
   curr -> next = del -> next;
   free(del);
   }

   Delete 31 (terletak di head) :
   

   Delete 35 (tidak terletak di head) :
   

2. Polynomial Representation
   Polynomial dirumuskan sebagai : 6x³ + 9x² + 1
   Setiap istilah individu dalam polynomial terdiri dari dua bagian, koefisien dan kekuatan.
   Di sini, 6, 9, 7, dan 1 adalah koefisien dari persyaratan yang masing-masing memiliki 3, 2, 1, dan 0 sebagai kekuatan masing-masing.
   Setiap istilah polinomial dapat direpresentasikan sebagai simpul dari linked list.
   
3. Circular Single Linked List
   Dalam circular, node terakhir mengandung pointer menuju node pertama.
   Tidak ada penyimpanan value / nilai NULL dalam list.
   
4. Doubly Linked List
   Doubly Linked List atau linked list 2 jalur, yaitu linked list data struktur dengan 2 alamat (link), yang satu mengandung referensi ke data selanjutnya (next) dan satu lagi mengandung referensi ke data sebelumnya (previous).
   

   struct tnode {
   int value;
   struct tnode *next;
   struct tnode *prev;
   };
   struct tnode *head = 0;
   struct tnode *tail = 0;

   Doubly Linked List : Insert
   Misalkan kita ingin memasukkan node baru dalam posisi tertentu (lokasi di manapun, antara head dan tail).

   struct tnode *a = ??;
   struct tnode *b = ??;
   // node baru akan dimasukkan antara a dan bstruct tnode *node =
   (struct tnode*) malloc(sizeof(struct tnode));
   node -> value  = x;
   node -> next  = b;
   node -> prev  = a;
   a -> next  = node;
   b -> prev  = node;

   Doubly Linked List : Delete
   Ada 4 kondisi yang harus kita perhatikan ketika ingin menghapus :
   – Node yang akan dihapus adalah satu-satunya node dalam linked list.
   – Node yang akan dihapus adalah head.
   – Node yang akan dihapus adalah tail.
   – Node yang akan dihapus bukan head maupun tail.

   1. Jika node yang akan dihapus adalah satu-satunya node

   free(head);
   head = NULL;
   tail = NULL;

   2. Jika node yang akan dihapus adalah head

   head = head -> next;
   free(head -> prev);
   head -> prev = NULL;

   3. Jika node yang akan dihapus adalah tail

   tail = tail -> prev;
   free(tail -> next);
   tail -> next = NULL;

   4. Jika node yang akan dihapus bukan head maupun tail

   struct tnode *curr = head;
   while ( curr -> next -> value != x ) curr = curr -> next;
   struct tnode *a   = curr;
   struct tnode *del = curr -> next;
   struct tnode *b   = curr -> next -> next;
   a -> next = b;
   b -> prev = a;
   free(del);

5. Circular Doubly Linked List
   Mirip dengan circular single linked list, tapi total pointer dalam setiap node di sini adalah 2 pointer.
   
6. Header Linked List
   Header Linked List adalah tipe khusus dari linked list yang mengandung sebuah node header pada awal list.
   Jadi, dalam header linked list, START (L) tidak akan menunjuk node pertama dalam list tetapi START (L) akan mengandung alamat dari node header.