Elemen-elemen dihubungkan dengan dua pointer dalam satu elemen. Struktur ini menyebabkanlist melintas baik ke depan maupun ke belakang. Masing-masing elemen pada double linked list terdiri dari tiga bagian, disamping data dan pointer next, masing-masing elemen dilengkapi dengan pointer prev yang menunjuk ke elemen sebelumnya. Double linked list dibentuk dengan menyusun sejumlah elemen sehingga pointer next menunjuk ke elemen yang mengikutinya dan pointer prev menunjuk ke elemen yang mendahuluinya. Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail dari double linked list tersebut, maka pointer next dari elemen terakhir menunjuk NULL. Susunan elemen yang dihubungkan dalam bentuk double linked list dapat dilihat pada Gambar di bawah ini.
Gambar 1. Sebuah simpul dengan menggunakan double linked list
Untuk melintas kembali melalui double linked list, kita gunakan pointer prev dari elemen yang berurutan pada arah tail ke head. Double linked list mempunyai fleksibilitas yang lebih tinggi daripada single linked list dalam perpindahan pada list. Bentuk ini sangat berguna ketika akan meletakkan suatu elemen pada list dan dapat memilih dengan lebih bijaksana bagaimana memindahkannya. Sebagai contoh, salah satu fleksibilitas dari double linked list adalah dalam hal memindahkan elemen dari pada menggunakan single linked list.
Definisi simpul
struct node
{ char nama[20];
int umur;
float tinggi;
node *prev;
node *next;
};
Setelah node dibuat, buat variabel baru yang bertipe pointer dari node yang berguna sebagai kepala (head) dan ekor (tail) linked list. Head selalu menunjuk pada simpul pertama, sedangkan tail selalu menunjuk pada simpul terakhir.
node *head=NULL, *tail=NULL;
Ulasan lebih rinci mengenai bagian-bagian dari program lengkap di bawah ini dapat Anda simak di sini:
- Menambah Simpul Double Linked List
- Menghapus Simpul Double Linked List
Program Lengkap
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int pil;
void pilih();
void buat_baru();
void tambah_belakang();
void tambah_depan();
void hapus_belakang();
void hapus_depan();
void tampil();
struct node
{
char nama [20];
int umur;
float tinggi;
node *prev, *next;
};
node *baru, *head=NULL, *tail=NULL,*hapus,*bantu;
void main()
{
do
{
clrscr();
cout<<"MENU DOUBLE LINKEDLIST"<<endl;
cout<<"1. Tambah Depan"<<endl;
cout<<"2. Tambah Belakang"<<endl;
cout<<"3. Hapus Depan"<<endl;
cout<<"4. Hapus Belakang"<<endl;
cout<<"5. Tampilkan"<<endl;
cout<<"6. Selesai"<<endl;
cout<<"Pilihan Anda : ";
cin>>pil;
pilih();
} while(pil!=6);
}
void pilih()
{
if(pil==1)
tambah_depan();
else if(pil==2)
tambah_belakang();
else if(pil==3)
hapus_depan();
else if(pil==4)
hapus_belakang();
else if(pil==5)
tampil();
else
cout<<"selesai";
}
void buat_baru()
{
baru = new(node);
cout<<"input nama : ";cin>>baru->nama;
cout<<"input umur : ";cin>>baru->umur;
cout<<"input tinggi : ";cin>>baru->tinggi;
baru->prev=NULL;
baru->next=NULL;
}
void tambah_belakang()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
tail->next=baru;
baru->prev=tail;
tail=baru;
}
cout<<endl<<endl;
tampil();
}
void tambah_depan()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
baru->next=head;
head->prev=baru;
head=baru;
}
cout<<endl<<endl;
tampil();
}
void hapus_depan()
{
if (head==NULL)
cout<<"Kosong";
else if (head->next==NULL)
{
hapus=head;
head=NULL;
tail=NULL;
delete hapus;
}
else
{
hapus=head;
head=hapus->next;
head->prev=NULL;
delete hapus;
}
cout<<endl<<endl;
tampil();
}
void hapus_belakang()
{
if (head==NULL)
cout<<"Kosong";
else if (head->next==NULL)
{
hapus=head;
head=NULL;
tail=NULL;
delete hapus;
}
else
{
hapus=tail;
tail=hapus->prev;
tail->next=NULL;
delete hapus;
}
cout<<endl<<endl;
tampil();
}
void tampil()
{
if (head==NULL)
cout<<"Kosong";
else
{
bantu=head;
while(bantu!=NULL)
{
cout<<" nama : "<<bantu->nama;
cout<<" umur : "<<bantu->umur;
cout<<" tinggi : "<<bantu->tinggi<<endl;
bantu=bantu->next;
}
}
getch();
}
Sumber
Mata kuliah Struktur Data. STMIK EL Rahma Yogyakarta.
Disusun oleh Eko Riswanto
