Double Linked Lisk

   Pada dasarnya, penggunaan Double Linked List hampir sama dengan penggunaan Single Linked List yang telah kita pelajari pada materi sebelumnya. Hanya saja Double Linked List menerapkan sebuah pointer baru, yaitu prev, yang digunakan untuk menggeser mundur selain tetap mempertahankan pointer next.

   Keberadaan 2 pointer penunjuk (next dan prev) menjadikan Double Linked List menjadi lebih fleksibel dibandingkan Single Linked List, namun dengan mengorbankan adanya memori tambahan dengan adanya pointer tambahan tersebut
 Ada 2 jenis Double Linked List, yaitu: Double Linked List Non Circular dan Double Linked List Circular.

I.              Double Linked List Cicular

1.       Dengan Head

-          Menggunakan 1 pointer head

-          Head selalu menunjuk node pertama

Sebelumnya kita harus mendeklarasikan dulu pointer head :

                TNode *head;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :

head = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.

int isEmpty() {

      if(head==NULL) return 1;

      else return 0;

}

2.       Dengan Head dan tail

-          Menggunakan 2 pointer, head dan tail.

-          Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir

Sebelumnya kita harus mendeklarasikan dulu pointer head :

                TNode *head, *tail;

Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :

head = NULL;

tail = NULL;

untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.

int isEmpty() {

      if(tail==NULL) return 1;

      else return 0;

}

2.2              INSERT DATA TENGAH

                        Operasi penyisipan data ditengah linked list adalah suatu operasi menambah data diposisi tertentu di dalam linked list. Karena double linked list memiliki dua pointer sambungan, maka penyisipan bisa dilakukan serbelum data tertentu atau sesudah data tertentu, berbeda dengan single linked list yang hanya memiliki satu pointer sambunagn yaitu sambungan kanan atau next.

Untuk proses tersebut ada dua hal yang harus diperhatikan yaitu :

1.        Kondisi linked list masih kosong prosesnya sama sepertyi penyisipan didepan atau awal.

2.        Kondisi linked list sudah mempunyai data.

Contoh program insert data tengah:

#include <iostream.h>

#include <conio.h>

#include <iomanip.h>

#include <string.h>

struct node

{

            char nama[10];

   int nim;

   node *next;

};

int i,n,cari,menu;

node *last=NULL;

node *p, *first, *curr;

node *sementara, *baru;

void pilihan()

{

            cout<<endl;

            cout<<"`````````````````````SINGLE LIST LIST`````````````````````````"<<endl;

   cout<<"1. Insert node awal"<<endl;

   cout<<"2. Insert setelah node tertentu"<<endl;

   cout<<"3. Hapus di akhir"<<endl;

   cout<<"4. Cetak"<<endl;

   cout<<"5. Quit"<<endl;

   cout<<"``````````````````````````````````````````````````````````````"<<endl;

   cout<<"Pilihan anda : ";

   cin>>menu;

   cout<<endl;

   cout<<endl;

}

void insertawal()

{

            cout<<"Input jumlah data = ";

   cin>>n;

   cout<<endl;

   for (i=1;i<=n;i++)

   {

            p= new node;

      cout<<"Node ke-"<<i<<endl;

      if (last==NULL)

      {

            cout<<"Nama : ";

         cin>>p->nama;

         cout<<"NIM : ";

         cin>>p->nim;

         last=p;

         first=last;

      }

      else

      {

            cout<<"Nama : ";

         cin>>p->nama;

         cout<<"NIM : ";

         cin>>p->nim;

         p->next=first;

         first=p;

      }

      cout<<endl;

   }

}

void tertentu()

{

            p=first;

   cout<<"Insert ke node berapa ? ";

   cin>>cari;

   cout<<endl<<endl;

   while(p!=NULL)

   {

            if (p->nim==cari)

      {

            cout<<"Input node baru"<<endl;

         baru=new node;

         cout<<"Nama node baru = ";

         cin>>baru->nama;

         cout<<"NIM node baru = ";

         cin>>baru->nim;

         cout<<endl;

         sementara=p->next;

         p->next=baru;

         baru->next=sementara;

         break;

      }

      else

      {

            p=p->next;

      }

   }

}

void hapusakhir()

{   int h;

            cout<<"masukkan data keberapa yang ingin dihapus!! ";

   cin>>h;

   p=first;

   while (p->next!=)

   {

            sementara=p;

      p=p->next;

   }

   delete p;

   sementara->next=NULL;

}

void display()

{

            p=first;

   clrscr();

   cout<<"Data yang telah diinput : "<<endl;

   cout<<endl;

   while(p!=NULL)

   {

            cout<<"Nama : "<<p->nama;cout<<endl;

      cout<<"NIM  : "<<p->nim; cout<<endl;

      p=p->next;

      cout<<endl;

   }

}

void main()

{

   clrscr();

   do

   {

            pilihan();

      clrscr();

      if(menu==1)

      {

            insertawal();

      }

      else if(menu==2)

      {

            tertentu();

      }

      else if(menu==3)

      {

            hapusakhir();

      }

      else if(menu==4)

      {

            display();

      }

      else if(menu==5)

      {

            cout<<"Thanks";

      }

   }

   while (menu!=5);

getch();

}

