Single Linked List

SINGLE LINKED LIST

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 :

https://www.scribd.com/doc/122366588/SINGLE-LINKED-LIST-NON-CIRCULAR.html