1.
Tujuan
Mahasiswa mampu
menjelaskan pengertian queue dan dequeue
·
Mahasiswa dapat melakukan perancangan aplikasi menggunakan
struktur Linked List (Senarai Berkait)
·
Mahasiswa mampu melakukan analisis pada algoritma Single &
Double Linked List yang dibuat
·
Mahasiswa mampu mengimplementasikan algoritma Single &
Double Linked List pada sebuah aplikasi secara tepat dan efisien
2.
Tujuan
Instruksional Khusus
·
Mahasiswa dapat menjelaskan mengenai Single & Double Linked
List
·
Mahasiswa dapat membuat dan mendeklarasikan Abstraksi Tipe Data Single
& Double Linked List
·
Mahasiswa mampu menerapkan operasi Single Linked List Non
Circular & Single Linked List Circular
·
Mahasiswa mampu menerapkan Double Linked List Non Circular
& Double Linked List Circular
3.
Dasar
Teori
Pengertian Linked List
Salah
satu bentuk struktur data yang berisi kumpulan data yang tersusun secara
sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait (linked
list). Suatu senarai berkait (linked list) adalah suatu simpul (node)
yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu
simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai
satu atau lebih elemen struktur atau class yang berisi data. Secara
teori, linked list adalah sejumlah node yang dihubungkan secara linier
dengan bantuan pointer. Senarai berkait lebih efisien di dalam
melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan. Senarai berkait
juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan
yang dialokasikan pada runtime. Karena di dalam banyak aplikasi, ukuran
dari data itu tidak diketahui pada saat kompile, hal ini bisa merupakan suatu
atribut yang baik juga. Setiap node akan berbentuk struct dan
memiliki satu buah field bertipe struct yang sama, yang berfungsi
sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan
cara first-create-first-access ataupun first-create lastaccess.
Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama
next, yang bertipe struct tnode. Hal ini sekilas dapat
membingungkan. Namun, satu hal yang jelas, variabel next ini akan
menghubungkan kita denga node di sebelah kita, yang juga bertipe struct
tnode. Hal inilah yang menyebabkan next harus bertipe struct
tnode.
Bentuk Umum :
infotype à sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen
list
next à address dari elemen berikutnya (suksesor) .
Jika L adalah list, dan P
adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi : first (L)
Sebelum digunakan harus dideklarasikan terlebih dahulu :
#define First(L)
(L)
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan
notasi :
info(P)deklarasi #define info(P) P->info
next(P)deklarasi #define next(P) P->next
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define
Nil Null
Operasi-operasi Linked List
§ Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam
suatu linked list.
§
IsEmpty
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 berikutnya.
§
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.
a.
Single Linked
List (Senarai berkait tunggal)
Single linked list adalah apabila hanya ada satu pointer yang
menghubungkan setiap node (satu arah “next”).
§
Single Linked
List non Circular
Pembuatan
struct bernama tnode berisi 2 field, yaitu field data bertipe integer dan field
next yang bertipe pointer dari tnode. Deklarasi node dengan struct:
Asumsikan kita memiliki sejumlah node yang selalu menoleh
ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, kita bisa
mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan
memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain
adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain
depan adalah variabel next. Sampai di sini, kita baru saja
mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan
mendeklarasikan beberapa variabel pointer bertipe struct tnode.
Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list,
node aktif dalam linked list, dan node sementara yang akan
digunakan dalam pembuatan node di linked list. Berikan nilai awal
NULL kepada mereka. Deklarasi node untuk beberapa keperluan, seperti
berikut ini:
struct tnode
*head=NULL, *curr=NULL, *node=NULL;
Dengan demikian, sampai saat ini, telah dimiliki tiga node.
Satu sebagai kepala (head), satu sebagai node aktif dalam linked
list (curr) dan satu lagi node sementara (node). Untuk
mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan.
Head akan berada pada pangkal anak panah, dan node node berikutnya akan
berbaris ke arah bagian anak panah yang tajam.
Apabila
diperhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Node
terakhir akan diberikan nilai NULL. Dengan demikian, setiap node kebagian
jatah.
int i;
for (i=0; i<5; i++)
{
node = (struct tnode *)
malloc (sizeof(struct
tnode));
node -> data = i;
if (head == NULL)
{
head = node;
curr = node;
}else
{
curr -> next = node;
curr = node;
}
}
curr -> next = NULL;
Berikut
adalah penjelasan kode-kode pembuatan singly linked list tersebut.
Pertama-tama, akan dibuat perulangan dari 0 sampai 4, yang dimaksudkan untuk
membuat lima buah node yang masing-masing field data nya berisikan nilai dari 0
sampai 4. Pembuatan node dilakukan dengan fungsi malloc()
for (i=0; i<5; i++)
{
node = (struct tnode *)
malloc (sizeof(struct
tnode));
node -> data = i
...
... }
Setelah itu,
perlu dibuat node dan penghubung. Pertama-tama, akan diuji apakah head bernilai
NULL. Kondisi head bernilai NULL hanya terjadi apabila belum dimiliki satu node
pun. Dengan demikian, node tersebut akan dijadikan sebagai head. Node aktif
(curr), juga kita dapat dari node tersebut. Kalau head tidak bernilai NULL
alias telah dimiliki satu atau lebih node, yang pertama dilakukan adalah
menghubungkan pointer next dari node aktif (curr) ke node yang baru saja
dibuat. Dengan demikian, baru saja dibuat penghubung antara rantai lama dengan
mata rantai baru. Atau, dalam permainan kereta api, pemain paling depan dalam
barisan lama akan menempelkan tangannya pada bahu pemain yang baru bergabung.
Node aktif (curr) kemudian dipindahkan ke node yang baru dibuat.
§
Single Linked
List Circular
Hampir sama dengan single linked list non circular, bahwa
dibutuhkan sebuah kait untuk menghubungkan node-node data yang ada, dimana pada
node terakhir atau tail yang semula menunjukkan NULL diganti dengan menunjuk ke
kepala atau head. Dimana inisialisasi senarai berkait tunggal sirkular
menggunakan struc adalah sebagai berikut: Deklarasi Single Linked List
Circular:
Menambah node
dan membuat tail dari single linked list circular
Deklarasi
penambahan node baru:
Menyisipkan
Node baru
Deklarasi
menyisipkan node baru menggunakan sintak berikut:
Void main()
{
node = new tnode;
node->next =
head->next;
head->next = node;
}
Menghapus
Node dari Single Linked List Circular
Deklarasi
menghapus node dari single linked list circular, menggunakan sintaks berikut:
Void main()
{
hapus = new tnode;
if( head != tail)
{
hapus = head;
head = head->next;
tail->next = head;
delete hapus;
}else
{
head = NULL;
tail = NULL;
}
}
b.
Double Linked List (Senarai berkait ganda)
Double Linked List adalah elemen-elemen
yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas
baik di depan atau belakang. Elemen double linked list terdiri dari tiga bagian
:
1.
Bagian data informasi
2.
Pointer next yang menunjuk ke elemen berikutnya
3.
Pointer prev yang menunjuk ke elemen sebelumnya
§
Double Linked List non Circular
Setiap node pada linked list mempunyai field yang berisi data dan
pointer ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node baru,
mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya, pointer
prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node
selanjutnya pada list.
Deklarasi node dibuat dari struct berikut ini :
typedef struct TNode{
int data;
Tnode *next;
Tnode *prev;
};
Double Linked List Non Circular dengan HEAD membutuhkan satu buah
variabel pointer, yaitu: head. Head akan selalu menunjuk pada node pertama.
Function
untuk mengetahui kosong tidaknya DLLNC
int
isEmpty(){
if(head ==
NULL) return 1;
else return
0;
}
Penambahan
data di depan
Penambahan
node baru akan dikaitkan di ode 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.
Fungsi
Menambah Di Depan
void
insertDepan(int databaru){
TNode
*baru;
baru =
new TNode;
baru->data
= databaru;
baru->next
= NULL;
baru->prev
= NULL;
if(isEmpty()==1){
head=baru;
head->next
= NULL;
head->prev
= NULL;
}
else {
baru->next
= head;
head->prev
= baru;
head =
baru;
}
cout<<”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.
Fungsi penambahan Node ke belakang :
Void insertBelakang (int databaru){
Tnode *baru, *bantu;
Baru = new Tnode;
baru->data = databaru;
baru->next = NULL;
baru->prev = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
head->prev = NULL;
}
else{
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next
}
bantu->next = baru;
baru->prev = bantu;
}
Cout<<”Data masuk\n”;
Cout<<”Data masuk\n”;
}
Ilustrasi Penambahan Node di Belakang
4.
Latihan
Praktikum
Latihan
Algoritma dan
Struktur Data
Nama
Program : Single Linked List Non Circular
Syntax :
#include <iostream>
#include <conio.h>
#include <iomanip> //setw()
#include <stdlib.h>
using namespace std;
struct node
{
int
data;
node*
next; //untuk menghubungkan dengan node lain, tipe data dibuat sama seperti
aturan penggunaan pointer
};
node* head;
node* tail;
node* curr;
node* entry;
node* del;
void inisialisasi()
{
head =
NULL;
tail =
NULL;
}
void input(int dt)
{
entry =
(node* )malloc(sizeof(node)); //alokasi memori
entry->data
= dt;
entry->next
= NULL;
if(head==NULL)
{
head
= entry;
tail
= head;
}
else
{
tail->next
= entry;
tail
= entry;
}
}
void hapus()
{
int
simpan;
if(head==NULL)
{
cout<<"\nlinked
list kosong, penghapusan tidak bisa dilakukan"<<endl;
}
else
{
simpan
= head->data;
cout<<"\ndata
yang dihapus adalah"<<simpan<<endl;
//hapus
depan
del
= head;
head
= head->next;
delete
del;
}
}
void cetak()
{
curr =
head;
if(head
== NULL)
cout<<"\ntidak
ada data dalam linked list"<<endl;
else
{
cout<<"\nData
yang ada dalam linked list adalah"<<endl;
cout<<setw(6);
while(curr!=NULL)
{
cout<<curr->data<<"->";
curr
= curr->next;
}
cout<<endl;
}
}
void menu()
{
char
pilih, ulang;
int
data;
do
{
system("cls");
cout<<"SINGLE
LINKED LIST NON CIRCULAR"<<endl;
cout<<"-------------------------------"<<endl;
cout<<"Menu
: "<<endl;
cout<<"1.
Input data"<<endl;
cout<<"2.
Hapus data"<<endl;
cout<<"3.
Cetak data"<<endl;
cout<<"4.
Exit"<<endl;
cout<<"Masukkan
pilihan Anda : ";
cin>>pilih;
switch(pilih)
{
case
'1' :
cout<<"\nMasukkan
data : ";
cin>>data;
input(data);
break;
case
'2' :
hapus();
break;
case
'3' :
cetak();
break;
case
'4' :
exit(0);
break;
default
:
cout<<"\nPilih
ulang"<<endl;
}
cout<<"Kembali
ke menu?(y/n)";
cin>>ulang;
}while
(ulang=='y' || ulang=='Y');
}
int main()
{
inisialisasi();
menu();
return
EXIT_SUCCESS;
}
Tampilan Output :
Penjelasan Program :
Program
diatas merupakan program Single Linked List yang digunakan untuk menginput
data, menghapus data, mencetak data, dan exit. Pengguna akan diminta
untuk memilih menu sesuai yang diinginkan. Jika pilih 1 maka
untuk menginpukan data, lalu jika pilih 2 maka untuk menghapus data, jika pilih
3 maka untuk mencetak data dan jika pilih 4 maka exit. Program selesai.
Tugas Praktikum
Algoritma dan
Struktur Data
Nama
Program : Troubleshoot Linked List
Syntax :
#include <stdio.h>
#include <stdlib.h>
//denisikan struct
struct SNode{
int
data;
struct
SNode *next;
struct
SNode *before;
};
struct SNode *n_awal, //node awal dari linked list
*n_tampil, //node bantu untuk tampilkan data
*n_bantu; //node bantu untuk insert node
baru
int
iterasi;
//inisialisasi
linked list
void inisialisasi(){
n_awal
= NULL;
}
//tampilkan
linked list
void
tampil_list(){
n_tampil
= n_awal;
while(n_tampil!=NULL){
printf("%d
,", n_tampil->data);
n_tampil
= n_tampil->next;
}
printf("\n");
}
//method
untuk insert node baru
void
insert_node(int data){
//node
baru yang akan di insert
struct
SNode *n_insert;
n_insert
= (struct SNode*)malloc(sizeof(struct SNode));
n_insert->data
= iterasi;
n_insert->next
= NULL;
n_insert->before
= NULL;
//kondisi
linked list masih kosong
if(n_awal
== NULL){
n_awal
= n_insert;
}else{
n_bantu
= n_awal;
//cari
node terakhir
while(n_bantu->next
!= NULL){
n_bantu
= n_bantu->next;
}
//hubungkan
node terakhir dengan node baru
if(n_bantu->next==NULL)
{
n_bantu->next
= n_insert;
n_insert->before
= n_bantu;
}
}
}
int
main(int argc, char *argv[])
{
inisialisasi();
for(iterasi
= 11; iterasi<=15; iterasi++)
{
insert_node(iterasi);
}
tampil_list();
system("PAUSE");
return
0;
}
Tampilan Output :
Penjelasan Program :
program diatas
adalah program setelah dilakukan troubleshot dan ditemukan kesalah pada program
yaitu : pertama pada
while(n_tampil !== NULL) pada
tanda == itu adalah operator untuk tes kesetaraan dan mengembalikan boolean dan
tanda tersebut error karena tidak cocok, seharusnya adalah = tanda sama dengan
hanya satu yang bermakna operator penugasan dan bila dijalankan akan hilang
error nya karena cocok dengan fungsi sebelumnya. Kedua adalah n_tampil =
n_tampil->before; syntax
tersebut salah karena ada before yang seharusnya next agar dapat menampilkan
sampai nilai maximum yang telah dideklarasikan.
Tugas Rumah
Algoritma dan
Struktur Data
Nama
Program : Program Linked List Wahana Jatim Park
Malang
Syntax :
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<ctype.h>
using namespace std;
struct Node
{
int data;
Node *next;
};
Node *head, *tail;
void menu();
void LinkedList();
void penutup();
void inisialisasi();
void insertData();
void removeData();
void bersih();
void tampil();
void line()
{
for(int i=0; i<25; i++)
cout<<"__";
cout<<endl;
}
int main()
{
char MENU;
int ulangMetode = 1;
do
{
system("cls");
system("color A0");
line();
line();
printf(" === ===
====== ==== ===
======= \n");
printf(" === ===
=== === === ==
== === === \n");
printf("
======== === ===
=== === ===
======= \n");
printf(" === ===
=== === ===
=== === \n");
printf(" === ===
===== === ===
======= \n");
line();
line();
printf("1. pendaftaran permainan Wahana Jatim Park Malang
\n");
printf("2. EXIT \n");
printf("=====================================\n");
printf(">> Masukkan Pilihan : ");
MENU = getche();
printf("\n");
getch();
switch(MENU)
{
case '1' :
LinkedList();
break;
case '2' :
penutup();
break;
default :
{
puts("\nKode yang dimasukkan salah\n");
puts("Press any key untuk kembali");
getch();
}
break;
}
}
while(ulangMetode == 1);
}
void menu()
{
system("cls");
system("color
57");
printf("\n\n");
printf(" Pendaftaran Antrian Wahana Jatim Park Malang \n");
printf("=========================================\n");
printf(" 1. masukan
antrian penumpang \n");
printf(" 2. mulai masuk
permainan \n");
printf(" 3.
memberangkatkan semua antrian \n");
printf(" 4. menampilkan
semua antrian \n");
printf(" 5. kembali ke
menu utama \n");
printf(" 6. keluar \n");
printf("=========================================\n");
}
void LinkedList()
{
char pilihMenu;
int ulang = 1;
do
{
menu();
printf(">> Pilihan
Anda : ");
pilihMenu = getche();
printf("\n");
switch(pilihMenu)
{
case '1' :
insertData();
break;
case '2' :
removeData();
break;
case '3' :
bersih();
break;
case '4' :
tampil();
break;
case '5' :
main();
break;
case '6' :
penutup();
break;
default :
{
puts("Input Menu
Salah!\n");
puts("Press any key
untuk kembali");
getch();
}
break;
}
}
while(ulang == 1);
}
void inisialisasi()
{
head = NULL;
tail = NULL;
}
void insertData()
{
int angka;
Node *nodeBaru;
nodeBaru = new Node;
cout<<"Masukkan Nomor Karcis : ";
cin>>angka;
nodeBaru->data = angka;
nodeBaru->next = NULL;
if(tail == NULL)
{
head = tail = nodeBaru;
tail->next = NULL;
}
else
{
tail->next = nodeBaru;
tail = nodeBaru;
}
printf("Data %i masuk!\n\n", angka);
puts("Press any key untuk kembali");
getch();
system("cls");
}
void removeData()
{
int elDel;
Node *del, *prevTail;
del = new Node;
if(tail != NULL)
{
del = tail;
elDel = del->data;
if(tail == head)
{
inisialisasi();
}
else
{
prevTail = head;
while(prevTail->next != tail)
prevTail = prevTail->next;
tail = prevTail;
tail->next = NULL;
}
delete del;
printf("antrian %i masuk ke permainan wahana jatim
park\n\n", elDel);
}
else
{
puts("antrian Kosong! Tidak ada antrian yang dapat
bermain!\n");
}
puts("Press any key untuk kembali");
getch();
system("cls");
}
void bersih()
{
Node *clear, *point;
if(tail != NULL)
{
point = head;
while(point != NULL)
{
clear = point;
point = point->next;
delete clear;
}
inisialisasi();
puts("Semua antrian masuk dalam permainan wahana jatim
park\n");
}
else
puts("antrian Masih Kosong!\n");
puts("Press any key untuk kembali");
getch();
system("cls");
}
void tampil()
{
Node *see;
see = head;
if(tail != NULL)
{
puts("Daftar Data Antrian permainan wahana jatim park
:");
puts("");
while(see != NULL)
{
printf("%i ", see->data);
see = see->next;
}
puts("\n");
}
else
puts("antrian kosong!\n");
puts("Press any key untuk kembali");
getch();
system("cls");
}
void penutup()
{
printf("\n\n\tTERIMA KASIH\n\n");
exit(0);
}
Tampilan Output :
Penjelasan Program :
Program diatas digunakan untuk mendaftar permainan di wahana jatim park
malang. Tampilan pertama merupakan home, dimana ada 2 pilihan yaitu 1 pendaftaran
permainan wahana jatim park malang
untuk mendaftar permainan, dan yang ke-2 exit untuk keluar. Jika pilih menu 1 maka akan muncul
beberapa pilihan yaitu no 1 untuk memasukkan antrian, no 2 maka untuk memulai masuk permainan, no 3 untuk
memberangkatkan semua antrian, no 4 untuk menampilkan semua antrian dan no 5
untuk kembali ke home. Dan terakir no 6 untuk
mengakhiri program
tersebut. Program diatas memiliki banyak sekali pilihan karena memang kebutuhan
maka dari itu saya menggunakan system cls agar tampilan tidak menumpuk-numpuk.
KESIMPULAN
1.
Pada struktur data linked
list ini terdapat 2 macam, yaitu single linked list (senarai berkait tunggal),
double linked list (senarai berkait ganda.
2.
Single linked list yaitu
bila stuctur data sebuah node berikutnya dalam sebuah senarai maka senarai
tersebut dinamakan senarai tunggal, senarai tunggal tiap-tiap node yang berdiri
atas dua elemen yaitu data integer dan elemen rujukan ke node berikutnya
3.
Double linked list memiliki
2 pointer penunjuk yaitu next dan prev
4.
Dalam linked list dapat menambah node baru. Di
tengah ,depan , dan belakang
5.
Dapat menghapus sebuah
node dari linked list circular
