Circular Doubly Linked List
Struktur Data - Pertemuan 17
"Circular Doubly Linked List"
Double Linked List Circular
Circular Doubly Linked List
adalah Linked List dimana link simpul terakhir bukan diisi dengan null, tetapi
diisi dengan alamat simpul pertama yaitu simpul yang ditunjuk oleh pointer
FIRST, sehingga menciptakan efek melingkar’ sesuai arah jarum jam.
Ilustrasi
Double Linked List Circular
Setiap node
pada linked list mempunyai field yang berisi data dan pointer ke node
berikutnya & ke node sebelumnya. Untuk pembentukan node baru ,
mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer
prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node
selanjutnya pada list.
Perbedaan antara Linearly Doubly
Link List dengan Circular Doubly Link List terletak pada simpul terakhir.
Dengan demikian proses pada Linearly dengan Circular sama kecuali penanganan
simpul terakhir.
Berikut ini adalah representasi dari circular double linked list node
dalam C / C ++:
Berikut ini
adalah keuntungan dan kerugian dari circular double linked list:
Keuntungan:
- List dapat dilalui dari kedua arah yaitu dari kepala ke ekor atau dari ekor ke kepala.
- Melompat dari kepala ke ekor atau dari ekor ke kepala dilakukan dalam waktu konstan O (1).
- Circular Doubly Linked Lists digunakan untuk implementasi struktur data tingkat lanjut seperti Fibonacci Heap.
Kekurangan
- Dibutuhkan sedikit memori ekstra di setiap node untuk mengakomodasi pointer sebelumnya.
- Banyak petunjuk yang terlibat saat mengimplementasikan atau melakukan operasi pada list. Jadi, pointer harus ditangani dengan hati-hati jika tidak data dari list dapat hilang.
Program :
Buat program
animasi Circular Doubly Linked List untuk mengelola data mahasiswa dengan
struktur mahasiswa sbb : NAMA, NIM, GENDER, NILAI . Data terurut naik
berdasarkan NIM. Program dibuat dalam bentuk menu dengan pilihan : INSERT DATA,
HAPUS DATA, CETAK DATA, EXIT.
Ket :
INSER DATA :
menambah data
HAPUS DATA :
menghapus satu data berdasarkan kriteria NIM
CETAK DATA :
mencetak seluruh isi linked list
EXIT :
Keluar/selesai
Tampilan menu :
CIRCULAR DOUBLY
LINKED LIST
==========================
1. INSERT DATA
2. HAPUS DATA
3. CETAK DATA
4. EXIT
Pilihan (1 – 4) :
Source Code :
#include
<iostream>
#include
<conio.h>
#include
<stdio.h>
#include
<windows.h>//mendukung format system("CLS") sebagai peganti
clrscr()
using namespace
std;
int pilih; void
pilihan();
void
insert_data();
void
hapus_data();
void
cetak_data();
struct node
{
int nomorinduk;
char nama [40];
char gender [20];
float nilai;
node *prev, *next;
};
node *baru,
*head=NULL, *tail=NULL,*help,*del;
main()//interface
monitor
{
do
{
system("cls");
cout<<"\tLIN. DOUBLY LINKED
LIST"<<endl;
cout<<"\t=========================="<<endl;
cout<<"\t1. INSERT
DATA"<<endl;
cout<<"\t2. HAPUS
DATA"<<endl;
cout<<"\t3. CETAK
DATA"<<endl;
cout<<"\t4. EXIT"<<endl;
cout<<"\tPilihan (1 - 4) : ";
cin>>pilih;
cout<<endl<<endl;
pilihan();
cout<<"==============================="<<endl;
}
while(pilih!=4);
}
void
pilihan()//fungsi "pilihan" untuk pemrosesan
{
if(pilih==1)
insert_data();
else if(pilih==2)
hapus_data();
else if(pilih==3)
cetak_data();
else
{
cout<<"EXIT";
cout<<"\nSampai Jumpa
lagi"<<endl;
}
}
void
buat_baru()//fungsi membuat data baru
{
baru = new(node);
cout<<"Masukkan Nomor Induk :
";cin>>baru->nomorinduk;
cout<<"Masukkan Nama :
";cin>>baru->nama;
cout<<"Masukkan Gender :
";cin>>baru->gender;
cout<<"Masukkan Nilai :
";cin>>baru->nilai;
cout<<"\n\t---Data telah
dimasukkan---";
cout<<"\n\nPRESS ENTER TO
CONTINUE...";
getch();
baru->prev=NULL;
baru->next=NULL;
}
void
insert_data()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
baru->next=head;
head->prev=baru;
head=baru;
}
cout<<endl<<endl;
}
void
hapus_data()//fungsi penghapusan data
{
int hapus,nomorinduk;
if(head==NULL)
{
cout<<"\nLinked List kosong,
\nPenghapusan tidak dapat dilakukan"<<endl;//data yang habis maka
tampilannya
}
else
{
hapus=head->nomorinduk;
cout<<"\nData yang dihapus adalah
";//pemilihan data yang akan dihapus
cin>>nomorinduk;
del = head;
head = head->next;
delete del;
}
}
void cetak_data()
{
if (head==NULL)
cout<<"\nData tidak dapat
ditemukan!"<<endl;//data yang kosong
else
{
help=head;
while(help!=NULL)
{
cout<<" Nomor Induk :
"<<help->nomorinduk;//data akan muncul dengan tampilan
cout<<" Nama :
"<<help->nama;
cout<<" Gender :
"<<help->gender;
cout<<" Nilai :
"<<help->nilai<<endl;
help=help->next;
}
}
getch();
}
Komentar
Posting Komentar