single linked list

5/16/2018 Single Linked List - slidepdf.com

http://slidepdf.com/reader/full/single-linked-list-55ab52fa96a07 1/6

SINGLE LINKED LIST

Sejarah 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).

Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara

sekuensial, saling sambung-menyambung, dinamis dan terbatas. Linked List sering disebut juga Senarai

Berantai. Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam

Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya

berupa record yang terdiri dari beberapa field.

- Kamus Global Single Linked List

{Algoritma}

Type

nama_pointer = ↑simpul

simpul = record

medan_data : tipedata;medan_sambungan : nama_pointer

endrecord

nama_var_pointer : nama_pointer

- Perbedaan Array dengan Linked List

ARRAY LINKED LIST

Statis Dinamis

Penambahan / Penghapusan data terbatas Penambahan / Penghapusan data tak

terbatas

Random Access Sequential AccessPenghapusan Array tidak mungkin Penghapusan Linked List mudah

- Bentuk Node Single Linked List

- Contoh Single Linked List

// Catatan : Akhir dari Single Linked List harus di nil kan (lihat gambar) karena medan sambungannya

tidak menunjuk node (simpul) yang lain.

Info next

Keterangan:

Info : Medan data yang dapat diisi

Next : Medan sambungan yang menghubungkan node

pertama (awal) sampai node terakhir (akhir).

Info next

Info next

Info next

Awal Akhir



- Operasi-Operasi pada Single Linked List:

1. Penciptaan (Create)

2. Penyisipan

3. Penghapusan

4. Traversal

5. Pencarian (Searching)

6. Pengurutan (Sorting)

7. Penghancuran (Destroy)

1. Penciptaan (Create)

Adalah tahap awal untuk membuat satu simpul yang mana awal dan akhirnya berada di satu

simpul tersebut. Setelah itu, awal dan akhir dari satu simpul itu diinisialisasi dengan angka nil (nil

digambarkan seperti pada simpul akhir pada contoh single linked list yang mana medan

sambungannya dicoret).

2. Penyisipan

2.1 Penyisipan di Depan

Adalah tahapan setelah tahap penciptaan, yang mana satu simpul akan disisipkan di depansebelum simpul awal dan akhir (create). Setelah simpul disisipkan, maka variabel awal pada

simpul create pindah ke simpul baru yang disisipkan sebelum simpul create tadi.

2.2 Penyisipan di Belakang

Adalah tahapan setelah tahap penciptaan, yang mana satu simpul akan disisipkan di

belakang setelah simpul awal dan akhir (create). Setelah simpul disisipkan, maka variabel

akhir pada simpul create pindah ke simpul baru yang disisipkan setelah simpul create tadi.

2.3 Penyisipan di Tengah

Adalah tahapan setelah tahap penciptaan, yang mana satu simpul akan disisipkan di tengah

pada sebuah single linked list. Sebelum penyisipan dilakukan, posisi sisip tengahnya harus

diketahui terlebih dahulu dengan melakukan penyisiran dari simpul awal sampai simpul

akhir. Jika sudah diketahui, maka penyisipan pun dilakukan. Jika tidak diketahui, maka tidakada penyisipan.

3. Penghapusan

3.1 Penghapusan di Depan

Adalah tahapan setelah tahap penciptaan, yang mana satu simpul akan dihapus pada suatu

single linked list di posisi paling depan (simpul yang ditunjuk oleh variabel awal). Sebelum

terjadi penghapusan, variabel awal pindah ke simpul setelah simpul paling depan tadi,

sehingga yang ditunjuk oleh variabel awal itulah yang menjadi simpul paling depan. Setelah

proses pemindahannya selesai, maka penghapusan pun dilakukan.

3.2 Penghapusan di Belakang


single linked list di posisi paling belakang (simpul yang ditunjuk oleh variabel akhir). Sebelum

terjadi penghapusan, variabel akhir pindah ke simpul sebelum simpul paling belakang tadi,

sehingga yang ditunjuk oleh variabel akhir itulah yang menjadi simpul paling Belakang.

Setelah proses pemindahannya selesai, maka penghapusan pun dilakukan.



3.3 Penghapusan di Tengah


single linked list di posisi tengah. Sebelum terjadi penghapusan, posisi hapusnya harus

diketahui terlebih dahulu dengan melakukan penyisiran dari simpul awal sampai simpul

akhir. Jika simpul ditemukan, maka penghapusan pun dilakukan. Jika simpul tidak

ditemukan, maka tidak ada penghapusan.

4. Traversal

Adalah suatu proses mengunjungi setiap simpul satu persatu dari simpul pertama (awal) sampai

simpul terakhir (akhir).

5. Pencarian (Searching)

Adalah suatu proses melakukan pencarian suatu medan data pada sekumpulan single linked list.

