BAB
I
PENDAHULUAN
Kajian
struktur data merupakan kajian yang sangat penting dalam bidang informatika.
Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan
struktur data yang efisien yang dapat meningkatkan kinerja program.
Salah satu bentuk struktur data yang berisi kumpulan data yang
tersusun secara sekuensial, saling bersambungan, dinamis dan terbatas adalah
linked list (senarai berkait). Suatu 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.
Dikatakan single (singly) linked apabila hanya ada satu pointer yang
menghubungkan setiap node. single artinya field pointer-nya hanya satu buah
saja dan satu arah.
Linked list
adalah struktur data yang paling dasar. Linked list terdiri atas sejumlah
unsur-unsur dikelompokkan, atau terhubung, bersama-sama di suatu deret yang
spesifik. Linked list bermanfaat di dalam memelihara koleksi-koleksi data, yang
serupa dengan array.
Bagaimanapun juga, linked list
dan array mempunyai perbedaan. Memakai Linked list lebih bagus dibandingkan
dengan array/larik baik dalam banyak hal. Secara rinci, linked list lebih
efisien di dalam melaksanakan penyisipan-penyisipan dan
penghapusan-penghapusan. Linked list 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-last-access.
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 dengan node di sebelah
kita, yang juga bertipe struct tnode. Hal inilah yang menyebabkan next harus
bertipe struct tnode.
Secara umum linked list
dibedakan atas 2 macam,
yaitu :
1. Single
Linked List
2. Double
Linked List
BAB
II
LANDASAN
TEORI
Pada
array, apabila programmer ingin menyimpan data, programmer diharuskan untuk
mendefinisikan besar array terlebih dahulu, seringkali programmer
mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena
seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin
menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena
sifat array yang besarnya statik. Linked list adalah salah satu struktur data
yang mampu menutupi kelemahan tersebut.
Linked
list (list bertaut) adalah salah satu struktur data dasar yang sangat
fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka
programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan
array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan
secara dinamis pada saat pengoperasian program (run-time).
BAB III
PEMBAHASAN
1.
Single Linked List
Salah satu struktur data dinamis
yang paling sederhana adalah Senarai Berantai (Linked List), atau senarai satu
arah. Senarai Berantai sendiri punya makna sebagai kumpulan komponen yang
disusun secara berurutan dengan menggunakan bantuan pointer. Komponen-komponen
yang tersusun tersebut akan disebut sebagai simpul, sehingga pada senarai akan
terdapat banyak simpul, dan tiap simpulnya dapat dibagi menjadi dua bagian.
Bagian pertama dari simpul disebut dengan medan informasi, yang berisi
informasi/data yang fapat berupa record yanag akan diolah. Sedangkan
bagian yang kedua disebut sebagai medan penyambung (link field),
yang berisi alamat simpul berikutnya.
 |
|
Gambar 1.1. Ilustrasi
Linked List
Untuk memudahkan setiap pembahasan
selanjutnya, maka akan kita tetapkan untuk sebelah kiri simpul disebut sebagai
medan informasi dan sebelah kanan simpul disebut sebagai medan penyambung.
Perlu diketahui bahwa medan penyambung sebenarnya adalah suatu pointer yang
akan menunjuk ke simpul berikutnya, sehingga nilai dari medan ini dapat berupa
alamat lokasi simpul berikutnya ataupun dapat bernilai nil. Perlu
diingat bahwa setiap simpul terakhir dari linked list medan penyambung harus
bernilai nil.
Contoh dari
senarai berantai dengan 5 simpul :
Gambar 1.2. Senarai Berantai 5
simpul
Tampak dari Gambar
1.2 bahwa medan penyambung menunjuk ke simpul berikutnya, dan medan
penyambung pada simpul terakhir akan bernilai nil karena medan
penyambung tersebut tidak menunjuk kemanapun. Pada senarai berantai juga
terdapat 2 buah pointer awal dan akhir, kedua pointer ini berfungsi untuk
mempermudah dalam melakukan operasi pengolahan data pada senarai berantai,
seperti : pembacaan, pencarian, pengeditan, serta penghapusan data, pengertian
kedua pointer ini mungkin akan lebih jelas pada pembahasan selanjutnya.
Bentuk
umum pendeklarasian single linked list :
Penjelasan
: nmlis : sebuah pointer yang menunjuk ke sebuah
record.
nmrecord : nama record yang berisi variabel penyimpan
data dan berisi medan penyambung.
nmvar1 : variabel yang akan berfungsi sebagai
penyimpan data
nmvarn : variabel yang berfungsi sebeagai media
penyambung.
Contoh penulisan
Single Linked List :
Type simpul = ^data;
data = record
info : char;
kait : simpul;
end;
var awal,akhir,baru : simpul;
Dengan contoh pendeklarasian sederhana
tersebut, maka operasi-operasi pengolahan data dapat dilakukan seperti pada
contoh program berikut yang berfungsi untuk menambah dan menampilkan data
menggunakan linked list.
Program diatas pertama kali setelah
pendeklarasian simpul adalah melakukan pemberian nilai nil terhadap
variabel awal, karena pada saat program pertama dijalankan data belum ada
sehingga variabel awal belum menunjuk kesuatu tempat. Tampak pada program
terdapat 3 proses, demikian ilustrasi ke 3 proses tersebut :
Proses
1
: Proses untuk memberikan nilai pada variabel awal dan akhir saat pertama
penginputan data.
 |
|
Tampak
bahwa medan penyambung dari bantu (bantu^.kait) dibuat nilainya nil
karena data masih satu sehingga berperan sebagai awal dan akhir linked list.
Proses
2 :
Proses untuk memberikan nilai pada akhir untuk menunjuk ke-bantu yang baru saja
diinputkan.
 |
Pada
gambar a simpul bantu baru dibentuk. Gambar b menjelaskan akhir
akan menunjuk ke bantu yang baru. Gambar c menjelaskan peberian
nilai nil kepada bantu^.kait, karena bantu tersebut berada
pada posisi terakhir. Tampak pada gambar bahwa yang berpindah arah hanya akhir
dan bukan awal, hal ini menandakan bahwa penambahan dilakukan di belakang
linked list. Perlu diingat bahwa dalam linked list terdapat peraturan-peraturan
sebagai berikut :
- awal akan selalu menunjuk ke awal linked list, dan akhir akan selalu menunjuk ke akhir linked list, sekalipun penambahan data dilakukan.
- Setiap simpul yang terakhir dari linked list nilai dari medan penyambung harus selalu bernilai nil.
Proses
3 :
Pada proses ini bantu akan membaca simpul dan menampilkan hasilnya dari awal
sampai akhir linked list.
Operasi pada Senarai Berantai (Single Linked
List)
1. Menambah
Simpul di Belakang
Untuk contoh dan ilustrasi menambah
dibelakang sudah dijelaskan pada contoh program Proses 2.
2. Menambah
Simpul di Depan
Ilustrasi :
Bentuk
penulisan dalam bentuk program :
new(bantu);
bantu^.nama := ‘Alung’;
bantu^.kait := awal;
awal := bantu;
3. Menambah
Simpul di Tengah
Ilustrasi :
Bentuk
penulisan dalam bentuk program :
new(bantu);
bantu^.nama := ‘Alung’;
bantu^.kait := bantu2^.kait;
bantu2^.kait := bantu;
4. Menghapus
Simpul di Awal
Ilustrasi :
Bentuk penulisan
dalam bentuk program :
bantu := awal;
awal := bantu^.kait;
dispose(bantu);
5. Menghapus
Simpul di Tengah
ilustrasi
:
Bentuk penulisan
dalam bentuk program atau algoritma :
While (bantu^.kait<>nil) or
(bantu^.nama<>‘Budi’) do
bantu := bantu^.kait;
If
(bantu <> nil) then
Begin
bantu2^.kait := bantu;
bantu2^.kait := bantu^.kait;
dispose(bantu);
End;
6. Menghapus
Simpul di Akhir.
ilustrasi
:
Bentuk penulisan
dalam bentuk program :
bantu := akhir;
akhir^.kait := bantu;
dispose(bantu);
akhir^.kait := nil;
2.
Double Linked List,
Double Linked List menggunakan
tekhnik yang sama dengan Single Linked List. Perbedaan utamanya adalah simpul
pada Double Linked List dapat menunjuk kedapan atau kebelakang. Hal ini akan
mempermudah pembacaan (bisa dilakukan dari kiri ke kanan atau sebalinya),
penambahan simpul baru atau penghapusan simpul bisa dilaksanakan untuk
simpul-simpul yang terletak disebelah kiri atau kanan dari pointer yang
diketahui.
Gambar 1.3. Double Linked List
Contoh
pendeklarasian Double Linked List :
Type simpul = ^data;
data = record
nama : string;
depan,belakang : simpul;
End;
Var awal,akhir,baru : simpul;
Tampak dari contoh pendeklarasian
tersebut pada bagian record terdapat dua buah variabel yang bertipe
pointer (simpul) yaitu depan dan belakang. Hal inilah yang
mengakibatkan Senarai Berantai tersebut disebut sebagai Double Linked List.
Pada deklarasi di atas pointer blakang adalah pointer untuk menunjuk ke simpul
sebelumnya, atau simpul sebelah kiri, pointer depan adalah pointer untuk
menunjuk ke simpul sesudahnya atau simpul sebelah kanan.
Operasi
pada Senarai Berantai Ganda (Double Linked List).
1. Menambah
Data
Ilustrasi :
Bentuk penulisan dalam bentuk program :
akhir^.depan := baru;
baru^.belakang := akhir;
baru^.depan := nil;
akhir := baru;
2. Membaca
simpul/data
Karena memiliki pointer yang dapat
menunjuk ke depan dan ke belakang, operasi pembacaan data dilakukan dari kedua arah, yaitu dari depan dan
belakang.
Membaca dari belakang :
Penulisan
dalam bentuk program atau algoritma :
bantu
:= awal;
While
bantu <> nil do
Begin
Writeln (‘nama : ‘,bantu^.nama);
bantu := bantu^.depan;
End;
Fungsi dari penulisan
program ini adalah untuk menjalankan pointer bantu dari awal
hingga akhir list serta menampilkan isi dari simpul yang dilewati.
Membaca dari depan :
Penulisan
dalam bentuk program :
bantu := akhir;
While bantu <> nil do
Begin
Writeln (‘nama
: ‘,bantu^.nama);
bantu :=
bantu^.belakang;
End;
Perintah-perintah
di atas adalah untuk menjalankan pointer bantu dari akhir hingga
ke awal senarai, serta menampilkan isi dari variabel nama pada setiap simpul
yang dilewatinya.
3.
Soal Latihan
- Buatlah program menggunakan methode Single Linked List untuk menginputkan nama, seperti berikut berikut :
Menu :
1.
Tambah Data
2.
Hapus Data Depan
3.
Hapus Data Belakang
4.
Cetak Data
Pilh Menu [1/2/3/4] :
Menu 1 :
Inputkan Nama : Alung
Kembali ke menu.
Menu 2 :
Hapus
Data Dari Depan List
Kembali ke menu.
Tambahkan
menu lain yang perlu dipergunakan dalam program.
BAB IV
KESIMPULAN
Simpul adalah semacam tipe
data yang kita buat sendiri sebagaimanan nama tipe yang telah disediakan oleh
bahasa pemrograman.
Info adalah tempat penyimpanan
data dengan tipe yang berbeda-beda sesuai keinginan.
Link adalah tempat penyimpanan
alamat simpulnya (pointer).
Linked list adalah sebuah
struktur untuk menyimpan data yang bersifat dinamik
Beberapa operasi dapat
diterapkan pada linked list seperti sisip(insert),hapus(delete)
Operasi-operasi yang ada pada
linked list relatif lebih sulit jika dibandingkan dengan operasi-operasi pada
struktur yang statis
Null adalah suatu kondisi
khusus dimana pointer itu belum di set dengan sebuah address tertentu, artinya
pointer tidak mrnunjuk ke alamat manapun.
DAFTAR PUSTAKA
Suarga, Drs, M.Sc.,M.Math.,Ph.D. 2012 “Algoritma
dan Pemrograman”. Yogyakarta: Andi.
Sjukani, Moh.2012“ Struktur Data (Algoritma dan
Struktur Data dengan C,C++”. Jakarta: Mitra Wacana Media.
Tidak ada komentar:
Posting Komentar