Contoh Kegiatan Single Linked List Dan Double Linked List C++
1. Single Linked List
SLLC yaitu 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 mempunyai field yang berisi data.
Pada simpulan linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.
Deklarasi dan node gres SLLC
Deklarasi node dibentuk dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};
Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node gres berserta alokasi memorinya.
TNode *baru;
gres = 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 sanggup dilakukan pribadi 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 gres akan dikaitan di node paling depan, namun pada ketika pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya.
Pada prinsipnya yaitu mengkaitkan data gres dengan head, kemudian head akan menunjuk pada data gres tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan diharapkan 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 ketika pertama kali data pribadi ditunjuk pada head-nya.
Penambahan di belakang lebih sulit alasannya yaitu kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data kurang arif perlu dipakai 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 gres ke linked list di depan
Penambahan data gres 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 dihentikan dilakukan kalau 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 sehabis head menjadi head baru, kemudian menghapus variabel hapus dengan memakai 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 kurang arif (terakhir) yang ditunjuk oleh tail pada linked list
Penghapusan node dihentikan dilakukan kalau keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian diharapkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya hingga sebelum tail, sehingga tail sanggup ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru. Setelah itu hapus variabel hapus dengan memakai 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 dipakai untuk bergerak sepanjang list, dan memakai pointer hapus yang dipakai untuk menunjuk node-node yang akan dihapus.
Pada ketika pointer hapus menunjuk pada node yang akan dihapus, pointer bantu akan bergerak ke node selanjutnya, dan kemudian pointer hapus akan didelete.
Contoh kegiatan 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 memilih tail
while(current->next!=NULL)
{
previous=current;
current=current->next; }
tail=previous;
//jika sudah mencapai simpulan , 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://helmykediri.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 yaitu struktur embel-embel dalam Double linked list berjulukan pointer prev yang dipakai untuk menunjuk elemen sebelumnya.
• head dari double linked list ditunnjukkan dengan pointer prev dari elemen pertama menunjuk ke NULL.
• Untuk menawarkan tail dari double linked list tersebut, maka pointer next dari elemen terakhir menunjuk NULL.
• Untuk kembali ke head dalam double linked list , kita sanggup memakai 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 sehabis node tertentu
- insert sebelum node tertentu
- insert sebagai node simpulan (tail) dari Double linked list
b. Insert pada node awal
- Kondisi awal : misalkan kita mempunyai list dengan node awal head dan satu node gres yang akan di masukkan berjulukan 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 : yaitu meng-assign node head = insert
c. Insert sehabis node tertentu
- Langkah ke-1 : gunakan pinjaman sebuah node berjulukan 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 simpulan elemen.
- Langkah ke-3 : apabila data x ditemukan, arahkan pointer next node insert menunjuk node yang berada sehabis node cari (cari->next)
- Langkah ke-4 : arahkan pointer prev node insert menunjuk node cari
- Langkah ke-5 : arahkan pointer prev node yang berada sehabis 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 pinjaman sebuah node berjulukan 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 simpulan elemen.
- Langkah ke-3 : apabila data x ditemukan, lakukan pengecekan dulu apakah node sebelum node cari yaitu 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 pinjaman 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 : yaitu 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 simpulan 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 simpulan 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 sehabis node tertentu
void insertAfter(int old, int element)
{
//gunakan pinjaman 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 instruksi yang dicari sama dengan head, apabila sesuai maka operasi insert dilakukan kalau 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 sehabis 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 pinjaman node temp mencari node yang berisi data
//cek apakah sebelum node temp yaitu head, kalau 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 pinjaman node cur untuk menghapus data di awal sehabis 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 sehabis 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 sehabis 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://helmykediri.com/\n";
cout<<"\n";
//Buat opsi pilihan sesuai fungsi masing-masing
init();
int choice;
while(1)
{
//Tampilan list sajian yang sanggup 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 sehabis 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:
0 Response to "Contoh Kegiatan Single Linked List Dan Double Linked List C++"
Post a Comment