Linked List I

Linked List (senarai berantai) adalah suatu struktur data linier yang dibentuk secara dinamik.

Terdapat tipe – tipe dari linked list, yaitu Simple Linked List, Doubly Linked List, dan Circular Linked List.

Circular Single Linked List

Circular single linked list adalah linked list yang dimana semua node terhubung untuk membentuk suatu lingkaran. Tidak ada NULL di akhir dari linked list. Terdapat keuntungan / advantage dalam pemakaian circular linked list:

-        Node manapun dapat dipakai sebagai starting point. Kita dapat melewati seluruh list dengan dimulai dari mana saja. Hanya diberhentikan ketika node yang pertama dilintasi lagi.

-        Tidak perlu memiliki 2 pointer pada edpan dan belakang jika menggunakan circular linked list.

-        Circular list berguna jika dipakai berulang kali di suatu list.

      Circular Doubly Linked List

Mirip dengan circular single linked list tetapi total pointer di masing – masing node ada dua pointer. Circular Doubly Linked List lebih kompleks yang dimana sebuah node berisi pointer node sebelum dan sesudah. Pada tipe linked list ini tidak terdapat NULL di node manapun. Node terakhir memiliki alamat dari node pertama. Dan node pertama memiliki alamat dari node terakhir pointer sebelumnya.

 Doubly Linked List

Adalah linked list data structure dengan 2 link, 1 link yang memiliki data selanjutnya dan satunya lagi memiliki data sebelumnya. Jadi, terdapat 3 macam pointer yang ada, yaitu pointer sebelum, pointer sesudah, dan data. Untuk menunjukkan head seperti contoh yang diatas, pointer sebelum dari element pertama menunjuk NULL. Untuk menunjukkan tail dari gambar tersebut, pointer sesudah dari elemen terakhir menunjuk NULL.

Jika dijelaskan berdasarkan Bahasa C:

1. Membuat 3 pointer yaitu prev, next, tail, dan head

struct tnode {

int value;

struct tnode *next;

struct tnode *prev;

};

struct tnode *head = 0;

                             struct tnode *tail = 0;

2. Insert

                        struct tnode *node =

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

                              node->value = x;

                              node->next  = NULL;

                              node->prev  = tail;

                              tail->next  = node;

                              tail = node;

3. Delete

Node:

free(head);

            head = NULL;

            tail = NULL;

Head:

            head = head->next;

            free(head->prev);

            head->prev = NULL;  

Tail:

            tail = tail->prev;

free(tail->next);

tail->next = NULL;

Delete tengah:

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);