Pencarian dilakukan menggunakan metode Sequential Search dari simpul awal sampai simpul

ditemukan atau sampai simpul akhir. Jika medan data ditemukan, maka pencarian selesai.

6. Pengurutan (Sorting)

Adalah suatu proses melakukan pengurutan suatu medan data pada sekumpulan single linked

list. Pengurutan dilakukan menggunakan metode Minimum Sort (Asc atau Dsc) mulai dari simpul

awal sampai simpul akhir.7. Penghancuran (destroy)

Adalah suatu proses menghapus simpul satu persatu sampai list kosong.

Source :

http://lecturer.ukdw.ac.id/anton/download/TIstrukdat6.ppt

http://kuliahonline.unikom.ac.id/?go/kuliah/&getMateriFile=MTE2NjY%3D&kID=MjQyMQ%3D%

3D

http://kuliahonline.unikom.ac.id/?go/kuliah/&getMateriFile=MTEzODI%3D&kID=MjQyMQ%3D

%3D



http://kuliahonline.unikom.ac.id/?go/kuliah/&getMateriFile=MTE2NjY%3D&kID=MjQyMQ%3D%3D



http://kuliahonline.unikom.ac.id/?go/kuliah/&getMateriFile=MTEzODI%3D&kID=MjQyMQ%3D%3D










*Penyisipan depan

Dalam proses menyisipkan depan, tahap-tahap sebagai berikut :

Keadaan Bila variable awal = nil

1. Membuat variable Misalnya kita namakan baru

2. Baru^.info kita masukan nilai berapa saja

3. Baru^.next kita beri nilai nil karena tidak menunjuk kemanapun

4. Awal akan menunjuk baru

5. Akhir akan menunjuk baru

Keadaan Bila variable awal ≠ nil



3. Baru^.next akan menuju variable awal

4. Baru akan menjadi Awal

*Penyisipan tengah

Keadaan bila variable awal = nil

1 Membuat variable Misalnya kita namakan baru

2 Baru^.info kita masukan nilai berapa saja

3 Baru^.next kita beri nilai nil karena tidak mengarah kemanapun

4 Awal akan menjadi baru

5 Akhir akan menjadi baru




3. Misal bila ingin menyisipkan setelah simpul ke-2 kita bisa menggunakan pencarian sequential

search dengan membuat variable baru Misal kita beri nama bantu

4. Bila bantunya ditemukan di data terakhir maka bisa mengunakan proses yang sisi belakang

5. Bila bantunya ditemukan di data tengah maka lakukan penyisipan

6. Bila bantunya tidak ditemukan maka tidak ada penyisipan

*Penyisipan belakang

Keadaan Bila variable awal = nil



3. Baru^.next kita beri nilai nil karena tidak mengarah kemanapun



4. Awal akan menjadi baru

5. Akhir akan menjadi baru




3. akhir^.next akan menuju variable baru

4. akhir akan menjadi baru

*penghapusan depan

Keadaan Bila variable awal = akhir

1. Membuat variable Misalnya kita namakan phapus

2. Elemen menuju baru^.info supaya nilai ketika dihapus akan tersimpan

3. Lakukan Penghapusan

4. Awal akan menjadi nil

5. Akhir akan menjadi nil

Keadaan Bila variable awal ≠ akhir


2. Elemen menuju baru^.info supaya nilai ketika dihapus akan tersimpan

3. Awal akan menuju awal ^.next

4. Lakukan Penghapusan

*Penghapusan tengah



2. Panggil procedure hapus di depan


1 Membuat variable Misalnya kita namakan phapus

2 Buat agar variabel phapus menunjuk ke pointer awal, sebagai iinisialisasi untuk mencari posisi

pointer yang akan hapus.

3 Masukkan posisi hapus untuk melakukan pencarian

4 Lakukan pencarian posisi hapus mulai dari pointer awal sampai pointer akhir

5 Jika posisi hapus ada di depan / awal, maka panggil procedure hapus di depan

6 Jika posisi hapus ada di belakang / akhir, maka panggil procedure hapus di belakang

7 Jika posisi hapus di temukan, maka lakukan penghapusan

8 Jika posisi hapus tidak di temukan, maka tidak ada penghapusan



*Penghapusan belakang



2 Elemen menuju baru^.info supaya nilai ketika dihapus akan tersimpan

3 Awal akan menjadi nil

4 Akhir akan menjadi nil



2 Elemen menuju baru^.info supaya nilai ketika dihapus akan tersimpan

3 Mengunakan pencarian sequential search untuk menemukan simpul akhir dengan

Menggunakan variabel phapus

4 Akhir akan menuju phapus

5 Phapus akan menuju phapus^.next

6 Setelah itu akhir^.next kita nil kan7 Lakukan Penghapusan

single linked list

Documents