linked list

13
LINKED LIST ..Struktur Data.. A1 Kelompok 3 Ketua : Anggota : 1. 2. 3. 4.

Upload: said-zulhelmi

Post on 16-Apr-2017

1.122 views

Category:

Education


62 download

TRANSCRIPT

Page 1: Linked List

LINKED LIST

..Struktur Data.. A1

Kelompok 3Ketua :

Anggota : 1. 2. 3. 4.

Page 2: Linked List

Pengertian Linked ListLinked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer. Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :a) INFO , berisi informasi tentang elemen data yang bersangkutan. b) NEXT (link field/next pointer field), berisi alamat dari elemen (node)

selanjutnya yang dituju.Berikut ini sebuah contoh linked list yang terdiri atas 4 node :

Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tersebut adalah node terakhir.

Page 3: Linked List

Ciri khas suatu node dalam linked list adalah harus selalu terdapat field, paling sedikit dua bagian, yaitu :1. Data2. Pointer  Linked list dapat disajikan dengan 2 bagian, yaitu Singly Linked List dan Doubly Linked List. Baik singly linked list maupun doubly linked list dapat juga disajikan secara Melingkar (circular).

Page 4: Linked List

Keuntungan & Kerugian Dari Linked List

Keuntungan dari Linked List : Jenis data yang berbeda dapat di-link. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-

nya saja.

Kerugian dari Linked List : Dibutuhkan ruang tambahan untuk menyatakan/tempat field pointer. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam

linked list.

Page 5: Linked List

Single Linked List Single linked list merupakan linked list yang paling sederhana. Setiap simpul dibagi menjadi dua bagian yaitu bagian isi dan bagian pointer. Bagian isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian pointer merupakan bagian yang berisi alamat dari simpul berikutya.

Sebagai ilustrasi simpul dari singly list dapat dilihat pada gambar berikut :

Page 6: Linked List

Pembagian Single Linked List

Single linked list dibagi menjadi 2, yaitu :1. Single linked list circular Single Linked List Circular adalah Single Linked List yang pointer next-nya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Contoh single list circular :

Page 7: Linked List

2. Single Linked List Non-Circular Single Linked List Non-Circular adalah Singly Linked List yang pointer next pada node terakhir-nya menunjuk ke Null.

Contoh single list non-circular :

Page 8: Linked List

Operasi Pada Single Linked ListOperasi pada single linked list ada 3, yaitu :• Menambah Simpul Operasi yang digunakan untuk menyisipkan simpul di posisi tertentu. Peyisipan simpul dapat dilakukan di posisi depan, penyisipan simpul di belakang penyisipan simpul di antara dua simpul (tengah).

• Menghapus Simpul Operasi yang digunakan unruk menghapus suatu simpul dari suatu linked list. Dalam melakukan penghaspusan simpul, ada yang perlu di perhatikan, bahwa linked list tidak boleh terputus. Sama hal nya dengan penyisipan, penghapusan simpul juga dapat dilakukan terhadap simpul depan, simpul belakang, dan simpul tengah.

• Mencetak Isi Simpul Nilai masing-masing simpul dapat dicetak mulai dari isi simpul pertama atau simpul depan hingga simpul belakang

Page 9: Linked List

Double Linked List Double linked list merupakan linked list dimana setiap simpul dibagi menjadi tiga bagian yaitu bagian isi, bagian pointer kiri, dan bagian pointer kanan. Bagian isi merupakan bagian yang berisi data yang disimpan oleh simpul, sedangkan bagian pointer kiri merupakan bagian yang berisi alamat dari simpul sebelumnya dan bagian pointer kanan merupakan bagian yang berisi alamat dari simpul berikutnya.

Page 10: Linked List

Pembagian Double Linked List

Double linked list dibagi menjadi 2, yaitu :1. Double Linked List Circular Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Circular pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

Contoh double list circular :

Page 11: Linked List

2. Double Linked List Non-Circular Double Linked List Non Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Non Circular pointer next dan prev nya menunjuk ke NULL. Dengan adanya 2 pointer penunjuk, next dan prev, DLLNC sangat flexible dibandingkan dengan SLLNC.

Contoh double list non-circular :

Page 12: Linked List

Operasi Pada Double Linked ListOperasi pada double linked list ada 4, yaitu :• Penyisipan Simpul Operasi penyisipan suatu simpul baru ke dalam suatu double linked list. Penyisipan dapat dilakukan di posisi depan, tengah, dan belakang. • Penghapusan Simpul Operasi menghapus suatu simpul dari suatu linked list pada double linked list hampir sama dengan penghapusan simpul single linked list, linked list (DL) tidak boleh dalam keadaan kosong. Penghapusan simpul juga dapat dilakukan terhadap simpul depan, simpul belakang, dan simpul tengah.

• Percetakan Simpul

• Mencetak Linked List Secara Mundur Mencetak mundur artinya mencetak elemen linked ist mulai dari elemen simpul belakang ke depan.

Page 13: Linked List

..Selesai..

THANK

YOU