Contoh Skripsi Bab II Struktur Data
Pada sebagian hal mengenai type data, struktur data dan type data abstrak sepertinya mempunyai perbedaan arti. Dalam bahasa pemrograman, type data dari suatu variabel adalah merupakan kumpulan nilai yang dapat dimuat oleh variable. Sebagai contoh, suatu variabel Boolean hanya dapat bernilai True dan False, tidak boleh ada nilai yang lain. Ada beberapa type data yang dikenal, contohnya dalam pemrograman Pascal antara lain adalah integer, real , Boolean, dan character.
Type data abstrak merupakan suatu model matematika yang disertai oleh sekumpulan operasi terhadap suatu model. Dalam hal ini diasumsikan bahwa pada suatu operasi dasar minimal ada sebuah type data abstrak operand atau minimal ada sebuah tipe data abstrak. Untuk merepresentasikan suatu model matematis dari suatu type data abstrak, digunakan struktur data yang berisikan sekumpulan variabel yang bisa terdiri atas beberapa type data dan mempunyai bermcam-macam jenis dan cara relasi.
Sel merupakan satuan dasar di dalam pembentukan struktur data. Setiap sel dapat dibentuk atas gabungan beberapa type data abstrak yang lain. Sebuah struktur data dibangun dengan memberi nama rangkaian sel-sel ini, ataupun merepresentasikan hubungan antar dan dalam sel. Metode yang paling sederhana didalam pengelompokan sel adalah array. Array terdiri atas serangkaian sel bertype data tertentu dan nilai dari suatu sel dapat diambil dengan menyebutkan indeks sel tersebut, yaitu letak sel dalam array. (Gortap Sinaga, 2006)
II.2. Pointer
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama program dieksekusi. Untuk itu diperlukan satu type data yang bisa digunakan untuk mengalokasikan pengingat secara dinamis, type data ini disebut type data pointer.
Pointer merupakan sel yang nilainya merupakan alamat sel tertentu. Sel tersebut dapat berupa data atau berupa pointer juga. Jadi setiap elemen di dalam Linked List selalu berisi pointer (Insap Santoso,1992: 89-91).
II.2.1. Deklarasi Pointer
Seperti halnya type data yang lain, type pointer biasanya dideklarasikan pada bagian deklarasi type.
Bentuk umum deklarasi pointer adalah:
type pengenal = ^simpul;
simpul = tipe;
dengan:
pengenal: nama pengenal yang menyatakan data bertipe pointer.
simpul : nama simpul
tipe : tipe data dari simpul (Insap Santoso, 1992: 91-92).
II.2.2. Operasi Pada Pointer
Secara umum ada dua operasi dasar yang bisa dilakukan dengan menggunakan data yang bertipe pointer. Operasi yang pertama adalah mengkopi pointer, sehingga sebuah simpul akan ditunjuk oleh lebih dari sebuah pointer. Operasi yang kedua adalah mengkopi isi simpul, sehingga dua atau lebih simpul yang ditunjuk oleh pointer yang berbeda mempunyai isi yang sama. Syarat yang harus dipenuhi untuk kedua operasi ini adalah bahwa pointer-pointer yang akan dioperasikan harus mempunyai deklarasi yang sama.
Contoh deklarasi pada operasi pointer:
Type Simpul = ^Data;
Data = record
Nama : string;
Alamat : string;
Berikut : Simpul;
end;
var T1, T2 : Simpul;
Pada deklarasi di atas, pointer T1 dan T2 mempunyai daklarasi yang simpul sama, sehingga memenuhi syarat untuk kedua operasi di atas (Insap Santoso,1992: 96).
II.3. Senarai Berantai (Linked List)
Linked List merupakan suatu struktur data yang terdiri atas rangkaian elemen yang saling berhubungan atau berkaitan, dimana setiap elemen dihubungkan dengan elemen lainnya melalui pointer. Node/simpul terdiri atas dua bagian yaitu bagian data dan bagian pointer yang menunjuk ke simpul berikutnya.
II.3.1. Pembagian Linked List
Secara umum Linked List dibedakan atas 2 macam yaitu:
1. Single Linked List
Single Linked List mempunyai satu pointer untuk setiap node/simpul yang menunjuk ke node berikutnya, artinya hanya punya satu arah. Single Linked List ini terbagi atas dua bagian yaitu:
a) Linier Single Linked List
Linier Single Linked List terdiri dari dua kata yaitu single yang artinya field pointernya hanya satu saja dan satu arah dan linked list yang artinya node-node tersebut saling berhubungan satu sama lain. Dari dua pengertian di atas dapat disimpulkan bahwa:
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 Nil yang akan digunakan sebagai kondisi berhenti pada setiap pembacaan linked list.
b) Circular Single Linked List
Circular Single Linked List adalah senarai berantai biasa dimana pointer pada simpul terakhir diarahkan kembali ke simpul pertama (Insap Santoso, 1992:135).
2. Double Linked List
Double Linked List sendiri mempunyai dua buah pointer yang menunjuk ke node berikutnya, artinya punya dua arah (Paulus Bambangwirawan, 2004: 48).
Salah satu kelemahan Single Linked List adalah Pointer hanya dapat bergerak satu arah saja, yaitu maju atau ke kanan, sehingga pencarian hanya dapat dilakukan satu arah hanya. Untuk mengatasi kelemahan Single Linked List dapat digunakan Double Linked List yang terdiri dari tiga bagian, yaitu bagian data dan bagian pointer kiri dan bagian pointer kanan yang menunjuk ke simpul berikutnya. Double Linked List ini juga dapat dibagi dalam dua jenis yaitu:
a) Linier Double Linked List
Bagian pointer kiri dan bagian pointer kanan dari Linier Double Linked List ini akan menunjuk ke simpul berikutnya, dengan adanya dua pointer pada linked list ini maka Linier Double Linked List sangat fleksibel digunakan dibandingkan dengan Linier Single Linked List.
b) Circular Double Linked List
Circular Double Linked List tidak mengandung Nil dimana Kanan Simpul terakhir menunjuk simpul pertama dan Kiri Simpul pertama menunjuk simpul terakhir sehingga membentuk semacam cincin. Dan Circular Double Linnked List ini mempunyai kelebihan yaitu mempermudah mengakses sembarang simpul dimulai dari sembarang simpul.
II.3.2. Operasi Pada Senarai Berantai (Linked List)
II.3.2.1. Menambah Simpul
Operasi pertama yang terdapat pada senarai berantai adalah operasi menambah simpul dimana operasi ini dapat dilakukan di depan, di tengah, ataupun di belakang Linked List tersebut.
II.3.2.1.1. Menambah Simpul Belakang
Pada operasi penambahan simpul belakang dimana elemen baru selalu pada posisi belakang. Jika Linked List belum ada maka Simpul Baru menjadi Linked List.
a. Operasi Penambahan simpul belakang pada Single Linked List
Operasi penambahan belakang ini dapat dibagi dalam dua bagian yaitu:
1. Operasi Penambahan simpul belakang pada Linier Single Linked List
Operasi penambahan simpul belakang pada Linier Single Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Elemen baru selalu pada posisi belakang
b) Jika Linked List belum ada maka Simpul Baru menjadi Linked List
c) Penambahan simpul dilakukan dengan:
1) Buat satu Pointer yang dapat digerakkan misalnya Bantu yang menunjuk simpul pertama dan Linked (Bantu:=Awal)
2) Gerakkan pointer Bantu hingga ke simpul paling Belakang dari Linked List (dilakukan perulangan hingga Bantu^.Next=Nil)
d) Sambungkan Linked List dengan Simpul baru (Bantu^.Next=Baru)
2. Operasi Penambahan simpul belakang pada Circular Single Linked List
Operasi penambahan simpul belakang pada Linier Single Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
Elemen baru selalu pada posisi belakang
Jika Linked List belum ada maka Simpul Baru menjadi Linked List
Jika Linked List sudah ada, maka:
1) Pointer dari baru menunjuk ke Awal
Sambungkan Linked List dengan Simpul baru dimana simpul akhir menunjuk ke simpul awal.
b. Operasi Penambahan simpul belakang pada Double Linked List
Operasi penambahan simpul belakang ini dapat dibagi dalam dua bagian yaitu:
1. Operasi Penambahan simpul belakang pada Linier Double Linked List
Operasi penambahan simpul belakang pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul ditambah sebagai Simpul belakang atau simpul paling kanan
b) Penyisipan simpul ada kemungkinan simpul menjadi Awal pembentukan Linked List.
2. Operasi Penambahan simpul belakang pada Circular Double Linked List
Operasi penambahan simpul belakang pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Jika Linked List belum ada maka Simpul Baru menjadi awal Linked List (Awal:=Baru)
b) Jika Linked List sudah ada, maka:
1) Kanan dari Baru menunjuk Awal (Baru^.Kanan:=Awal)
2) Kiri dari Baru menunjuk Kiri Awal (Baru^.Kiri:=Awal^.Kiri)
3) Kanan dari Awal menunjuk Baru (Bantu^.Kiri^.Kanan:=Baru)
4) Kiri dari Awal menunjuk Baru (Awal^Kiri=Baru)
II.3.2.1.2. Menambah Simpul Depan
a. Operasi Penambahan simpul depan pada Single Linked List
Untuk melakukan operasi penambahan simpul depan dapat dilakukan dengan tahap sebagai berikut:
a) Elemen Baru selalu pada posisi pertama
b) Jika Linked List belum ada maka Simpul Baru menjadi Linked List
c) Penambahan dilakukan dengan cara Simpul Baru disambungkan dengan Linked List
d) Penunjuk Linked List dipindahkan ke Simpul Baru.
b. Operasi Penambahan simpul depan pada Double Linked List
Operasi penambahan depan ini dapat dibagi dalam dua bagian yaitu:
1. Operasi Penambahan simpul depan pada Linier Double Linked List
Operasi penambahan simpul depan pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul ditambah sebagai Simpul depan atau simpul paling kiri
b) Penyisipan simpul ada kemungkinan simpul menjadi Awal pembentukan Linked List .
1. Operasi Penambahan simpul depan pada Circular Double Linked List
Operasi penambahan simpul depan pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Jika Linked List belum ada maka Simpul Baru menjadi awal Linked List (Awal:=Baru)
b) Jika Linked List sudah ada, maka:
1) Kanan dari Baru menunjuk Awal (Baru^.Kanan:=Awal)
2) Kiri dari Baru menunjuk Kiri Awal (Baru^.Kiri:=Awal^.Kiri)
3) Kanan dari Awal menunjuk Baru (Awal^.Kiri^.Kanan:=Baru)
4) Kiri dari Awal menunjuk Baru (Awal^Kiri=Baru)
5) Awal menunjuk Baru.
II.3.2.1.3. Menambah Simpul Tengah
a. Operasi Penambahan simpul tengah pada Single Linked List
Untuk menambah simpul tengah Single Linked List, diperlukan bantuan sebuah pointer lain, misalnya pointer Bantu. Dalam hal ini simpul akan diletakkan setelah simpul yang ditunjuk oleh pointer Bantu (Insap Santoso, 1992:110).
a. Operasi Penambahan simpul tengah pada Double Linked List
Operasi penambahan tengah ini dapat dibagi dalam dua bagian yaitu:
1. Operasi Penambahan simpul tengah pada Linier Double Linked List
Operasi penambahan simpul tengah pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul ditambah pada simpul di tengah Linked List
b) Linked List tidak boleh kosong
c) Gunakan Pointer Bantu untuk mengihindari terputusnya Linked List.
2. Operasi Penambahan simpul tengah pada Circular Double Linked List
Operasi penambahan simpul tengah pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Linked List tidak boleh kosong gunakan Pointer Bantu untuk menjaga agar urutan Linked List tidak berubah
b) Letakkan Pointer Bantu pada impul tertentu di tengah Linked List:
1) Kanan Baru menunjuk Kanan Bantu (Baru^.Kanan:=Bantu^.Kanan)
2) Kiri Baru menunjuk Bantu (Baru^.Kiri:=Bantu)
3) Kiri dari Kanan Bantu menunjuk Baru (Bantul^.Kanan^.Kiri:=Baru)
4) Kanan Bantu menunjuk Baru (Bantu^.Kanan=Baru)
II.3.2.2. Menghapus Simpul
Operasi yang kedua yang ada pada senarai berantai adalah operasi menghapus simpul. Dalam mnenghapus simpul ada satu hal yang perlu diperhatikan, yaitu bahwa simpul yang bisa dihapus adalah simpul yang berada sesudah simpul yang ditunjuk oleh oleh suatu pointer.
II.3.2.2.1. Menghapus Simpul Depan
a. Operasi Penghapusan simpul depan pada Single Linked List
Operasi penghapusan simpul depan pada Single Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Linked List tidak boleh kosong
b) Pointer yang digunakan adalah Hapus untuk menunjuk Simpul yang akan dihapus dan Awal untuk menunjuk Linked List
c) Simpul Pertama ditunjuk oleh Pointer Hapus (Hapus=Awal)
d) Putuskan Simpul Pertama dari Awal (Hapus^.Next=Nil)
e) Dispose Simpul Hapus
b. Operasi Penghapusan simpul depan pada Double Linked List
Operasi penghapusan simpul depan pada Double Linked List dapat dibagi dalam dua jenis,yaitu:
1. Operasi Penghapusan simpul depan pada Linier Double Linked List
Operasi penghapusan simpul depan pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul Pertama ditunjuk oleh Pointer Hapus (Hapus=Awal)
b) Pointer Awal gerakkan satu simpul ke kanan
c) Putuskan Hapus dari Linked List
d) Dispose Hapus
2. Operasi Penghapusan simpul depan pada Circular Double Linked List
Operasi penghapusan simpul depan pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul Pertama ditunjuk oleh Pointer Hapus (Hapus=Awal)
b) Pointer Awal geser satu simpul ke kanan (Awal=Awal^.Kanan)
c) Kiri dari Awal menunjuk Kiri dari Hapus (Awal^.Kiri=Hapus^.Kiri)
d) Kanan dari Kiri Hapus menunjuk Awal (Hapus^.Kiri^.Kanan=Awal)
e) Kanan Hapus menunjuk Hapus (Hapus^.Kanan=Kanan)
f) Kiri Hapus menunjuk Hapus (Hapus^.Kiri=Hapus)
g) Dispose (Hapus)
II.3.2.2.2. Menghapus Simpul Belakang
a. Operasi Penghapusan simpul belakang pada Single Linked List
Operasi penghapusan simpul belakang pada Single Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Linked List tidak boleh kosong
b) Pointer yang digunakan adalah Hapus untuk menunjuk Simpul yang akan dihapus; Bantu untuk menunjuk Simpul demi Simpul dari Linked List dan Awal untuk menunjuk Linked List
1) Gerakkan Pointer Bantu hingga pada satu Simpul sebelum Simpul Terakhir
2) Simpul Terakhir ditunjuk oleh Pointer Hapus (Hapus=Bantu^.Next)
3) Putuskan Simpul Terakhir dari Awal (Bantu^.Next=Nil)
4) Dispose Simpul Hapus
b. Operasi Penghapusan simpul belakang pada Double Linked List
Operasi penghapusan simpul belakang pada Double Linked List dapat dibagi dalam dua jenis,yaitu:
1. Operasi Penghapusan simpul belakang pada Linier Double Linked List
Operasi penghapusan simpul belakang pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Untuk menghindari terputusnya Linked List maka gunakan Pointer Bantu
b) Gerakkan Pointer Bantu hingga satu simpul sebelum simpul belakang
c) Simpul Belakang ditunjuk oleh Pointer Hapus
d) Putuskan Hapus dari Linked List
e) Dispose Hapus
2. Operasi Penghapusan simpul belakang pada Circular Double Linked List
Operasi penghapusan simpul belakang pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Simpul Belakang ditunjuk oleh Pointer Hapus (Hapus=Awal^.Kiri)
b) Kiri dari Awal menunjuk Kiri dari Hapus (Awal^.Kiri=Hapus^.Kiri)
c) Kanan dari Kiri Hapus menunjuk Awal (Hapus^.Kiri^.Kanan=Awal)
d) Kanan Hapus menunjuk Hapus (Hapus^.Kanan=Hapus)
e) Kiri Hapus menunjuk Hapus (Hapus^.Kiri=Hapus)
f) Dispose (Hapus)
II.3.2.2.3. Menghapus Simpul Tengah
a. Operasi Penghapusan simpul tengah pada Single Linked List
Operasi penghapusan simpul tengah pada Single Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Linked List tidak boleh kosong
b) Pointer yang dibutuhkan Awal, Bantu, dan Hapus
c) Pointer Awal menunjuk Linked List
d) Pointer Bantu merupakan Pointer yang dapat digerakkan menunjuk setiap simpul
e) Pointer Hapus menunjuk simpul yang akan dihapus
1) Gerakkan Pointer Bantu satu simpul sebelum simpul yang akan dihapus
2) Letakkan Pointer Hapus pada simpul yang akan dihapus
3) Pointer Bantu menunjuk simpul setelah simpul yang ditunjuk oleh Hapus
4) Putuskan simpul yang ditunjuk oleh Hapus dari Linked List
b. Operasi Penghapusan simpul tengah pada Double Linked List
Operasi penghapusan simpul tengah pada Double Linked List dapat dibagi dalam dua jenis,yaitu:
1. Operasi Penghapusan simpul tengah pada Linier Double Linked List
Operasi penghapusan simpul tengah pada Linier Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Untuk menghindari terputusnya Linked List maka gunakan Pointer Bantu
b) Gerakkan Pointer Bantu hingga satu simpul sebelum simpul yang akan dihapus
c) Simpul yang akan dihapus ditunjuk oleh Pointer Hapus
d) Putuskan Kiri dari Simpul setelah Hapus terhadap Hapus
e) Putuskan Kanan dari Bantu terhadap Hapus
f) Sambungkan Kanan Bantu terhadap simpul setelah Hapus
g) Sambungkan Kiri dari simpul setelah Hapus terhadap Bantu
h) Dispose Hapus
2. Operasi Penghapusan simpul tengah pada Circular Double Linked List
Operasi penghapusan simpul tengah pada Circular Double Linked List dapat dilakukan dengan langkah-langkah sebagai berikut:
a) Gerakkan Pointer Bantu hingga satu simpul sebelum simpul yang akan dihapus
b) Pointer Hapus menunjuk Kanan Bantu (Hapus=Bantu^.Kanan)
c) Kanan dari Bantu menunjuk dua simpul dari Bantu ke kanan (Bantu^.Kanan = Bantu^.Kanan^.Kanan)
d) Kiri dari Kanan Bantu menunjuk Bantu (Bantu^.Kanan^.Kiri =Bantu)
e) Kanan Hapus menunjuk Hapus (Hapus^.Kanan=Hapus)
f) Kiri Hapus menunjuk Hapus (Hapus^.Kiri = Hapus)
