Minggu, 01 Maret 2020
Review singkat materi pertemuan 1: Linked List I
- Linked List : sebuah struktur data linear yang terdiri dari data berurut sehingga tiap data berisi referensi ke data berikutnya dalam urutan.
- Elemen dalam Linked List disebut Node
- Linked List memungkinkan Insertion dan Deletion pada node di lokasi manapun dalam list
- Linked List dibagi kedalam dua bentuk : Single Linked List & Double Linked List
- Linked List hanya bisa diakses secara sekuensial (berurutan) sesuai jejak penyimpanan data
- Single linked list : setiap node hanya memiliki 1 pointer mengarah ke node lain
Materi : Linked List (ii)
Circular
Linked List : Circular Linked List adalah varian dari Linked List dimana node
pertama (head) menunjuk ke node terakhir (tail) dan kebalikannya. Circular
dapat dibentuk dengan single maupun double linked list
Circular
Doubly Linked List : Sama dengan yang single, hanya saja total pointer ada dua.
Double
linked list : Linked list dimana setiap node memiliki 1 pointer keareah node berikutnya
dan 1 pointer kearah node sebelumnya. Seperti halnya single linked list, double
linked list juga dapat melakukan insert dan delete.
Insert :
seperti single linked list, pertama kita harus mengalokasikan node baru
kedalam list, menetapkan value pada node tersebut, dan barulah kita sambungkan
ke list.
Contoh :
1. Jika kita ingin menaruh node baru tersebut dibelakang tail
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
node->value
= x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail =
node;
struct tnode *a = ??;
struct tnode *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
Delete :
4 kondisi yang harus diperhatikan saat melakukan delete:
- Node yang akan dihapus adalah satu-satunya node di linked list
- Node berada di Head
- Node berada di Tail
- Node berada diantara Head dan Tail
- Jika sesuai kondisi (1)
free(head);
head = NULL;
tail = NULL;
head = NULL;
tail = NULL;
- Jika sesuai kondisi (2)
head = head->next;
free(head->prev);
head->prev = NULL
free(head->prev);
head->prev = NULL
- Jika sesuai kondisi (3)
tail =
tail->prev;
free(tail->next);
tail->next = NULL;
free(tail->next);
tail->next = NULL;
- Jika sesuai kondisi (4)
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);
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);
