Linked List #3: Double Linked List

May 6, 2022

Double Linked List

Pada tutorial sebelumnya kita sudah mengenal apa itu Single Linked List. Jadi apa nih bedanya Double dan Single Linked List ? Perbedaan yang pertama ada di bagian node nya, di dalam Node Double Linked List terdapat bagian pointer untuk menyimpan alamat dari node sebelumnya yang kita beri nama variabelnya prev untuk previous.

Oke karena Double Linked List menyimpan alamat node sebelumnya, jadi sekarang kita bisa melakukan Traversal kebelakang nih menggunakan pointer prev yang ada pada node. Jadi pada Double Linked List kita bisa melakukan traversal kedepan dan kebelakang.

Penjelasan

HEAD : Berfungsi untuk menyimpan alamat dari Node pertama.
TAIL : Berfungsi untuk menyimpan alamat dari Node terakhir (Pada Single Linked List sebenarnya kita juga bisa menggunakan TAIL)
next : Sebuah pointer yang berfungsi untuk menyimpan alamat node selanjutnya.
prev : Sebuah pointer yang berfungsi untuk menyimpan alamat node sebelumnya.

Contoh program

Oke langsung saja kita awali dengan membuat menu awal terlebih dahulu.

main.cpp

#include <iostream>
using namespace std;

struct Node{
    int data;
    struct Node *next;
    struct Node *prev;
};

int main(){
    Node *HEAD = NULL, *TAIL = NULL;
    int menu;
    while (menu != 9){
        cout << "========== Menu ==========" << endl;
        cout << "1. Tambah Data" << endl;
        cout << "2. Ubah Data" << endl;
        cout << "3. Hapus Data" << endl;
        cout << "4. Tampil Data" << endl;
        cout << "9. Exit Program" << endl;
        cout << "Masukan pilihan : ";
        cin >> menu;
        switch (menu){
        case 1:
            break;
        case 2:
            break;
        case 3:
            break;
        case 4:
            break;
        case 9:
            continue;
        default:
            cout << "Pilihan tidak ada" << endl;
        }
    }
}

Fitur menampilkan data

Karena pada double linked list kita bisa melakukan traversal ke kebelakang, kita coba contoh penerapannya pada menampilkan data.

main.cpp

// Dibawah struct node
void displayData(Node *head, Node *tail){
    // Jika linked list kosong
    if (head == NULL){
        cout << "========================" << endl;
        cout << "Linked List masih kosong" << endl;
        cout << "========================" << endl;
        return;
    }
    // Jika tidak kosong
    int pilih; // default akan bernilai 0
    // Selama variabel pilih tidak bernilai 1 atau 2 kita akan menjalankan : 
    while (pilih != 1 || pilih != 2){
        cout << "========================" << endl;
        cout << "1. Data Awal ke Akhir" << endl;
        cout << "2. Data Akhir ke Awal" << endl;
        cout << "========================" << endl;
        cout << "Masukan pilihan : ";
        cout << "========================" << endl;
        cin >> pilih;
        if (pilih == 1 || pilih == 2){
            // menggunakan operator ternary agar tidak perlu menggunakan if else
            // Jika pilih == 1 maka variabel temp = head, jika tidak maka temp = tail
            Node *temp = pilih == 1 ? head : tail;
            while (temp != NULL){
                cout << temp->data << " ";
                // menggunakan operator ternary agar tidak perlu menggunakan if else
                temp = pilih == 1 ? temp->next : temp->prev;
            }
            cout << endl;
        } else {
            cout << "========================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "========================" << endl;
        }
    }
    cout << "========================" << endl;
}
// Di atas int main()

Penjelasan

Operator Ternary : Operator yang dimana struktrunya kondisi ? eksekusi jika kondisi true : eksekusi jika kondisi false
if (head == NULL) : kita melakukan pengecekan jika linked list nya kosong maka hanya menampilkan output “Linked List Kosong”
temp->next : artinya kita mengakses alamat dari node selanjutnya.
temp->prev : artinya kita mengakses alamat dari node sebelumnya.

Fitur tambah data

Pada fitur tambah data kita coba buatkan fiturnya dimana dapat menambahkan data diawal dan diakhir ( dengan memanfaatkan TAIL ). Biar gak terlalu bingung fungsinya kita pisah dan disatukan pada fungsi tambahData() pada versi 1.

Versi 1

main.cpp

// Di bawah struct Node
void tambahDataAwal(Node **head, Node **tail){
    // Membuat node baru
    Node *nodeBaru = new Node();
    cout << "Masukan angka : ";
    cin >> nodeBaru->data;
    nodeBaru->next = NULL;
    nodeBaru->prev = NULL;
    // Jika linked list kosong, ditambahkan ke node awal
    if (*head == NULL){
        (*head) = nodeBaru;
        (*tail) = nodeBaru;
        cout << "====================================" << endl;
        cout << "Data berhasil ditambahkan" << endl;
        cout << "====================================" << endl;
        return;
    }
    // Jika tidak kosong
    nodeBaru->next = (*head); // menghubungkan node baru dengan node awal
    (*head)->prev = nodeBaru; // menghubungkan node awal dengan node baru
    (*head) = nodeBaru;       // memindahkan head ke node baru
    cout << "====================================" << endl;
    cout << "Data berhasil ditambahkan" << endl;
    cout << "====================================" << endl;
}
void tambahDataAkhir(Node **head, Node **tail){
    // Membuat node baru
    Node *nodeBaru = new Node();
    cout << "Masukan angka : ";
    cin >> nodeBaru->data;
    nodeBaru->next = NULL;
    nodeBaru->prev = NULL;
    // Jika linked list kosong, ditambahkan ke node awal
    if (*head == NULL){
        (*head) = nodeBaru;
        (*tail) = nodeBaru;
        cout << "====================================" << endl;
        cout << "Data berhasil ditambahkan" << endl;
        cout << "====================================" << endl;
        return;
    }
    // Jika tidak kosong
    nodeBaru->prev = (*tail); // menghubungkan node baru dengan node akhir
    (*tail)->next = nodeBaru; // menghubungkan node akhir dengan node baru
    (*tail) = nodeBaru;       // memindahkan tail ke node baru
    cout << "====================================" << endl;
    cout << "Data berhasil ditambahkan" << endl;
    cout << "====================================" << endl;
}
void tambahData(Node **head, Node **tail){
    // Membuat node baru
    int pilih = 0;
    while (pilih != 1 && pilih != 2){
        cout << "====================================" << endl;
        cout << "1. Tambah data di awal linked list" << endl;
        cout << "2. Tambah data di akhir linked list" << endl;
        cout << "====================================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "====================================" << endl;
        if (pilih == 1 || pilih == 2){
            // menggunakan operator ternary agar tidak perlu menggunakan if else
            pilih == 1 ? tambahDataAwal(head, tail) : tambahDataAkhir(head, tail);
        } else{
            cout << "====================================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "====================================" << endl;
        }
    }
}
// Di atas int main()

Versi 2 DRY (Dont Repeat Yourself)

main.cpp

// Di bawah struct Node
void tambahData(Node **head, Node **tail){
    // Membuat node baru
    Node *nodeBaru = new Node();
    cout << "Masukan angka : ";
    cin >> nodeBaru->data;
    nodeBaru->next = NULL;
    nodeBaru->prev = NULL;
    // Jika linked list kosong, ditambahkan ke node awal
    if (*head == NULL){
        (*head) = nodeBaru;
        (*tail) = nodeBaru;
        cout << "Data berhasil ditambahkan" << endl;
        return;
    }
    // Jika tidak kosong
    int pilih = 0;
    while (pilih != 1 && pilih != 2){
        cout << "====================================" << endl;
        cout << "1. Tambah data di awal linked list" << endl;
        cout << "2. Tambah data di akhir linked list" << endl;
        cout << "====================================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "====================================" << endl;
        if (pilih == 1 || pilih == 2){
            if (pilih == 1){
                nodeBaru->next = (*head); // menghubungkan node baru dengan node awal
                (*head)->prev = nodeBaru; // menghubungkan node awal dengan node baru
                (*head) = nodeBaru;       // memindahkan head ke node baru
            }
            else{
                nodeBaru->prev = (*tail); // menghubungkan node baru dengan node akhir
                (*tail)->next = nodeBaru; // menghubungkan node akhir dengan node baru
                (*tail) = nodeBaru;       // memindahkan tail ke node baru
            }
            cout << "====================================" << endl;
            cout << "Data berhasil ditambahkan" << endl;
            cout << "====================================" << endl;
        }
        else{
            cout << "====================================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "====================================" << endl;
        }
    }
}
// Di atas int main()

Fitur hapus data

Kita buat seperti versi 2 tambah data biar efisien dan tidak berulang

main.cpp

// Di bawah struct Node
void hapusData(Node **head, Node **tail){
    // Jika linked list kosong
    if (*head == NULL){
        cout << "Linked list kosong" << endl;
        return;
    }
    // Jika tidak kosong
    // Jika linked list hanya ada 1 node
    if (*head == *tail){
        delete (*head);
        (*head) = NULL;
        (*tail) = NULL;
        cout << "====================================" << endl;
        cout << "Data berhasil dihapus" << endl;
        cout << "====================================" << endl;
        return;
    }
    // Jika linked list lebih dari 1 node
    int pilih = 0;
    while (pilih != 1 && pilih != 2){
        cout << "====================================" << endl;
        cout << "1. Hapus data di awal linked list" << endl;
        cout << "2. Hapus data di akhir linked list" << endl;
        cout << "====================================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "====================================" << endl;
        if (pilih == 1 || pilih == 2){
            if (pilih == 1)
            {
                Node *nodeHapus = (*head);
                (*head) = nodeHapus->next;
                (*head)->prev = NULL;
                delete nodeHapus;
            } else {
                Node *nodeHapus = (*tail);
                (*tail) = nodeHapus->prev;
                (*tail)->next = NULL;
                delete nodeHapus;
            }
            cout << "====================================" << endl;
            cout << "Data berhasil dihapus" << endl;
            cout << "====================================" << endl;
        } else {
            cout << "====================================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "====================================" << endl;
        }
    }
}
// Di atas int main()

Fitur ubah data

Untuk logikanya masih bisa kita terapkan seperti pada single linked list.

main.cpp

// Di bawah struct Node
void ubahData(Node **head)
{
    if (*head == NULL)
    {
        cout << "====================================" << endl;
        cout << "LinkedList masih kosong" << endl;
        cout << "====================================" << endl;
        return;
    }
    int ubah;
    cout << "====================================" << endl;
    cout << "Masukan data yang akan diubah : ";
    cin >> ubah;
    Node *temp = (*head);
    while (temp != NULL)
    {
        if (temp->data == ubah)
        {
            cout << "====================================" << endl;
            cout << "Masukan data yang baru : ";
            cin >> temp->data;
            cout << "====================================" << endl;
            cout << "Data berhasil diubah" << endl;
            cout << "====================================" << endl;
            return;
        }
        temp = temp->next;
    }
    cout << "====================================" << endl;
    cout << "Data tidak ditemukan" << endl;
    cout << "====================================" << endl;
}
// Di atas int main()

Full Source Code

Maka full file nya akan seperti ini.

main.cpp

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
};

void tampilData(Node *head, Node *tail) {
    // Jika linked list kosong
    if (head == NULL) {
        cout << "========================" << endl;
        cout << "LinkedList masih kosong" << endl;
        cout << "========================" << endl;
        return;
    }
    // Jika tidak kosong
    int pilih = 0;
    while (pilih != 1 && pilih != 2) {
        cout << "========================" << endl;
        cout << "1. Data Awal ke Akhir" << endl;
        cout << "2. Data Akhir ke Awal" << endl;
        cout << "========================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "========================" << endl;
        if (pilih == 1 || pilih == 2) {
            // menggunakan operator ternary agar tidak perlu menggunakan if else
            Node *temp = pilih == 1 ? head : tail;
            while (temp != NULL) {
                cout << temp->data << " ";
                // menggunakan operator ternary agar tidak perlu menggunakan if else
                temp = pilih == 1 ? temp->next : temp->prev;
            }
            cout << endl;
        } else {
            cout << "Pilihan tidak ada" << endl;
        }
    }
    cout << "========================" << endl;
}

// Versi 1
// void tambahDataAwal(Node **head, Node **tail) {
//     // Membuat node baru
//     Node *nodeBaru = new Node();
//     cout << "Masukan angka : ";
//     cin >> nodeBaru->data;
//     nodeBaru->next = NULL;
//     nodeBaru->prev = NULL;
//     // Jika linked list kosong, ditambahkan ke node awal
//     if (*head == NULL) {
//         (*head) = nodeBaru;
//         (*tail) = nodeBaru;
//         cout << "Data berhasil ditambahkan" << endl;
//         return;
//     }
//     // Jika tidak kosong
//     nodeBaru->next = (*head); // menghubungkan node baru dengan node awal
//     (*head)->prev = nodeBaru; // menghubungkan node awal dengan node baru
//     (*head) = nodeBaru;       // memindahkan head ke node baru
//     cout << "Data berhasil ditambahkan" << endl;
// }
// void tambahDataAkhir(Node **head, Node **tail) {
//     // Membuat node baru
//     Node *nodeBaru = new Node();
//     cout << "Masukan angka : ";
//     cin >> nodeBaru->data;
//     nodeBaru->next = NULL;
//     nodeBaru->prev = NULL;
//     // Jika linked list kosong, ditambahkan ke node awal
//     if (*head == NULL) {
//         (*head) = nodeBaru;
//         (*tail) = nodeBaru;
//         cout << "Data berhasil ditambahkan" << endl;
//         return;
//     }
//     // Jika tidak kosong
//     nodeBaru->prev = (*tail); // menghubungkan node baru dengan node akhir
//     (*tail)->next = nodeBaru; // menghubungkan node akhir dengan node baru
//     (*tail) = nodeBaru;       // memindahkan tail ke node baru
//     cout << "Data berhasil ditambahkan" << endl;
// }
// void tambahData(Node **head, Node **tail) {
//     // Membuat node baru
//     int pilih = 0;
//     while (pilih != 1 && pilih != 2) {
//         cout << "====================================" << endl;
//         cout << "1. Tambah data di awal linked list" << endl;
//         cout << "2. Tambah data di akhir linked list" << endl;
//         cout << "====================================" << endl;
//         cout << "Masukan pilihan : ";
//         cin >> pilih;
//         cout << "====================================" << endl;
//         if (pilih == 1 || pilih == 2) {
//             // menggunakan operator ternary agar tidak perlu menggunakan if else
//             pilih == 1 ? tambahDataAwal(head, tail) : tambahDataAkhir(head, tail);
//         } else {
//             cout << "====================================" << endl;
//             cout << "Pilihan tidak ada" << endl;
//             cout << "====================================" << endl;
//         }
//     }
// }

// Versi 2
void tambahData(Node **head, Node **tail) {
    // Membuat node baru
    Node *nodeBaru = new Node();
    cout << "====================================" << endl;
    cout << "Masukan angka : ";
    cin >> nodeBaru->data;
    nodeBaru->next = NULL;
    nodeBaru->prev = NULL;
    // Jika linked list kosong, ditambahkan ke node awal
    if (*head == NULL) {
        (*head) = nodeBaru;
        (*tail) = nodeBaru;
        cout << "====================================" << endl;
        cout << "Data berhasil ditambahkan" << endl;
        cout << "====================================" << endl;
        return;
    }
    // Jika tidak kosong
    int pilih = 0;
    while (pilih != 1 && pilih != 2) {
        cout << "====================================" << endl;
        cout << "1. Tambah data di awal linked list" << endl;
        cout << "2. Tambah data di akhir linked list" << endl;
        cout << "====================================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "====================================" << endl;
        if (pilih == 1 || pilih == 2) {
            if (pilih == 1) {
                nodeBaru->next = (*head); // menghubungkan node baru dengan node awal
                (*head)->prev = nodeBaru; // menghubungkan node awal dengan node baru
                (*head) = nodeBaru;       // memindahkan head ke node baru
            } else {
                nodeBaru->prev = (*tail); // menghubungkan node baru dengan node akhir
                (*tail)->next = nodeBaru; // menghubungkan node akhir dengan node baru
                (*tail) = nodeBaru;       // memindahkan tail ke node baru
            }
            cout << "====================================" << endl;
            cout << "Data berhasil ditambahkan" << endl;
            cout << "====================================" << endl;
        } else {
            cout << "====================================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "====================================" << endl;
        }
    }
}

