Linked List II

Materi Data Structure 25 Februari 2020

Linked List II

Hal yang akan dibahas pada materi pertemuan hari ini adalah :

1. Circular Single Linked List
2. Doubly Linked List
3. Circular Doubly Linked List

1. Circular Single Linked List

Di dalam circular single linked list, node paling akhir berisikan pointer yang menunjuk pada node pertama, sehingga di dalam circular single linked list tidak ada NULL value pada node paling terakhir.

contoh penggambaran circular single linked list

2. Doubly Linked List

Doubly/Double linked list merupakan suatu linked list yang sama seperti pada single linked list, yaitu dia memiliki pointer yang menunjuk node setelahnya dan di node paling akhir selalu menunjuk ke NULL.

Namun yang membedakan double linked list adalah double linked list memiliki dua tautan, yaitu satu link yang menunjuk ke data selanjutnya da satu link lagi menunjuk pada data sebelumnya.

Atau dengan kata lain double linked list memiliki 1 pointer ekstra tambahan untuk menunjuk alamat  node yang berada di sebelumnya, sehingga hal ini membuat node pertama pada double linked list pointer prevnya menunjuk ke NULL.

contoh gambaran perbedaan single linked list dengan double linked list

Double Linked List Insertion

Misalnya kita memiliki double linked list dengan code berikut:

dan jika kita ingin melakukan insertion pada double linked list tersebut, maka insertionnya dapat dilakukan dengan cara sebagai berikut :

1. Insertion at the beginning of the list

LANGKAH-LANGKAH :

-  Pertama-tama ketika kita ingin membuat node yang baru maka kita harus mengalokasikan memori yang baru untuk node tersebut dengan menggunakan fungsi (malloc), dan kita initialize value dari node yang baru.

-  Lalu karena kita ingin menempatkan node yang baru pada bagian awal maka kita harus initialize pointer prev node yang baru untuk menunjuk ke NULL.

-  Langkah selanjutnya kita menghubungkan node yang baru dengan node yang pertama pada linked list dengan cara membuat next pointer dari node yang baru berisi alamat dari node yang paling pertama dari linked list awal, lalu kita juga harus menghubungkan pointer prev dari node linked list yang lama dengan node yang baru.

-  Langkah terakhir kita harus memindahkan posisi head ke node yang baru.

dapat dilihat codenya sebagai berikut:

2. Insertion at the end of the list

  

LANGKAH-LANGKAH :

-  Pertama-tama ketika kita ingin membuat node yang baru maka kita harus mengalokasikan memori yang baru untuk node tersebut dengan menggunakan fungsi (malloc), dan kita initialize value dari node yang baru.

-  Karna kita akan menempatkan node yang baru pada bagian akhir dari linked list, maka kita harus initialize next pointer dari node yang baru untuk menunjuk ke NULL.

-  Kemudian, kita harus menghubungkan node yang baru dengan node terakhir dari linked list yang lama

dapat dilihat codenya sebagai berikut:

Double Linked List Delete

terdapat beberapa hal yang perlu diperhatikan apabila kita ingin mendelete node dari suatu linked list yaitu:

1.  The node to be deleted is the only node in linked list

     free (head);

     head = NULL;

     tail = NULL;

2.  The node to be deleted is head

atau sumber lain menyebutkan sebagai berikut:

     head = head->next;

  free(head->prev);

  head->prev = NULL;

3.  The node to be deleted is tail

atau sumber lain menyebutkan sebagai berikut;

     tail = tail->prev;

  free(tail->next);

  tail->next = NULL;

4.  The node to be deleted is not head or 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);

3. Circular Doubly linked list

Pada circular doubly linked list sama seperti pada circular single linked list, akan tetapi pada circular doubly linked list tiap node terdapat 2 pointer. pointer next yang berada pada tail tiap node berfungsi untuk menunjuk node setelahnya, dan pointer prev pada head tiap node berfungsi untuk menunjuk node sebelumnya.  

contoh penggambaran circular doubly linked list

NAMA : Timothy Gilbert

NIM : 2301851036

KELAS Besar : CB01

KELAS Lab : LK01