Struktur Data Jenis Senarai Berantai
(Linked List)
Oleh: Amira Najma
11.PENGERTIAN
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
22.JENIS - JENIS LINKED LIST
Ada beberapa jenis linked list, yaitu :
1.
Single Linked List
2.
Double Linked List
3.
Circular Linked List
4.
Multiple Linked List
·
Single Linked List
Single Linked List merupakan suatu
linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer
tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke
NULL.
Contoh :
Contoh codingannya :
struct Mahasiswa
{
char
nama [25];
int
usia;
struct
mahasiswa *next;
}
*head, *tail;
· Double Linked List
Double Linked
List merupakan suatu linked list yang memiliki dua variabel pointer yaitu
pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node
sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
Contoh :
Contoh
codingannya :
struct Mahasiswa
{
char
nama [25];
int usia;
struct
mahasiswa *next, *prev;
}
*head, *tail;
·
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:
o Circular
Single Linked List
o Circular
Double Linked List
·
Multiple Linked List
Multiple Linked List merupakan suatu
linked list yang memiliki lebih dar 2 buat variabel pointer.
Contoh :
33. Operasi - Operasi yang ada pada Linked
List
· Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalamsuatu linked list.
Istilah Insert berarti menambahkan sebuah simpul baru ke dalamsuatu linked list.
· IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
Fungsi ini menentukan apakah linked list kosong atau tidak.
· Find First
Fungsi
ini mencari elemen pertama 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 ditunjuk oleh now. Jika yang dihapus adalah elemen
pertama dari linked list (head), head akan berpindah ke elemen berikut.
· Delete Head
Fungsi
ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
· Clear
Fungsi
ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda
ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya,
data-data yang dialokasikan ke memori pada program sebelumnya akan tetap
tertinggal di dalam memori.
44.
Algoritma dan contoh program LINKED LIST
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);
}
#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;
}
