Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
2. JENIS-JENIS LINKED LIST
- Single Linked List
Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
–LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
–FIFO (First In First Out), aplikasinya : Queue (Antrean)
- Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
- Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
–Circular Single Linked List
contoh :
–Circular Double Linked List
contoh :
- Multiple Linked List
Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. contoh :
- Non Circular linked list
Pengertian :
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Ilustrasinya :
-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 NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list
3. OPERASI YANG ADA DI DALAM LINKED LIST
- Operasi Pada Single Linked List
–Konstruktor = Fungsi ini membuat sebuah linked list yang baru dan masih kosong.
–IsEmpty = Fungsi ini menentukan apakah linked list kosong atau tidak.
–Find First = Fungsi ini mencari elemen pert ama dari linked list
–Find Next = Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.
–Retrieve = Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
–Update = Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
–Delete Now = Fungsi ini menghapus elemen yang ditunj uk oleh now. J ika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
- Operasi –operasi pada Double Linked List
–Insert Head = Sesuai dengannamanya, fungsi Insert Head berguna untuk menambah simpul di depan (sebelah kiri). Fungsi ini tidak berada jauh dengan fungsi Insert Tail yang t elah dijelaskan sebelumnya.
–Delete Tail = Fungsi Delete Tail berguna untuk menghapus simpul dari belakang. Fungsi ini merupakan kebalikan dari fungsi I nsert Tail yang menambah simpul dibelakang. Fungsi Delete Tail akan mengarahkan Now kepada Tail dan kemudian memanggil fungsi Delete Now.
–Delete Head = Fungsi Delete Head merupakan kebalikan dari fungsi Delete Tail yang menghapus simpul dari belakang, sedangkan Delete Head akan menghapus simpul dari depan (sebelah kiri). Fungsi Delete Head akan mengarahkan Now kepada Head dan kemudianm memanggil fungsi Delete Now.
4. AGORITMA DAN CONTOH PROGRAM UNTUK OPERASI-OPERASI DIDALAMNYA
a. Single Linked List
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
struct TNode{
int data;
TNode *next;
};
TNode *head, *tail;
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 = NULL;
if(isEmpty()==1){
head=tail=baru;
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
cout<<"Data masuk\n";
}
void insertBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
cout<<"Data masuk\n";
}
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<<bantu->data<<" ";
bantu=bantu->next;
}
} else cout<<"Masih kosong\n";
}
void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head!=tail){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = tail->data;
head=tail=NULL;
}
cout<<d<<"terhapus";
} else cout<<"Masih kosong\n";
}
void hapusBelakang(){
TNode *bantu,*hapus;
int d;
if (isEmpty()==0){
bantu = head;
if(head!=tail){
while(bantu->next!=tail){
bantu = bantu->next;
}
hapus = tail;
tail=bantu;
d = hapus->data;
delete hapus;
tail->next = NULL;
}else {
d = tail->data;
head=tail=NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
void clear()
{
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL)
{
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
printf("CLEAR");
}
main()
{
int pil,databaru;
do
{
clrscr();
cout<<endl<<endl;
cout<<" ==========================="<<endl;
cout<<" = PROGRAM LINKED LIST ="<<endl;
cout<<" ==========================="<<endl;
cout<<" = 1. Insert Depan ="<<endl;
cout<<" = 2. Insert Belakang ="<<endl;
cout<<" = 3. Delete Depan ="<<endl;
cout<<" = 4. Delete Belakang ="<<endl;
cout<<" = 5. Tampil Data ="<<endl;
cout<<" = 6. Clear ="<<endl;
cout<<" = 7. Exit ="<<endl;
cout<<" ==========================="<<endl;
cout<<" Masukan Pilihan : ";cin>>pil;
switch (pil)
{
case 1: clrscr();{
cout<<"Masukkan Data = ";
cin>>databaru;
insertDepan(databaru);
break;
}
case 2: clrscr();{
cout<<"Masukkan Data = ";
cin>>databaru;
insertBelakang(databaru);
break;
}
case 3: clrscr();{
hapusDepan();
break;
}
case 4: clrscr();{
hapusBelakang();
break;
}
case 5: clrscr();{
tampil();
break;
}
case 6: clrscr();{
clear();
break;
}
case 7: {
return 0;
break;
}
default : clrscr();{
cout<<"\n Maaf, Pilihan yang anda pilih tidak tersedia!";
}
}
getch();
}
while(pil!=7);
}
b. Double Linked List
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int pil;
void pilih();
void buat_baru();
void tambah_belakang();
void tambah_depan();
void hapus_belakang();
void hapus_depan();
void tampil();
void tambah_tengah();
void hapus_tengah();
struct node
{
char nama [20];
int umur;
float tinggi;
node *prev, *next;
};
node *baru, *head=NULL, *tail=NULL,*hapus,*bantu,*bantu2;
void main()
{
do
{
clrscr();
cout<<"MENU DOUBLE LINKEDLIST"<<endl;
cout<<"1. Tambah Depan"<<endl;
cout<<"2. Tambah Belakang"<<endl;
cout<<"3. Hapus Depan"<<endl;
cout<<"4. Hapus Belakang"<<endl;
cout<<"5. Tampilkan"<<endl;
cout<<"6. Tambah Tengah"<<endl;
cout<<"7. Hapus Tengah"<<endl;
cout<<"8. Selesai"<<endl;
cout<<"Pilihan Anda : ";
cin>>pil;
pilih();
} while(pil!=8);
}
void pilih()
{
if(pil==1)
tambah_depan();
else if(pil==2)
tambah_belakang();
else if(pil==3)
hapus_depan();
else if(pil==4)
hapus_belakang();
else if(pil==5)
tampil();
else if(pil==6)
tambah_tengah();
else if(pil==7)
hapus_tengah();
else
cout<<"selesai";
}
void buat_baru()
{
baru = new(node);
cout<<"input nama : ";cin>>baru->nama;
cout<<"input umur : ";cin>>baru->umur;
cout<<"input tinggi : ";cin>>baru->tinggi;
baru->prev=NULL;
baru->next=NULL;
}
void tambah_belakang()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
tail->next=baru;
baru->prev=tail;
tail=baru;
}
cout<<endl<<endl;
tampil();
}
void tambah_depan()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
baru->next=head;
head->prev=baru;
head=baru;
}
cout<<endl<<endl;
tampil();
}
void hapus_depan()
{
if (head==NULL)
cout<<"Kosong";
else if (head->next==NULL)
{
hapus=head;
head=NULL;
tail=NULL;
delete hapus;
}
else
{
hapus=head;
head=hapus->next;
head->prev=NULL;
delete hapus;
}
cout<<endl<<endl;
tampil();
}
void hapus_belakang()
{
if (head==NULL)
cout<<"Kosong";
else if (head->next==NULL)
{
hapus=head;
head=NULL;
tail=NULL;
delete hapus;
}
else
{
hapus=tail;
tail=hapus->prev;
tail->next=NULL;
delete hapus;
}
cout<<endl<<endl;
tampil();
}
void tampil()
{
if (head==NULL)
cout<<"Kosong";
else
{
bantu=head;
while(bantu!=NULL)
{
cout<<" nama : "<<bantu->nama;
cout<<" umur : "<<bantu->umur;
cout<<" tinggi : "<<bantu->tinggi<<endl;
bantu=bantu->next;
}
}
getch();
}
void tambah_tengah()
{
int sisip;
cout<<"Masukan Posisi Sisip Anda : ";cin>>sisip;
bantu=head;
for(int i=1;i<sisip-1;i++)
{
bantu=bantu->next;
}
buat_baru();
bantu2=bantu->next;
bantu->next=baru;
baru->prev=bantu;
baru->next=bantu2;
bantu2->prev=baru;
}
void hapus_tengah()
{
int sisip;
cout<<"Masukan Posisi Sisip Anda : ";cin>>sisip;
bantu=head;
for(int i=1;i<sisip-1;i++)
{
bantu=bantu->next;
}
hapus=bantu->next;
bantu2=hapus->next;
bantu->next=hapus->next;
bantu2->prev=bantu;
delete hapus;
}
REFERENSI :
http://mudavih16.blogspot.co.id/2015/11/struktur-data-linked-list.html