2.3         Hapus Data Tengah

Operasi hapus data ditengah linked list adalah suatu operasi menghapus data diposisi tertentu di dalam linked list.

Output program hapus data :

#include <iostream.h>

#include <conio.h>

#include <iomanip.h>

#include <string.h>

struct node

{

          char nama[35];

   char telpon[15];

   node *next;

};

class link

{

 private:

          node *first;

   node *pendahulu; //digunakan untuk penghapusan

   node *cari(char *nama);

 public:

   link();

   ~link();

   int tambah(char *nama,char *telpon);

   void tampil();

   void tampil(char *nama);

   int hapus (char *nama);

};

void main()

{

          //clrscr(); //hapus layar

   link daftar;

   daftar.tambah("Amiruddin","675834");

   daftar.tambah("Esti Pangestu","(024)111111");

   daftar.tambah("Udinsah","56655");

   daftar.tambah("Sita Dewi","443546");

   daftar.tambah("Gusti Randa","565788");

   daftar.tampil();

   daftar.tampil("udin");

   daftar.hapus("Udinsah");

   daftar.tampil();

getch();

}

link::link()

{

          first= NULL;

}

link::~link()

{

          //Hapus seluruh simpul

   node *node_dihapus;

   while(first!= NULL)

   {

          node_dihapus=first;

      first=first->next;

      delete node_dihapus;

   }

}

/////////////////////////////////////////////////////

//tambah()                                         //

//                                                 //

//Menambah data ke link                            //

//Nilai balik:0 - Data tidak berhasil ditambahkan  //

//                (heap penuh)                     //

//            1 - Data berhasil ditambahkan        //

/////////////////////////////////////////////////////

int link::tambah(char *nama,char *telpon)

{

          node *baru;

   baru=new node;

   if (baru)

   {

          baru->next=first;

      strcpy(baru->nama,nama);

      strcpy(baru->telpon,telpon);

      first=baru; //sekarang first menunjuk baru

      return (1);

   }

   else

   return (0);

}

/////////////////////////////////////////////////////

//tampil()                                         //

//                                                 //

//Menampilkan daftar telpon berdasarkan            //

//        suatu penggalan nama. Misalnya : udin           //

// akan cocok dengan Baharudin,Udinsah,Burhanudin  //

/////////////////////////////////////////////////////

void link::tampil(char *nama)

{

          node *ptr_data=first;

   char data_nama[35];

   char dicari[35];

   strcpy(dicari,nama);

   strupr(dicari);

   cout<<setiosflags(ios::left)<<setfill(',');

   cout<<endl<<" DAFTAR TELPON "<<dicari<<" : "<<endl;

   while (ptr_data != NULL)

   {

          strcpy(data_nama,ptr_data->nama);

      strupr(data_nama);

      if (strstr(data_nama,dicari))

      cout<<setw(36)<<ptr_data->nama<<ptr_data->telpon<<endl;

      ptr_data=ptr_data->next;

   }

   cout<<resetiosflags(ios::left)<<setfill(' ');

}

/////////////////////////////////////////////////////

//tampil()                                         //

//                                                 //

//Menampilkan isi seluruh node pada link list      //

/////////////////////////////////////////////////////

void link::tampil()

{

          node *ptr_data=first;

   cout<<setiosflags(ios::left)<<setfill(',');

   cout<<endl<<"DAFTAR TELPON: "<<endl;

   while (ptr_data != NULL)

   {

      cout<<setw(36)<<ptr_data->nama<<ptr_data->telpon<<endl;

      ptr_data=ptr_data->next;

   }

   cout<<resetiosflags(ios::left)<<setfill(' ');

}

/////////////////////////////////////////////////////

//cari()                                           //

//        Nilai balik :                                   //

// €NULL->data tidak ketemu                        //

// €bukan NULL->data ketemu                        //

//  Nilai balik menunjuk node data yang dicari     //

//  dan node pendahulu adalah menunjuk simpul      //

//  yang ada di depannya.                          //

//  Node pendahulu berisi Null kalau data terletak //

//   pada node pertama                             //

/////////////////////////////////////////////////////

node *link::cari(char*nama)

{

          node *ptr_data=first;

   pendahulu=NULL;

   while (ptr_data!=NULL)

   {

          if (strcmp(nama,ptr_data->nama)==0)

          break; //ketemu

      pendahulu=ptr_data;

      ptr_data=ptr_data->next;

   }

   return(ptr_data);

}

/////////////////////////////////////////////////////

//hapus()                                          //

//                                                 //

//Menghapus suatu simpul berdasarkan suatu nama    //

//Nilai balik:0 - Data tidak ada                   //

//            1 - node berhasil dihapus            //

/////////////////////////////////////////////////////

int link::hapus(char *nama)

{

          node *posisi_data;

   posisi_data=cari(nama);

   if (posisi_data==NULL)

          return(0); //data tak ada

   else

   {

          if (pendahulu==NULL)

      {

          // node yang akan dihapus adalah node first

         first=first->next;

      }

      else

      {

          //bukan node first yang akan dihapus

         pendahulu->next=posisi_data->next;

      }

      delete posisi_data;

   }

   return(1);

}