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.
- 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
typedef struct TNode{
int data;
TNode *next;
};
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
- Dibutuhkan satu buah variabel pointer: head
- Head akan selalu menunjuk pada node pertama
TNode *head;
Fungsi Inisialisasi Single LinkedList Circular
void init(){
head = NULL;
}
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}
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 masukn“);
}
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 masukn“);
}
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 kosongn“);
}
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 terhapusn“,d);
} else printf(“Masih kosongn“);
}
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 terhapusn“,d);
} else printf(“Masih kosongn“);
}
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu->next!=head){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL; }
- Dibutuhkan dua buah variabel pointer: head dan tail
- Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.
TNode *head, *tail;
Fungsi Inisialisasi SLLC
void init(){
head = NULL;
tail = NULL;
}
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
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 masukn“);
}
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 masukn”;
}
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 kosongn“);
}
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 terhapusn“,d);
} else printf(“Masih kosongn“);
}
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 terhapusn“,d);
} else printf(“Masih kosongn“);
}
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;
}
}
#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<<“https://helmykediri.comn”;
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
#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<<“https://helmykediri.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<<“nnMasukkan 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: