Double Link List C++ Disertai Contoh, Tugas & Jawaban

Imam Ibnu Badri Algoritma dan Pemrograman 08.27

DAFTAR ISI

Materi

Double linked list atau disebut juga Senarai Berantai Ganda hampir sama dengan Single Linked List yang telah dibahas pada bab sebelumnya, yaitu pengalokasian memori secara dinamis yang digunakan untuk menyimpan data. Bedanya Double Linked list lebih flexibel dibanding Single linked list karena pada Double Linked List semua simpul-simpulnya yang ada didalamnya memiliki 2 buah penunjuk yang digunakan untuk mengkaitkan diri dengan simpul lain yang ada disebelah kanannya dan di sebelah kirinya.

Didalam konsep Double Linked List ada 3 unsur pendukung yang penting, yaitu :
1. Penunjuk (Biasa disebut pointer)
Penunjuk atau pointer yang dimaksud disini alat yang digunakan untuk menunjuk sebuah simpul, seperti pada gambar berikut.

Ilustrasi Sebuah Penunjuk atau Pointer

Penunjuk dapat menunjuk ke sebuah sebuah simpul, ataupun ke sebuah tempat kosong (null).

2. Simpul Ganda (biasa disebut node)
Simpul yang digunakan dalam bab ini adalah simpul ganda yang digambarkan sebagai berikut.

Ilustrasi Sebuah Simpul dalam Double Linked List

Simpul yang demikian disebut 'simpul ganda' karena simpul ini mempunyai dua buah pointer, yaitu 'kiri' dan 'kanan'. Artinya pointer kanan menunjuk ke elemen disebelah kanannya dan pointer kiri menunjuk ke elemen disebelah kirnya. Dalam gambar diatas ini diilustrasikan sebuah simpul dalam Double Linked List.

Sedangkan (data) adalah data yang digunakan dalam simpul, kiri adalah pointer yang menunjuk pada simpul sebelumnya dan kanan adalah pointer yang menunjuk pada simpul sesudahnya. Untuk pembuatan simpul ganda dapat dideklarasikan dengan membuat struct strSimpul yang memiliki 2 anggota bertipe strSimpul, yaitu : kanan dan kiri yang berfungsi sebagai penunjuk. Kemudian, struct strSimpul tersebut dibuat aliasnya dengan nama simpul, seperti contoh dibawah ini

typedef struct strSimpul

{

data masukkan;

struct strSimpul *kanan;
struct strSimpul *kiri;

} Simpul;

3. Senarai berantai ganda atau Double Linked List itu sendiri
Seperti senari berantai tunggal, senarai berantai ganda merupakan kumpulan simpul-simpul yang terhubung satu dengan yang lain. Hanya bedanya pada senarai ini setiap simpulnya mempunyai 2 penghubung, kiri dan kanan, seperti Gambar berikt .

Ilustrasi Sebuah Double Linked List

Untuk pembuatan Senarai Berantai Ganda dapat dideklarasika dengan membuat struct strSenarai Ganda yang memiliki 2 anggota bertipe simpul yaitu : awal dan akhir yang berfungsi sebagai penunjuk. Kemudian, struct strSenaraiGanda tersebut dibuat aliasnya dengan nama SenaraiGanda. Selain itu diperlukan juga fungsi untuk membuat Senarai Berantai ganda dengan nama buat dan parameter berupa pointer *q, yang memiliki anggota awal dan akhir dengan nilai awal masih kosong (null), seperti contoh dibawah ini:

typedef struct strSeneraiGanda
{
Simpul *awal;
Simpul *akhir;
} SeneraiGanda;

void buat (SeneraiGanda *q)
{
q -> awal = NULL;
q -> akhir = NULL;
}

Gambar berikut merupakan ilustrasi penambahan data dibelakang pada double link list.

Ilustrasi penambahan data dibelakang pada double link list

Contoh Program

Berikut contoh implementasi double link list untuk menambahkan data didepan , belanga dan membaca data maju.
Source code

#pragma hdrstop
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#pragma argsused

using namespace std;

typedef char data;
typedef struct strSimpul
{
    data masukkan;
    struct strSimpul *kanan;
    struct strSimpul *kiri;
}Simpul;

typedef struct strSeneraiGanda
{
    Simpul *awal;
    Simpul *akhir;
}SeneraiGanda;

void buat (SeneraiGanda *q)
{
    q->awal=NULL;
    q->akhir=NULL;
}

void Tambah_Depan(SeneraiGanda *q, data elemen)
{
    Simpul *baru=new Simpul();
    baru->masukkan=elemen;
    if (q->awal==NULL && q->akhir==NULL)
    {
        q->awal=baru;
        q->akhir=baru;
        baru->kanan=NULL;
        baru->kiri=NULL;
    }
    else
    {
        q->awal->kiri=baru;
        baru->kanan=q->awal;
        q->awal=baru;
        q->awal->kiri=NULL;
    }
}

void Baca_Maju(SeneraiGanda *q)
{
    Simpul *bantu=new Simpul();
    bantu=q->awal;
    while (bantu!=NULL)
    {
        cout<<bantu->masukkan<<" ";
        bantu=bantu->kanan;
    }
    cout<<endl;
}

main()
{
    SeneraiGanda *SnrGd=new SeneraiGanda();
    buat (SnrGd);
    data hasil;
    char pilih='1';
    while (pilih=='1' || pilih=='2' || pilih=='3')
    {
        cout<<"Pilih menu"<<endl;
        cout<<"1. Tambah Depan"<<endl;
        cout<<"2. Tambah Belakang"<<endl;
        cout<<"3. Baca Maju"<<endl;
        cout<<"4. Selesai"<<endl;
        cout<<"Pilihan = ";cin>>pilih;
        switch(pilih)
        {
            case '1':
                {
                   cout<<"Masukkan datanya : ";
                   cin>>hasil;
                   Tambah_Depan(SnrGd, hasil);
                   system("cls");
                } break;
            case '2':
                {
                    system("cls");
                    Baca_Maju(SnrGd);
                } break;
            default :
                {
                    cout<<"Selesai. Tekan enter";
                } break;

        }
    }
    getch();
    delete (SnrGd);
}