Doubly Linked List

Doubly Linked List

Double/Doubly linked list atau daftar tertaut dua arah adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. struktur data daftar tertaut dengan dua tautan, satu yang berisi referensi ke data berikutnya dan satu yang berisi referensi ke data sebelumnya.

Doubly linked list yang nodenya berisi tiga bidang: tautan ke simpul sebelumnya, nilai integer, dan tautan ke simpul berikutnya.

Insert

Sama seperti dalam Singel Linked List, pertama, kita harus mengalokasikan node baru dan menetapkan nilainya, dan kemudian kita menghubungkan node dengan daftar tertaut yang ada.

Misalkan kita ingin menambahkan node baru di belakang tail.

            struct tnode *node =

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

            node->value = x;

            node->next  = NULL;

            node->prev  = tail;

            tail->next  = node;

            tail = node;

Misalkan kita ingin menyisipkan simpul baru di posisi tertentu (setiap lokasi antara head dan tail)

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;

Delete

Ada 4 kondisi yang harus kita perhatikan saat menghapus:

·         Node yang akan dihapus adalah satu-satunya node dalam linked list.

free(head);

            head = NULL;

            tail = NULL;

·         Node yang akan dihapus adalah head.

head = head->next;

            free(head->prev);

            head->prev = NULL;

·         Node yang akan dihapus adalah tail.

tail = tail->prev;

free(tail->next);

tail->next = NULL;

·         Node yang akan dihapus bukanlah head atau 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);

Circular Doubly Linked List

Ini mirip dengan single linked list melingkar, tetapi penunjuk total di setiap simpul di sini adalah 2 (dua) petunjuk.