Linked List

1. Circular Single Linked List
    Konsep dari circular single linked list ini mirip dengan single linked list biasa tetapi untuk pointer untuk node terakhir menunjuk pointer first, Sehingga tidak ada nilai null pointer.
2. Doubly Linked List
   Doubly Linked list adalah Linked list 2 arah dimana setiap node memiliki 2 pointer yaitu next dan prev sehingga kita bisa bergerak kekiri maupun kekanan, sedangkan single linked list hanya setiap node hanya menunjuk ke satu arah saja.
    Langkah dalam membuat doubly linked list adalah:
     a. Insert
         pertama kita harus membuat fungsi untuk mengenerate node baru dengan mengalokasikan memori sebesar node, kemudian memasukkan nilai nilai parameter kedalam node yang sudah dibuat.
Jika kita ingin memasukkan node kita dibelakang tail cukup inisialisasi prev dari node adalah tail dan next dari tail adalah node. Karena tail letaknya selalu diujung maka inisialisasi tail = node.

struct tnode *node =

(struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Jika kita ingin memasukkan node pada lokasi tertentu. Kita cukup mengganti nilai next dan prev dari node kita menunjuk ke node diantara lokasi yang ingin kita tuju

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

(struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next = b;

node->prev = a;

a->next = node;

b->prev = node;

b. Delete

- Untuk fungsi delete, jika node hanya satu, langsung free pada head kemudian inisialisai head dan tail adalah null
  - Jika node yang dihapus adalah head, jadikan node setelah head adalah head kemudian free node sebelum head yang baru
- Jika node yang dihapus adalah tail, jadikan node sebelum tail adalah tail kemudian free node setelah tail yang baru
- Jka node yang inin dihapus bukan head atau tail. Pertama kita membuat pointer baru yang sama dengan head gunanya agar kita bisa menggerakkan pointer baru ini kekiri dan kekanan. Kemudian kita mengecek nilai dari parameter apakah nilai nodenya sudah sama atau belum. Apabila nilai yang dari parameter dengan node belum sama maka akan looping pointer menunjuk ke node setelahnya. Apabila ketemu, maka diinisialisasi kembali node->prev->next=node->next dan node->next->prev=node->prev. Kemudian node tersebut di free

3. Circular Doubly Linked List
    Ini mirip dengan circular linked list, hanya bedanya setiap node memiliki 2 pointer. Sehingga node pada head memiliki pointer yang menunjuk pada tai dan node pada tail memiliki pointer yang menunjuk ke node head

Implementasi dari Singly Linked list:

1. Implementasi stack dan queue
2. Implementasi grafik : membuat linked list untuk menyimpan vertex yang adjacent
3. Menjaga directory nama
4. Melakukan operasi aritmatik pada long integer
5. manipulasi polinomial dengan menyimpan konstan pada linked list
6. merepresentasikan sparse matrices

Implementasi dari Doubly Linked list:

1. Sistem navigasi karena ada navigasi ke depan dan belakang

2. Implemetasi pada browser ada forward dan backward

3. Fungsi undo dan redo

4. Merepresentasikan dek kartu pada game

5. Merepresentasikan state pada game

Untuk mengatasi masalah doubly linked list tentang kekurangan memori maka di buat XOR Linked List. Cara kerjanya adalah dengan membuat single linkedlist kemudian untuk mengakses setiap nodenya dengan menggunakan operator XOR.  Jadi dalam 1 node terdapat pointer pada node yang menunjuk node kanan dan kirinya dengan bentuk "node kanan ^ node kiri" apabila kita memasukkan node kanan dalam persamaan tersebut maka node yang ditunjuk akan menghasilkan node di kiri. Karena (kanan ^ kiri) ^kanan = kiri.
Referensi:https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/

Kesimpulannya : Langkah-langkah membuat linked list dengan mengalokasikan memori untuk menyimpan data pada memori, kemudian memasukkan nilai dari parameter kedalam node, kemudian menentukan nilai pointer yang ditunjuk. Single Linked List dan Double Linked list sama-sama berguna untuk menyimpan data perbedaan paling mendasar adalah banyaknya pointer pada setiap node yang dimiliki, singly linked list memiliki 1 pointer yaitu next saja sedangkan doubly linked list memiliki pointer next dan prev.