Contoh program single linked list dan double linked list C++
1. Single Linked List
SLLC adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
- Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
- Linked List : artinya node-node tersebut saling terhubung satu sama lain.
- Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
Ilustrasi SLLC
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.
Deklarasi dan node baru SLLC
Deklarasi node dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};
Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
SLLC dengan HEAD
- Dibutuhkan satu buah variabel pointer: head
- Head akan selalu menunjuk pada node pertama
Deklarasi Pointer Penunjuk Kepala Single Linked List
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:
TNode *head;
Fungsi Inisialisasi Single LinkedList Circular
void init(){
head = NULL;
}
Function untuk mengetahui kosong tidaknya SLLC
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}
Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.
Source code:
void insertDepan(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
printf("Data masuk\n“);
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
Source code:
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
printf("Data masuk\n“);
}
Function untuk menampilkan isi single linked list
void tampil(){
TNode *b;
b = head;
if(isEmpty()==0){
do{
printf(“%d “,b->data);
b=b->next;
}while(b!=head);
printf(“\n”);
} else printf("Masih kosong\n“);
}
SLLC dgn HEAD
void hapusDepan (){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
Source hapus data belakang :
void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
if(head->next == head){
head = NULL;
}else{
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
Function untuk menghapus semua elemen Linked List
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu->next!=head){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL; }
SLLC dengan HEAD dan TAIL
- Dibutuhkan dua buah variabel pointer: head dan tail
- Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.
Inisialisasi SLLC :
TNode *head, *tail;
Fungsi Inisialisasi SLLC
void init(){
head = NULL;
tail = NULL;
}
Function untuk mengetahui kosong tidaknya SLLC
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
Pengkaitan node baru ke linked list di depan
Penambahan data baru di depan akan selalu menjadi head.
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
tail=baru;
head->next=head;
tail->next=tail;
}
else {
baru->next = head;
head = baru;
tail->next = head;
}
printf("Data masuk\n“);
}
Source code:
void tambahBelakang(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
tail=baru;
head->next=head;
tail->next=tail;
}
else {
tail->next = baru;
tail = baru;
tail->next = head;
}
cout<<"Data masuk\n";
}
Function untuk menampilkan isi linked list:
void tampil(){
TNode *b;
b = head;
if(isEmpty()==0){
do{
printf(“%d”,b->data);
b=b->next;
}while(b!=tail->next);
printf(“\n”);
} else printf("Masih kosong\n“);
}
Function untuk menghapus data di depan:
void hapusDepan(){
TNode *hapus;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head != tail){
hapus = head;
head = head->next;
tail->next = head;
delete hapus;
}else{
head=NULL;
tail=NULL;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru, kemudian menghapus variabel hapus dengan menggunakan perintah delete.
Jika tail masih NULL maka berarti data masih kosong!
Function untuk menghapus data di belakang:
void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
if(head == tail){
d = tail->data;
head = NULL;
tail = NULL;
}else{
bantu = head;
while(bantu->next != tail){
bantu = bantu->next;
}
hapus = tail;
tail = bantu;
d = hapus->data;
tail->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
Function di atas akan menghapus data terbelakang (terakhir) yang ditunjuk oleh tail pada linked list
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru. Setelah itu hapus variabel hapus dengan menggunakan perintah delete.
Jika tail masih NULL maka berarti data masih kosong!
Function untuk menghapus semua elemen LinkedList:
void clear(){
TNode *bantu,*hapus;
if(isEmpty() == 0){
bantu = head;
while(bantu->next!=head){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
tail = NULL;
}
}
Menggunakan pointer bantu yang digunakan untuk bergerak sepanjang list, dan menggunakan pointer hapus yang digunakan untuk menunjuk node-node yang akan dihapus.
Pada saat pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan didelete.
Contoh program single link list C++ dengan fungsi insert diakhir, insert di awal , insert pada node tertentu, delete diawal, delete di akhir, delete/hapus pada node tertentu
#include<iostream>
#include<conio.h>
using namespace std;
//mendeklarasikan struct yang mendefinisikan satu nodes
struct node
{
int data;
node *next; };
//kelas untuk menangani node berisi penunjuk head dan tail
class list
{
private:
node *head, *tail;
public:
list()
{
head=NULL;
tail=NULL;
} void createnode(int value)
{
//buat pointer untuk memasukkan nilai
node *temp=new node;
temp->data=value;
temp->next=NULL;
//jika head berisi null berarti berarti data yang ditaut kosong
if(head==NULL)
{
head=temp;
tail=temp;
temp=NULL;
}
else
{ tail->next=temp;
tail=temp;
}
}
// untuk menampilkan daftar node dari data yang tertaut/linked
void display()
{
node *temp=new node;
temp=head;
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->next;
}
}
//fungsi untuk memasukkan node di awal=head
void insert_start(int value)
{
node *temp=new node;
temp->data=value;
temp->next=head;
head=temp;
}
//fungsi untuk memasukkan node pada posisi tertentu
void insert_position(int pos, int value)
{
node *pre=new node;
node *cur=new node;
node *temp=new node;
cur=head;
//melakukan loop untuk mencapai node tertentu
for(int i=1;i<pos;i++)
{
pre=cur;
cur=cur->next;
}
temp->data=value;
pre->next=temp; temp->next=cur;
}
//fungsi untuk menghapus node pertama dimana temp=head
void delete_first()
{
node *temp=new node;
temp=head;
head=head->next;
delete temp;
}
//fungsi untuk menghapus node terakhir
void delete_last()
{
node *current=new node;
node *previous=new node;
current=head;
//mencari node terakhir hingga mencapai null/kosong untuk menentukan tail
while(current->next!=NULL)
{
previous=current;
current=current->next; }
tail=previous;
//jika sudah mencapai akhir , hapus
previous->next=NULL;
delete current;
}
//fungsi untuk menghapus node pada posisi tertentu
void delete_position(int pos)
{
node *current=new node;
node *previous=new node;
current=head;
//cari posisi yang ingin dihapus kalau sudah ketemu hapus dan lanjutkan pada node berikutnya
for(int i=1;i<pos;i++)
{
previous=current;
current=current->next;
}
previous->next=current->next;
}
};
int main()
{
//memasukkan nilai node
list obj;
obj.createnode(20);
obj.createnode(30);
obj.createnode(40);
obj.createnode(50);
obj.createnode(60);
cout<<"http://helmynia.com\n";
cout<<"\n";
cout<<"---------------Tampilkan semua nodes---------------";
cout<<"\n--------------------------------------------------\n";
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"-----------------Insert diakhir-----------------";
cout<<"\n--------------------------------------------------\n";
obj.createnode(70);
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"----------------Insert diawal----------------";
cout<<"\n--------------------------------------------------\n";
obj.insert_start(80);
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"-------------Insert pada posisi 5--------------";
cout<<"\n--------------------------------------------------\n";
obj.insert_position(5,90);
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"----------------Delete awal-----------------";
cout<<"\n--------------------------------------------------\n";
obj.delete_first();
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"-----------------Delete akhir-------------------";
cout<<"\n--------------------------------------------------\n";
obj.delete_last();
obj.display();
cout<<"\n--------------------------------------------------\n";
cout<<"--------------Delete posisi ke-4--------------";
cout<<"\n--------------------------------------------------\n";
obj.delete_position(4);
obj.display();
cout<<"\n--------------------------------------------------\n";
getch();
}
Preview :
2. Double Linked List
• Perbedaan antara Single linked list dengan Double linked list adalah struktur tambahan dalam Double linked list bernama pointer prev yang digunakan untuk menunjuk elemen sebelumnya.
• head dari double linked list ditunnjukkan dengan pointer prev dari elemen pertama menunjuk ke NULL.
• Untuk menunjukkan tail dari double linked list tersebut, maka pointer next dari elemen terakhir menunjuk NULL.
• Untuk kembali ke head dalam double linked list , kita dapat menggunakan pointer prev dari tail hingga ke ke head
a. Operasi Insert pada Double Linked List :
- insert sebagai node awal (head) dari Double linked list
- insert setelah node tertentu
- insert sebelum node tertentu
- insert sebagai node akhir (tail) dari Double linked list
b. Insert pada node awal
- Kondisi awal : misalkan kita memiliki list dengan node awal head dan satu node baru yang akan di masukkan bernama insert
- Langkah ke-1 : Arahkan pointer next pada node insert menunjuk ke head
- Langkah ke-2 : Arahkan pointer prev pada node insert menunjuk ke NULL
- Langkah ke-3 : Arahkan pointer prev pada node head menunjuk ke insert
- Langkah ke-4 : adalah meng-assign node head = insert
c. Insert setelah node tertentu
- Langkah ke-1 : gunakan bantuan sebuah node bernama cari untuk mencari dan menunjuk node yang berisi data x
- Langkah ke-2 : hentikan pancarian apabila node cari telah menunjuk node yang berisi data x atau pencarian telah berada pada akhir elemen.
- Langkah ke-3 : apabila data x ditemukan, arahkan pointer next node insert menunjuk node yang berada setelah node cari (cari->next)
- Langkah ke-4 : arahkan pointer prev node insert menunjuk node cari
- Langkah ke-5 : arahkan pointer prev node yang berada setelah node cari (cari->next->prev) untuk menunjuk node insert
- Langkah ke-6 : arahkan pointer next node cari menunjuk node insert
d. Insert sebelum node tertentu
- Langkah ke-1 : gunakan bantuan sebuah node bernama cari untuk mencari dan menunjuk node yang berisi data x
- Langkah ke-2 : hentikan pancarian apabila node cari telah menunjuk node yang berisi data x atau pencarian telah berada pada akhir elemen.
- Langkah ke-3 : apabila data x ditemukan, lakukan pengecekan dulu apakah node sebelum node cari adalah head, apabila ternyata head maka operasi insert sama dengan operasi insert di awal. Apabila tidak maka lanjut ke langkh selanjutnya.
- Langkah ke-4 : arahkan pointer next node insert menunjuk node cari
- Langkah ke-5 : arahkan pointer prev node insert menunjuk node sebelum node cari (cari->prev)
- Langkah ke-6 : Arahkan pointer next pada node sebelum node cari (cari->prev->next) untuk menunjuk node insert.
- Langkah ke-7 : Arahkan pointer prev node cari untuk menunjuk node insert
d. Insert pada node terakhir
- Langkah ke-1: gunakan bantuan node tail untuk mencari dan menunjuk node terakhir, dimana node terakhir ditandai dengan pointer next menunjuk ke NULL
- Langkah ke-2 : arahkan pointer next node tail menunjuk pada node insert
- Langkah ke-3 : arahkan pointer prev node insert menunjuk pada node tail
- Langkah ke-4 : adalah meng-assign node tail = insert
Source code double linked list C++ dengan fungsi hapus node tertentu, insert before, insert after , delete first , delete after
#include<iostream>
using namespace std;
//deklarasi struct double linklist bolak-balik dengan pointer next prev
struct node
{
int value;
struct node* next;
struct node* prev;
};
struct node* head;
struct node* tail;
void init()
{
//head ditunjuk dengan pointer prev yang menunjuk ke NULL
//tail ditunjuk dengan pointer next yang menunjuk ke NULL
//untuk kembali ke head , kita gunakan pointer prev dari tail hingga ke head
head=NULL;
tail=NULL;
}
// fungsi insert di awal node
void insertFirst(int element)
{
struct node* newItem;
newItem=new node;
if(head==NULL)
{
head=newItem;
newItem->prev=NULL;
newItem->value=element;
newItem->next=NULL;
tail=newItem;
}
else
{
//untuk insert di awal node, arahkan next ke head (awal), prev ke null , kemudian mengassign head sesuai newitem
newItem->next=head;
newItem->value=element;
newItem->prev=NULL;
head->prev=newItem;
head=newItem;
}
}
//fungsi insert di akhir node
void insertLast(int element)
{
struct node* newItem;
newItem=new node;
newItem->value=element;
if(head==NULL)
{
head=newItem;
newItem->prev=NULL;
newItem->next=NULL;
tail=newItem;
}
else
{
//untuk insert di akhir node, arahkan prev ke tail (akhir), next ke null , kemudian mengassign tail sesuai newitem
newItem->prev=tail;
tail->next=newItem;
newItem->next=NULL;
tail=newItem;
}
}
//fungsi insert setelah node tertentu
void insertAfter(int old, int element)
{
//gunakan bantuan node temp untuk mencari data
struct node* newItem;
newItem=new node;
struct node* temp;
temp=head;
if(head==NULL)
{
cout<<"could not insert"<<endl;
return;
}
//lakukan pengecekan apakah kode yang dicari sama dengan head, apabila sesuai maka operasi insert dilakukan jika tidak lanjutkan
if(head==tail)
{
if(head->value!=old)
{
cout<<"could not insert"<<endl;
return;
}
//Arahkan pointer next ke newitem
newItem->value=element;
head->next=newItem;
newItem->next=NULL;
head->prev=NULL;
newItem->prev=head;
tail=newItem;
return;
}
if(tail->value==element)
{
newItem->next=NULL;
newItem->prev=tail;
tail->next=newItem;
tail=newItem;
return;
}
while(temp->value!=old)
{
temp=temp->next;
if(temp==NULL)
{
cout<<"Could not insert"<<endl;
cout<<"element not found"<<endl;
return;
}
}
//arahkan pointer prev yang berada setelah node temp untuk menunjuk node newitem
newItem->next=temp->next;
newItem->prev=temp;
newItem->value=element;
temp->next->prev=newItem;
temp->next=newItem;
}
//fungsi insert sebelum node tertentu
void insertBefore(int old, int element)
{
//gunakan bantuan node temp mencari node yang berisi data
//cek apakah sebelum node temp adalah head, jika iya lanjut langkah selanjutnya
struct node* newItem;
newItem=new node;
struct node* temp;
temp=head;
if(head==NULL)
{
cout<<"could not insert"<<endl;
return;
}
if(head==tail)
{
if(head->value!=old)
{
cout<<"could not insert"<<endl;
return;
}
newItem->value=element;
head->next=newItem;
newItem->next=NULL;
head->prev=NULL;
newItem->prev=head;
tail=newItem;
return;
}
if(tail->value==element)
{
newItem->next=tail;
newItem->prev=NULL;
tail->next=newItem;
tail=newItem;
return;
}
while(temp->value!=old)
{
temp=temp->next;
if(temp==NULL)
{
cout<<"Could not insert"<<endl;
cout<<"element not found"<<endl;
return;
}
}
//arahkan pointer next ke node newitem dan menunjuk node temp
newItem->prev=temp->prev;
newItem->next=temp;
newItem->value=element;
temp->prev->next=newItem;
temp->prev=newItem;
}
//fungsi hapus node diawal
void deleteFirst()
{
if(head==NULL)
{
return;
}
if(head==tail)
{
//menggunakan bantuan node cur untuk menghapus data di awal setelah di assign dengan head
struct node* cur;
cur=head;
head=NULL;
tail=NULL;
delete cur;
return;
}
else
{
struct node* cur;
cur=head;
//pindahkan head ke element setelah head
head=head->next;
head->prev=NULL;
delete cur;
}
}
//fungsi hapus node diakhir
void deleteLast()
{
//isi head sama dengan tail, gunakan node cur untuk menghapus tail
if(head==NULL) return;
if(head==tail)
{
struct node* cur;
cur=head;
head=NULL;
tail=NULL;
delete cur;
return;
}
else
{
struct node* cur;
cur=tail;
tail=tail->prev;
tail->next=NULL;
delete cur;
}
}
//fungsi hapus node tertentu
void deleteItem(int element)
{
//gunakan node temp untuk mencari dan menunjuk node data element
struct node* temp;
temp=head;
if(head==tail)
{
if(head->value!=element)
{
cout<<"could not delete"<<endl;
return;
}
head=NULL;
tail=NULL;
delete temp;
return;
}
//jika x ditemukan , cek apakah ada data selanjutnya atau tidak
if(head->value==element)
{
head=head->next;
head->prev=NULL;
delete temp;
return;
}
else if(tail->value==element)
{
temp=tail;
tail=tail->prev;
tail->next=NULL;
delete temp;
return;
}
while(temp->value!=element)
{
temp=temp->next;
if(temp==NULL)
{
cout<<"element not found"<<endl;
return;
}
}
//arahkan pointer next pada node temp untuk menunjuk element setelah node temp
//arahkan pointer prev pada node temp untuk menunjuk element sebelum node temp
temp->next->prev=temp->prev;
temp->prev->next=temp->next;
delete temp;
}
//fungsi untuk menampilkan node
void printList()
{
struct node* temp;
temp=head;
while(temp!=NULL)
{
printf("%d->",temp->value);
temp=temp->next;
}
puts("");
}
int main()
{
cout<<"http://helmynia.com/\n";
cout<<"\n";
//Buat opsi pilihan sesuai fungsi masing-masing
init();
int choice;
while(1)
{
//Tampilan list menu yang bisa dipilih
printf("1.InsertFirst \n2.InsertLast \n3.InsertAfter \n4.Insertbefore \n5.DeleteFirst \n6.DeleteLast \n7.Delete Node \n8.Lihat node");
cout<<"\n\nMasukkan pilihan=";
cin>>choice;
if(choice==1)
{
//Untuk memanggil fungsi yang sudah di deklarasikan diatas
int element;
cout<<"Masukkan node=";
cin>>element;
insertFirst(element);
printList();
}
else if(choice==2)
{
int element;
cout<<"Masukkan node=";
cin>>element;
insertLast(element);
printList();
}
else if(choice==3)
{
int old,newitem;
cout<<"Node setelah item=";
cin>>old;
cout<<"Masukkan node baru=";
cin>>newitem;
insertAfter(old,newitem);
printList();
}
else if(choice==4)
{
int old,newitem;
cout<<"Node sebelum item=";
cin>>old;
cout<<"Masukkan node baru=";
cin>>newitem;
insertBefore(old,newitem);
printList();
}
else if(choice==5)
{
deleteFirst();
printList();
}
else if(choice==6)
{
deleteLast();
printList();
}
else if(choice==7)
{
int element;
cout<<"Masukkan node yang akan dihapus=";
cin>>element;
deleteItem(element);
printList();
}
else if(choice==8)
{
printList();
}
}
return 0;
}
Preview:
Posting Komentar untuk "Contoh program single linked list dan double linked list C++"
Posting Komentar
Artikel di blog ini bersumber dari pengalaman pribadi penulis, tulisan orang lain sebagai posting tamu maupun bayaran oleh sebab itu segala hak cipta baik kutipan dan gambar milik setiap orang yang merasa memilikinya