Algoritma dan Struktur Data Pertemuan 8 Doubly Linked List
pHead
Struktur Doubly Linked List A
B
C
Node-node doubly linked list saling berkait melalui pointer. Bagian left sebuah node menunjuk node selanjutnya. Bagian right sebuah node menunjuk node sesudahnya. pHead : pointer yang menunjuk node pertama
pHead
Struktur Doubly Linked List A
B
C
Setiap node terdiri atas Left, yaitu pointer yang menunjuk ke node sebelumnya pada list Data Left, yaitu pointer yang menunjuk ke node sebelumnya pada list Left node pertama bernilai NULL Right node terakhir bernilai NULL
Struktur Sebuah Node Doubly Linked List Setiap node terdiri atas Left, yaitu pointer yang menunjuk ke node sebelumnya pada list Data Left, yaitu pointer yang menunjuk ke node sebelumnya pada list left
data
right
Struktur Sebuah Node Doubly Linked List struct node { //bagian data tipedata data 1; tipedata data 2; … tipedata data n; //pointer ke node sebelum dan sesudahnya struct node *left; struct node *right; }; typedef struct node node;
Deklarasi Head Sebelum membuat doubly linked list, perlu dideklarasikan dan diinisialisasikan pHead, yaitu pointer yang menunjuk node pertama dari double linked list node *pHead = NULL;
Operasi Doubly Linked List 1. 2. 3. 4.
Menambah sebuah node pada doubly linked list. Menghapus sebuah node dari doubly linked list. Mencari node pada doubly linked list. List tranversal
Menambah Node Ke Doubly Linked List Tahap – tahap menambah node pada double linked list: • Buat node baru yang akan ditambahkan. • Tentukan node sebelum tempat penyisipan (pCur). • Set left node baru menunjuk predencecor dan right node baru menunjuk succesor. • Set right predencecor dan left succesor menunjuk node baru . pCur dapat memiliki dua keadaan: • it can contain the address of a node (i.e. you are adding somewhere after the first node – in the middle or at the end) • it can be NULL (i.e. you are adding either to an empty list or at the beginning of the list)
Menambah Node ke Doubly-Linked List Kosong Initial:
Code:
pNew
pNew = (node *) /*create node*/ malloc(sizeof(node)); pNew -> data = 39; pNew -> right = pHead; pNew -> left = pHead; pHead = pNew;
39
pHead
pCur
pNew
After:
pHead
pCur
39
Menambah Node Di Tengah Doubly-Linked List Before: 64
pNew
55
124
pCur
After: pNew
64
55 pCur
124
Menambah Node Di Tengah Doubly-Linked List pNew = (node *) malloc(sizeof(node)); pNew -> data = 64; pNew -> left = pCur; pNew -> right = pCur -> right; pCur -> right -> left = pNew; pCur -> right = pNew;
Menambah Node Di Akhir Doubly Linked List Before: 84
pNew
55
74
pCur
After: pNew
84
55 pCur
74
Menambah Node Di Akhir Doubly Linked List pNew = (node *) malloc(sizeof(node)); pNew -> data = 84; pNew -> left = pCur; pNew -> right = pCur -> right; pCur -> right = pNew;
Kode Untuk Menambah Node Ke DoublyLinked List //insert a node into a linked list struct node *pNew; pNew = (node *) malloc(sizeof(node)); pNew -> data = item; if (pCur == NULL){ //add before first logical node or to an empty list pNew -> left = pHead; pNew -> right = pHead; pHead = pNew; } else { if (pCur -> right == NULL) { //add at the end pNew -> left = pCur; pNew -> right = pCur -> right; pCur -> right = pNew; } else { //add in the middle pNew -> left = pCur; pNew -> right = pCur -> right; pCur -> right -> left = pNew; pCur -> right = pNew; } } }
Menghapus Node Dari Doubly Linked List • Setiap node pada doubly linked list dapat dihapus. Jika doubly linked list tidak memiliki node lagi, maka pHead bernilai NULL . • Untuk menghapus node baru : – Cari node yang akan dihapus (pCur). – Set right dari predencecor menunjuk succesor pCur
pCur
agar
– Set left dari succesor pCur agar menunjuk predencecor pCur – Hapus node yang ditunjuk pCurmenggunakan free function.
Menghapus Node Pertama Doubly-Linked List Before:
Code:
pHead
75
pHead = pCur -> right; pCur ->right -> left = NULL; free(pCur);
124
pCur
After: pHead
Recycled
pCur
124
Menghapus Node Pertama Doubly-Linked List Kasus umum Before: 75 23
12477
46
pCur
After: 75
Recycled
23
pCur
77 124
Kode Untuk Menghapus Sebuah Node Pada Doubly Linked List //delete a node from a linked list if (pCur -> left == NULL){ //deletion is on the first node of the list pHead = pCur -> right; pCur -> right -> left = NULL; { else { //deleting a node other than the first node of the list pCur -> left -> right = pCur -> right; pCur -> right -> left = pCur -> left; } free(pCur).
Pencarian Data Pada Doubly-Linked List • Proses tambah node dan hapus node membutuhkan pencarian node tempat disisipkan dan yang akan dihapus. //search the nodes in a linked list pCur = pHead; //search until the target value is found or the end of the list is reached while (pCur != NULL && pCur -> data != target) { pCur = pCur -> right; } //determine if the target is found or ran off the end of the list if (pCur != NULL) found = 1; else found = 0;
List tranversal • List tranversal mengunjungi seluruh node pada doubly linked list //traverse a linked list node *pWalker; pWalker = pHead; printf(“List contains:\n”); while (pWalker != NULL){ printf(“%d ”, pWalker -> data); pWalker = pWalker -> right; }
