Lima soal DLL dari UTS ASD 2022 dan variasinya: tracing pointer prev/next, implementasi Join, dan penghapusan duplikat.
Soal 1–4 bersumber dari naskah UTS ASD 2022. Soal tracing (1, 2, 3, 4) dikerjakan secara manual — gunakan editor untuk mengeksekusi soal implementasi (2, 4, 5).
Kunci DLL: Setiap node memiliki info, next (ke kanan), dan prev (ke kiri). Gambarkan list di kertas sebelum menelusuri ekspresi pointer yang panjang!
Diberikan Double Linked List (F ke 7, L ke 9):
Tentukan hasil keluaran a–j:
void Soal(List *L) {
address tmp;
tmp = (*L).first;
cout << ((tmp->next)->prev)->info << endl; // a?
cout << (((tmp->next)->prev)->next)->next << endl; // b?
cout << (((((((tmp->next)->prev)->next)->prev)->next)->prev)->next)->info << endl; // c?
tmp = ((((tmp->next)->next)->prev)->next)->prev;
cout << tmp->info << endl; // d?
cout << (tmp->next)->prev << endl; // e?
tmp = (*L).first;
((tmp->next)->prev)->next = ((tmp->next)->next)->next;
cout << tmp->info << endl; // f?
cout << tmp << endl; // g?
cout << ((tmp->next)->prev)->next << endl; // h?
tmp = (*L).last;
cout << (tmp->prev)->prev << endl; // i?
((tmp->prev)->prev)->prev = ((*L).first)->next;
cout << (((tmp->prev)->prev)->prev)->info << endl; // j?
}
7 <-> 4 <-> 8 <-> 2 <-> 93 <-> 1 <-> 10 <-> 12 <-> 19Implementasikan Join(&A, &B, 10) sehingga List A disisipkan ke dalam List B tepat setelah node yang bernilai 10.
Diberikan Double Linked List berbeda (F ke 5, L ke 8):
Kode sama dengan Soal 1. Tentukan hasil keluaran a–j untuk list ini!
5 <-> 12 <-> 3 <-> 6 <-> 89 <-> 3 <-> 7 <-> 14 <-> 1Implementasikan Join(&A, &B, 3) — logika sama dengan Soal 2, target berubah menjadi 3.
Implementasikan DeleteDuplicate yang menghapus semua node dengan nilai yang sudah pernah muncul sebelumnya dalam DLL. Kemunculan pertama dipertahankan.
Sebelum: 3 <-> 1 <-> 4 <-> 1 <-> 5 <-> 3 <-> 2 <-> NULL
Sesudah: 3 <-> 1 <-> 4 <-> 5 <-> 2 <-> NULLGunakan dua pointer: outer berjalan dari awal, inner mencari duplikat dari outer->next. Saat menghapus node, jangan lupa update L->last jika node terakhir yang dihapus!
4