1.
Sejarah Linked
List
Linked
List dikembangkan tahun 1955-1956 oleh
Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa
Information Processing Language (IPL). IPL
dibuat untuk mengembangkan program artificial intelligence, seperti pembuatan
Chess Solver.Victor Yngve di Massachusetts Institute of Technology (MIT) juga
menggunakan linked list pada
natural language processing dan machine transitions pada bahasa pemrograman
COMMIT. Linked List yaitu salah
satu bentuk struktur data, berisi kumpulan data (simpul) yang tersusun secara
sekuensial, saling sambung-menyambung, dinamis.
Linked
List adalah salah satu struktur data dasar yang sangat
fundamental dalam bidang ilmu komputer.
Dengan menggunakan linked list
maka programmer dapat menyimpan datanya kapanpun dibutuhkan. Linked list hampir mirip dangan array, perbedaannya pada linked list data yang ingin disimpan
dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Pada array, apabila programmer
ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali
programmer mengalokasikan array yang sangat besar (misalnya 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 statis. Linked list
adalah salah satu struktur data
yang mampu menutupi kelemahan tersebut.
2.
Pengertian Single Linked List
Linked List atau Senarai Berantai merupakan sekumpulan objek biasa juga
disebut simpul atau node yang tersusun secara sekuensial, saling sambung-menyambung,
bersifat dinamis.
Sedangkan objek (simpul atau node) nya itu merupakan
bagian dari beberapa elemen data (variable) yang dijadikan satu kelompok atau
satu structure atau record yang dibentuk dengan perintah struct. Tiap elemennya
memiliki tipe data tersendiri yang berbeda dengan tipe data elemen lainnya.
Serta untuk menghubungkan elemen satu dengan lainnya diperlukan sebuah bantuan
variable pointer yang juga merupakan salah satu variable dalam struktur objek
(simpul atau node). Sehingga single linked list mempunyai arti sekumpulan data yang tersusun
secara teratur dengan bantuan variable pointer atau penuding yang searah. Yang
mana setiap objek (simpul atau node) pada linked list mempunyai field yang berisi pointer ke
objek 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.
2.1 Ciri – Ciri Single Linked List
a.
Variable bersifat dinamis
b.
Mempunyai awalan (Header)
c.
Mempunyai penuding (pointer) yang searah
d.
Objek terdiri dari data dan link
e.
Mempunyai akhiran
2.2 Jenis Single
Linked List
a.
Single Linked List Circular
Single Linked
List Circular adalah sekumpulan data yang tersusun secara teratur dengan
bantuan variable pointer atau penuding yang searah tanpa mempunyai Null untuk
medan sambungnya.
Seperti pada
gambar berikut:
a.Single Linked List Circular
b.
Single Linked List Non Circular
Ini disebut
juga dengan single linked list linier adalah sekumpulan data yang tersusun
secara teratur dengan bantuan variable pointer atau penuding yang searah serta
mempunyai akhiran Null untuk medan sambungnya.
Seperti pada
gambar berikut:
b. Single Linked List Non Circular
3.
Metode – Metode Single Linked List
Dalam penggunaan Single
Linked List dapat menggunakan dua metode:
1)
Metode FIFO (First In First Out)
Yaitu suatu
metode pembuatan linked list dimana data yang masuk paling awal adalah data
yang keluar paling awal juga, hal ini dapat dianalogikan seperti sebuah
antrian, dimana yang datang paling awal adalah yang keluar paling awal.
2)
Metode LIFO (Last In First Out)
Yaitu suatu metoda pembuatan Linked List
dimana data yang masuk
paling akhir adalah data yang keluar paling
awal. Hal ini dapat dianalogikan dengan menumpukan
barang pada kehidupan sehari‐hari. Pembuatan
simpul pada suatu linked
list disebut dengan istilah
Insert.
Jika
linked list dibuat dengan
Metoda
LIFO maka penambahan/insert simpul
dilakukan di belakang.
4.
Procedure dan Function Single Linked List
1.
Create
Membuat sebuah linked
list
yang
baru dan
masih kosong.
Procedure
ini
wajib
dipanggil untuk menggunakan
linked list.
2.
Empty
Function
untuk menentukan apakah linked list kosong atau tidak.
3.
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu
linked list.
4.
Find First
Mencari elemen pertama dari linked list.
5.
Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk saat ini (now).
6.
Retrieve
Mengambil elemen yang ditunjuk oleh now. Elemen tersebut
lalu ditampung pada suatu
variabel, dalam potongan procedure lalu
dikembalikan oleh fungsi.
7.
Update
Mengubah elemen yang ditunjuk oleh now dengan isi dari suatu variable.
8.
Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus
adalah
elemen kedua dari linked list, maka link pertama akan menyimpan alamat ke
elemen ketiga, karena yang kedua telah dihapus.
9.
Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen
sesudahnya.
10.
Clear
Untuk menghapus linked list yang sudah ada. Wajib dilakukan bila ingin mengakhiri
program yang menggunakan linked list.
Jika tidak ada data‐data yang dialokasikan
ke memori pada
program sebelumnya akan tetap
tertinggal di dalam memori.
Refrensi :