MEMBUAT DOUBLE LINKED LIST DENGAN C++

Elemen-elemen dihubungkan dengan dua pointer dalam satu elemen. Struktur ini menyebabkan list 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;

Operasi pada Double Linked List
Membuat Simpul Baru
Untuk membuat node baru digunakan keyword new. Perintah ini digunakan untuk mempersiapkan sebuah node dengan alokasi memorinya. Selanjutnya medan informasi pada node tersebut diisi dengan data tertentu. Terakhir pointer prev dan next diisi dengan NULL.
Fungsi membuat simpul baru

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;
}

Menambah Simpul di Awal
Penambahan node baru yang akan diletakkan di node paling depan, perlu diperhatikan saat pertama kali (data masih kosong), maka saat penambahan data dilakukan head/tail ditunjukkan ke node baru tersebut. Sedangkan jika tidak kosong, data akan ditambahkan didepan head, kemudian node baru akan berubah menjadi head.

Fungsi menambah simpul di awal 

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();
}
Menambah Simpul di Belakang
Penambahan node di belakang akan selalu dikaitkan dengan tail dan kemudian node baru tersebut akan menjadi tail.

Fungsi menambah simpul di belakang
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();
}
Menghapus Simpul di Awal
Menghapus node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus. Kemudian head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru. Setelah itu barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Jika head masih NULL maka berarti data masih kosong!

Fungsi menghapus simpul dibelakang
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();
}

#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();
}