Session 3 Linked List II (L)

Di session 3, diajari tentang circular single linked list, doubly linked list, dan circular doubly linked list.

1. 1. Circular Single Linked List 

Seperti namanya, circular linked list berarti linked list yang sambung menyambung seperti lingkaran sehingga tail ke nextnya tidak null dan tidak akan ada node ke next yang null kecuali ketika head dan tailnya belum keisi.

1. 2. Double Linked List

Double linked list tidak berbeda jauh dengan single linked list yang telah diajarkan pada sesi sebelumnya. Di double linked list terdapat tambahan pointer yang menunjuk ke node sebelumnya yaitu pointer prev/previous. Sehingga ketika kita ingin menunjuk data sebelumnya lebih gampang dan efisien.
struct node{
         int value;
         struct node *next;      // pointer yang menunjuk data selanjutnya
         struct node *prev;      // pointer yang menunjuk data sebelumnya
};
struct node *head = 0;
struct node *tail = 0;

Seperti di single linked list, double linked list juga mempunyai beberapa perintah yaitu insert / push.

- Push Head (Menambah data ke barisan paling awal)

  Mirip dengan single linked list, ketika push head node ke nextnya langsung mengarah ke head, tetapi ketika di double linked list, kita harus menghubungkan pointer head sebelumnya ke node yang kita buat sebelum mengganti node yang baru menjadi head yang baru.

struct node *node = (struct node*) malloc(sizeof(struct node));

  node->value = x;

  head->prev=current;
  current->next=head;
  head=current;



- Push Tail (Menambah data ke barisan paling akhir)
  Sebelum insert kita harus membuat sebuah node untuk menampung valuenya, setelah memasukkan value barulah kita menyambungkan node baru tersebut dengan linked list yang sudah ada.

struct node *node = (struct node*) malloc(sizeof(struct node));

  node->value = x;

  node->next  = NULL;          // karena kita ingin push tail maka node ke next itu kosong

  node->prev  = tail;              // menyambungkan node baru dengan tail yang sebelumnya

  tail->next  = node;              // karena tail ke next sebelumnya masih null maka kita harus                                              menyambungkannya dengan node

  tail = node;                         // setelah disambung node yang baru dijadikan tail yang baru

- Delete
Di delete ada beberapa kondisi yang harus diperhatikan yaitu :

• Ketika node yang akan dihapus adalah satu-satunya node di linked list tersebut :
  free(head);
           head = NULL;
           tail = NULL;

• Ketika node yang akan dihapus adalah head :
  head = head->next;
  free(head->prev);
  head->prev = NULL;
• Ketika node yang akan dihapus adalah tail :
  tail = tail->prev;
  free(tail->next);
  tail->next = NULL;
• Ketika node yang akan dihapus bukan head dan bukan 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);
  

1. 3. Circular Doubly Linked List
   Mirip dengan circular single linked list, tetapi di circular doubly linked list terdapat 2 pointer di setiap node-node yang tersambung.