void hapusData(Node **head, Node **tail) {
    // Jika linked list kosong
    if (*head == NULL) {
        cout << "Linked list kosong" << endl;
        return;
    }
    // Jika tidak kosong
    // Jika linked list hanya ada 1 node
    if (*head == *tail) {
        delete (*head);
        (*head) = NULL;
        (*tail) = NULL;
        cout << "====================================" << endl;
        cout << "Data berhasil dihapus" << endl;
        cout << "====================================" << endl;
        return;
    }
    // Jika linked list lebih dari 1 node
    int pilih = 0;
    while (pilih != 1 && pilih != 2) {
        cout << "====================================" << endl;
        cout << "1. Hapus data di awal linked list" << endl;
        cout << "2. Hapus data di akhir linked list" << endl;
        cout << "====================================" << endl;
        cout << "Masukan pilihan : ";
        cin >> pilih;
        cout << "====================================" << endl;
        if (pilih == 1 || pilih == 2) {
            if (pilih == 1) {
                Node *nodeHapus = (*head);
                (*head) = nodeHapus->next;
                (*head)->prev = NULL;
                delete nodeHapus;
            } else {
                Node *nodeHapus = (*tail);
                (*tail) = nodeHapus->prev;
                (*tail)->next = NULL;
                delete nodeHapus;
            }
            cout << "====================================" << endl;
            cout << "Data berhasil dihapus" << endl;
            cout << "====================================" << endl;
        } else {
            cout << "====================================" << endl;
            cout << "Pilihan tidak ada" << endl;
            cout << "====================================" << endl;
        }
    }
}

void ubahData(Node **head) {
    if (*head == NULL) {
        cout << "====================================" << endl;
        cout << "LinkedList masih kosong" << endl;
        cout << "====================================" << endl;
        return;
    }
    int ubah;
    cout << "====================================" << endl;
    cout << "Masukan data yang akan diubah : ";
    cin >> ubah;
    Node *temp = (*head);
    while (temp != NULL) {
        if (temp->data == ubah) {
            cout << "====================================" << endl;
            cout << "Masukan data yang baru : ";
            cin >> temp->data;
            cout << "====================================" << endl;
            cout << "Data berhasil diubah" << endl;
            cout << "====================================" << endl;
            return;
        }
        temp = temp->next;
    }
    cout << "====================================" << endl;
    cout << "Data tidak ditemukan" << endl;
    cout << "====================================" << endl;
}

int main() {
    Node *HEAD = NULL, *TAIL = NULL;
    int menu = 0;
    while (menu != 9) {
        cout << "========== Menu ==========" << endl;
        cout << "1. Tambah Data" << endl;
        cout << "2. Ubah Data" << endl;
        cout << "3. Hapus Data" << endl;
        cout << "4. Tampil Data" << endl;
        cout << "9. Exit Program" << endl;
        cout << "Masukan pilihan : ";
        cin >> menu;
        switch (menu) {
        case 1:
            tambahData(&HEAD, &TAIL);
            break;
        case 2:
            ubahData(&HEAD);
            break;
        case 3:
            hapusData(&HEAD, &TAIL);
            break;
        case 4:
            tampilData(HEAD, TAIL);
            break;
        case 9:
            continue;
        default:
            cout << "Pilihan tidak ada" << endl;
        }
    }
}

Akhir kata

Bisa dibilang jika kita menggunakan Double Linked List akan membuat program kita menjadi lebih mudah mengolah datanya dibandingkan dengan saat menggunakan Single Linked List, dapat kita lihat ketika ingin menghapus data di akhir linked list. Dan penggunaan lain dari Double Linked List ini ketika kita ingin menerapkan konsep Tree dan juga Graph yang akan kita bahas pada tutorial selanjutnya. Terima kasih sudah membaca sampai akhir 🤗.

Linked List #3: Double Linked List

Double Linked List

Penjelasan

Contoh program

Membuat menu

Fitur menampilkan data

Penjelasan

Fitur tambah data

Versi 1

Versi 2 DRY (Dont Repeat Yourself)

Fitur hapus data

Fitur ubah data

Full Source Code

Akhir kata

Artikel Terkait