Circular dan Doubly Linked List (+Header Linked List)

Circular Linked List

Circular linked list memiliki pointer pada node terakhir berisi alamat node pertama. Hal ini berbeda dengan singly linked list dimana pointer pada node terakhir bernilai NULL. Berikut adalah operasi pada circular linked list:

• Transversal
  Untuk transversal node-node pada circular linked list, algoritma yang perlu dilakukan adalah:

1. Duplikasi pointer *head.
2. Transverse setiap node menggunakan pointer tersebut.
3. Apabila pointer tersebut sudah sama dengan pointer *head, maka hentikan transversal (keseluruhan node telah diakses).

• Insertion at Front
  Untuk menambahkan node di depan pada circular linked list, algoritma yang perlu dilakukan adalah:

1. Membuat node baru.
2. Mengubah alamat pada pointer pada node baru tersebut ke node pertama.
3. Duplikasi pointer *head, lalu transverse linked list hingga node terakhir dengan pointer tersebut.
4. Ubah alamat pada pointer node terakhir ke dalam node baru.
5. Pindahkan pointer *head ke alamat node baru.

• Insertion at Intermediate Node
  Menambahkan node di antara dua node pada circular linked list sama caranya dengan menambahkan node di antara dua node pada singly linked list (pertemuan sebelumnya).

• Insertion at Back
  Menambahkan node di belakang pada circular linked list sama dengan menambahkan node di awal circular linked list, karena bentuk circular linked list seperti siklus. Perbedaannya adalah pointer *head tidak perlu dipindahkan ke alamat node baru (langkah kelima tidak perlu dilakukan).

• Deletion at Front
  Untuk menghapus node pertama, algoritma yang perlu dilakukan adalah:

1. Pindahkan pointer *head ke node kedua.
2. Duplikasi pointer *head, lalu transverse linked list hingga node terakhir.
3. Hapus node pertama menggunakan alamat pada pointer pada node terakhir.
4. Ubah pointer node terakhir ke node kedua menggunakan alamat pada pointer *head.

• Deletion at Intermediate Node
  Menghapus node di antara dua node pada circular linked list sama caranya dengan menghapus node di antara dua node pada singly linked list (pertemuan sebelumnya). 

• Deletion at Back
  Untuk menghapus node terakhir, algoritma yang perlu dilakukan adalah:

1. Duplikasi pointer *head, lalu transverse linked list hingga satu node sebelum node terakhir dengan pointer tersebut.
2. Hapus node terakhir menggunakan alamat pada pointer node tersebut.
3. Ubah pointer pada node tersebut ke node pertama menggunakan alamat pada pointer *head.

Doubly Linked List

Doubly linked list memiliki pointer ganda pada setiap nodenya. Pointer tersebut mengarah pada node sebelumnya dan setelahnya (*prev dan *next). Hal tersebut memungkinkan transversal pada linked list menjadi lebih efisien untuk dua arah. Sedangkan, transversal pada singly linked list tidak efisien untuk arah yang berlawanan. Pointer *prev pada node pertama dan *next pada pointer terakhir bernilai NULL, kecuali untuk doubly circular linked list, di mana pointer *prev pada node pertama menunjuk pada node terakhir, dan pointer *next pada node terakhir menunjuk pada node pertama. Doubly linked list bersifat space-time tradeoff, di mana terjadi peningkatan kecepatan disertai dengan penambahan memori.

Berikut adalah operasi pada doubly linked list:

• Transversal
  Transversal node-node pada doubly linked list sama dengan singly linked list. Perbedaannya yaitu transversal dapat dilakukan dua arah secara efisien. Untuk melakukan transversing pada doubly linked list, algoritma yang perlu dilakukan adalah:

1. Transversing dari depan ke belakang dapat menggunakan pointer *head sama seperti singly linked list. Pointer *tail dapat juga dibuat dan diarahkan ke node terakhir untuk akses efisien dari belakang ke depan.
2. Duplikasi pointer *head atau *tail sesuai dengan kasus guna.
3. Transverse setiap node menggunakan pointer tersebut hingga menemukan NULL.

• Insertion at Front
  Untuk menambahkan node di depan pada doubly linked list, algoritma yang perlu dilakukan adalah:

1. Membuat node baru.
2. Mengubah alamat pada pointer *prev pada node tersebut menjadi NULL dan alamat pada pointer *next sama dengan pointer *head.
3. Memindahkan pointer *head dan *prev pada node pertama ke alamat node baru.

• Insertion at Intermediate Node
  Untuk menambahkan node di antara dua node pada doubly linked list, algoritma yang perlu dilakukan adalah:

1. Membuat node baru. 
2. Transverse menggunakan *head atau *tail (sebaiknya pilih yang terdekat jaraknya ke antara dua node yang akan diinsersi).
3. Mengubah alamat pada pointer *next pada node baru ke alamat node setelah node baru, dan alamat pada pointer *prev pada node baru ke alamat node sebelum node baru (diakses menggunakan pointer *head atau *tail).
4. Mengubah alamat pada pointer *next pada node sebelum node baru ke alamat node baru.
5. Mengubah alamat pada pointer *prev pada node setelah node baru ke alamat node baru.

• Insertion at Back
  Untuk menambahkan node di belakang pada doubly linked list, algoritma yang perlu dilakukan adalah:

1. Membuat node baru.
2. Mengubah alamat pada pointer *next pada node tersebut menjadi NULL dan alamat pada pointer *prev sama dengan pointer *tail.
3. Memindahkan pointer *tail dan *next pada node terakhir ke alamat node baru.

• Deletion at Front
  Untuk menghapus node pertama, algoritma yang perlu dilakukan adalah:

1. Pindahkan pointer *head ke node kedua menggunakan pointer *next pada node pertama.
2. Hapus node pertama menggunakan pointer *prev pada node kedua.

• Deletion at Intermediate Node
  Untuk menghapus node di antara dua node, algoritma yang perlu dilakukan adalah:

1. Transverse menggunakan *head atau *tail (sebaiknya pilih yang terdekat jaraknya ke antara dua node yang akan di delete).
2. Mengubah alamat pada pointer *next pada node sebelum node yang akan di delete menuju node setelah node yang akan di delete (diakses menggunakan pointer *head atau *tail).
3. Menghapus node menggunakan pointer *prev pada node setelah node yang akan di delete.
4. Mengubah alamat pada pointer *prev pada node setelah node yang telah di delete ke alamat node sebelum node yang telah di delete.

• Deletion at Back
  Untuk menghapus node pertama, algoritma yang perlu dilakukan adalah:

1. Pindahkan pointer *tail ke node kedua sebelum node terakhir menggunakan pointer *prev pada node terakhir.
2. Hapus node terakhir menggunakan pointer *next pada node kedua sebelum node terakhir.

Header Linked List
Header linked list adalah linked list yang ditambahkan node header di awal linked list. Header node ini biasanya digunakan untuk menyimpan karakteristik linked list, seperti jumlah node yang terdapat pada linked list.

Referensi
Cormen, T. and Leiserson, C. (2014). Introduction to algorithms. 3rd ed.
Karumanchi, N. (2016). DATA STRUCTURES AND ALGORITHMS MADE EASY. Careermonk Publications.

Media Pembelajaran Lebih Lanjut:
Linked list (Visualgo) - https://visualgo.net/en/list
Data Structures: Linked Lists by HackerRank (Youtube) - https://www.youtube.com/watch?v=njTh_OwMljA
Doubly Linked List - Implementation in C/C++ by mycodeschool (Youtube) - https://www.youtube.com/watch?v=VOQNf1VxU3Q