Modul 7. Double Linked List - fzl-22/modul-alstrukdat-informatika GitHub Wiki
Double Linked List
# Pengertian Double Linked List:
Double linked list adalah linked list yang masing-masing elemennya memiliki 2 suksesor, yaitu Suksesor yang menunjuk pada elemen sebelumnya (Prev) dan suksesor yang menunjuk pada sesudahnya (Next).
# Komponen dalam Double Linked List:
- First : Pointer pada list yang menunjukan pada elemen pertama list.
- Last : Pointer pada list yang menunjuk pada elemen terakhir list.
- Next : Pointer pada elemen sebagai suksesor yang menunjuk pada elemen didepannya.
- Prev : Pointer pada elemen sebagai suksesor yang menunjukan pada elemen dibelakangnya.
# Keuntungan dari Double Linked List dibandingkan dengan singly linked list:
- Double Linked List dapat di-traverse (dilalui) baik secara maju (forward) maupun mundur (backward).
- Operasi penghapusan (delete) pada Double Linked List lebih efisien jika diberikan sebuah pointer ke node yang akan dihapus.
- Kita dapat dengan cepat menyisipkan (insert) sebuah node baru sebelum node yang diberikan.
- Pada single linked list, untuk menghapus sebuah node, diperlukan pointer ke node sebelumnya. Untuk mendapatkan node sebelumnya ini, kadang-kadang list harus dilalui. Pada Doubly Linked List, kita dapat mendapatkan node sebelumnya menggunakan pointer previous.
# Kekurangan dari Double Linked List dibandingkan dengan singly linked list adalah:
- Setiap node pada Double Linked List membutuhkan ruang ekstra untuk menyimpan pointer previous.
- Semua operasi pada Double Linked List membutuhkan pointer previous tambahan yang harus dipelihara. Sebagai contoh, pada operasi penyisipan (insertion), kita perlu memodifikasi pointer previous bersama dengan pointer next. Sebagai contoh, pada fungsi-fungsi berikut untuk penyisipan pada posisi yang berbeda, kita membutuhkan 1 atau 2 langkah tambahan untuk mengatur pointer previous.
# Aplikasi dari Doubly Linked List:
- Fungsi redo dan undo dalam perangkat lunak.
- Navigasi maju dan mundur dalam browser.
- Untuk sistem navigasi di mana navigasi maju dan mundur diperlukan.
# Operasi pada Double Linked List
Beberapa operasi yang biasanya ada di dalam sebuah double linked list pada dasarnya sama dengan yang ada di dalam single linked list.
1. Create Node
//create node
struct node{
struct node *prev;
int data;
struct node *next;
};
typedef struct node node;
node *pHead = NULL;
//alokasi node
node *alokasiNodeBaru(){
node *pNew = NULL;
pNew = (node*) malloc(sizeof(node));
return (pNew);
}
2. Insert First
void insertFirst(node *pNew){
printf("Masukkan Bilangan: ");
scanf("%d", &pNew->data);
if(pHead == NULL){
pNew->prev = pHead;
pNew->next = pHead;
pHead = pNew;
} else {
pNew->prev = pHead;
pNew->next = pHead;
pHead->prev = pNew;
pHead = pNew;
}
}
3. Insert Last
void inserLast(node *pNew){
node *pEnd;
pEnd = pHead;
printf("Masukkan Nilai yang Ingin Ditambahkan: ");
scanf("%d", &pNew->data);
while(pEnd->next != NULL){
pEnd = pEnd->next;
}
pEnd->next = pNew;
pNew->prev = pEnd;
pNew->next = NULL;
}
4. Insert After
void insertAfter(node *pNew){
node *pWalker;
pWalker=pHead;
int nilai, sisip;
printf("Masukkan Nilai yang Ingin Ditambahkan: ");
scanf("%d", &pNew->data);
printf("Data Disisipkan Setelah Nilai: ");
scanf("%d", &sisip);
while(pWalker!=NULL && pWalker->data!=sisip){
pWalker=pWalker->next;
}
if(pWalker==NULL){
printf("\nData Tidak Ditemukan");
getch();
} else if (pWalker->data == sisip){
pNew->next = pWalker->next;
pWalker->next->prev = pNew;
pWalker->next = pNew;
pNew->prev = pWalker;
} else {
while(pWalker->next != NULL){
pWalker = pWalker->next;
}
pWalker->next = pNew;
pNew->prev = pWalker;
pNew->next = NULL;
}
}
5. Delete First
void deleteFirst(){
node *pHapus;
if(pHead->next == NULL){
pHead = NULL;
} else {
pHapus = pHead;
pHead = pHead->next;
pHead->prev = NULL;
free(pHapus);
}
}
6. Delete Last
void deleteLast(){
node *pEnd;
pEnd = pHead;
if(pHead->next == NULL){
pHead = NULL;
} else {
while(pEnd->next != NULL){
pEnd = pEnd->next;
}
pEnd->prev->next = NULL;
free(pEnd);
}
}
7. Delete After
void deleteAfter(){
node *pCari;
int hapus;
pCari = pHead;
printf("head: %d", pHead->data);
printf("Masukkan Bilangan yang Ingin Dihapus: ");
scanf("%d", &hapus);
while(pCari != NULL && pCari->data != hapus){
pCari = pCari->next;
printf("%d", pCari->data);
}
system("pause");
if(pCari == NULL){
printf("\nData Tidak Ditemukan");
getch();
} else if(pHead->next == NULL) {
pHead = NULL;
} else if (pCari == pHead){
pCari = pHead;
pHead = pHead->next;
pHead->prev = NULL;
free(pCari);
} else if(pCari->next == NULL){
pCari->prev->next = NULL;
free(pCari);
} else {
pCari->prev->next = pCari->next;
pCari->next->prev = pCari->prev;
free(pCari);
}
}
8. View
void View(){
node *pWalker = pHead;
int i=1;
if(pWalker == NULL){
printf("\n[DATA KOSONG]");
} else {
printf("\n");
while(pWalker != NULL){
printf("[%d] ", pWalker->data);
i++;
pWalker = pWalker->next;
}
}
}
9. Main Program
int main()
{
node *pNew;
int pilih, bil;
do{
system("cls");
View();
printf("\n\n");
printf("------------ MENU ------------");
printf("\n1. Insert First");
printf("\n2. Insert Last");
printf("\n3. Insert After");
printf("\n4. Delete First");
printf("\n5. Delete Last");
printf("\n6. Delete After");
printf("\n7. Exit");
printf("\nPilihan: ");
scanf("%d", &pilih);
if(pilih == 1){
pNew = alokasiNodeBaru();
insertFirst(pNew);
} else if (pilih == 2){
pNew = alokasiNodeBaru();
inserLast(pNew);
} else if (pilih == 3){
pNew = alokasiNodeBaru();
insertAfter(pNew);
} else if(pilih == 4){
deleteFirst();
} else if(pilih == 5){
deleteLast();
} else if (pilih == 6){
deleteAfter();
}
} while (pilih != 7);
printf("\n");
return 0;
}
# Soal Latihan
Kerjakan Praktikum diatas lalu tambahkan menu cari data.
Input: 5
Output: Data Ditemukan/Data Tidak Ditemukan