Pengertian Linked List
Salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programer dapat menyimpan datanya kapanpun di butuhkan. Linked list mirip dengan array, kecuali pada linked list data yang ingin disimpan dapat di alokasikan secara dinamispada saat pengoperasian program (run-time).
Definisi Linked List, Single Linked List, Double Linked List, & Circular Linked List
a. Linked List ( LL )
Adalah koleksi data item yang tersusun dalam sebuah barisan secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.
b. Single Linked List
Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.
Ilustrasi single LL:
c. Double Linked List
Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.
d. Circular Linked List
Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan
merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih
PENYAJIAN LINKED LIST DALAM MEMORY
Adalah dengan cara membentuk larik INFO(K) dan LINK(K), berturut-turut menyajikan bagian informasi dan field next pointer. Juga kita pakai sebuah variable START untuk menyimpanan alamat dari element list. Pada bagian akhir dari list, next pointer bernilai null. Apabila tidak di sebutkan nilai null adalah 0, dan nilai subscript larik INFO serta LINK selalu diambil positif.
KUNJUNGAN LINKED LIST
Pandangan sebuah linked list, LIST yang tersimpan dalam memory berupa larik INFO dan LINK, dilengkapi dengan variable penuding START, yang berfungsi menuding lokasi simpul pertama dari list, dan NULL yang digunakan untuk menyatakan berakhirnya list.
Penyisipan,Penghapusan,dan Pencarian dalam Linked List
Penyisipan : Misalkan A dan B adalah dua simpul yang berurutan . Dimana ada sebuah simpul baru N akan disisipkan ke dalam LIST, antara simpul A dan B. Disini simpul A sekarang menuding ke simpul baru N, dan simpul baru N menuding ke simpul B, yang tadinya di tuding oleh A.
Penghapusan : Misalnya simpul N adalah simpul dari LIST yang terletak diantara simpul A dan simpul B, Simpul N tersebut akan dihapus dari LIST. Penghapusan terjadi begitu nextpointer dari A berubah menuding ke B. Dalam penghapusan ini, kita harus mengingat alamat dari simpul A, simpul pendahulu dari simpul yang akan kita hapus tersebut.
Pencarian :
1.Cari dalam list tidak berurut.
Melakukan Traversal Simpul list, sambil setiap kali memeriksa apakah informasi dalam simpul yang tengah dikunjungi tersebut sama dengan ITEM.
Dalam algoritma ini diperlukan 2 buah pemeriksaan pada setiap putaran yaitu :
1.Memeriksa apakah telah sampai pada akhir dari list, yakni dengan memeriksa apakah PTR = NULL.
2. Memeriksa apakah ITEM telah ditemukan lokasinya, yakni dengan memeriksa apakah INFO(PTR) = ITEM
ALGORITMA
SEARCH(INFO, LINK, START, ITEM, LOC)
1. PTR := START.
2. Kerjakan langkah 3 dalam hal PTR <> NULL :
3. Jika INFO(PTR) = ITEM, maka :
LOC := PTR, exit.
Bila tidak
PTR := LINK(PTR).
4. LOC := NULL. (Pencarian gagal)
5. Exit.
2. Cari list berurut
Melakukan Traversal Simpul list, sambil setiap kali memeriksa apakah informasi dalam simpul yang tengah dikunjungi tersebut sama dengan ITEM. Karena terurutnya list, tidak perlu melakukan Traversal sampai akhir dari list, walau ITEM tidak terdapat dalam list.
Begitu INFO(PTR) > ITEM, hentikan proses pencarian.
Dalam algoritma ini diperlukan 2 buah pemeriksaan pada setiap putaran yaitu :
1. Memeriksa apakah INFO(PTR) sudah lebih besar dari ITEM, berarti ITEM tidak terdapat dalam list, hentikan proses cari.
2. Memeriksa apakah ITEM telah ditemukan lokasinya, yakni dengan memeriksa apakah INFO(PTR) = ITEM.
SRCHSL(INFO, LINK, START, ITEM, LOC)
1. PTR := START.
2. Kerjakan langkah 3 dalam hal PTR <> NULL :
3. Jika INFO(PTR) < ITEM, maka :
PTR := LINK(PTR).
Bila tidak jika ITEM = INFO(PTR), maka :
LOC := PTR, dan exit. (pencarian sukses)
Bila tidak :
LOC := NULL, and exit.
4. LOC := NULL.
5. Exit.
ALOKASI MEMORY : KOLEKSI SAMPAH
Ketika kita menyimpan linked list dalam memory, di asumsikan bahwa selalu dapat dilakukan penyisipan simbul baru ke dalam list, serta penghapusan simpul dari list.
HEADER LINKED LIST
Adalah : suatu linked list yang mengandung suatu simpul khusus yang terletak pada bagian awal dari list, yang disebut simpul headre.Header list ada 2 jenis yaitu
1. Grounded Header List
2.Circular Haeder List
Sumber : Perkuliahan Struktur Data STMIK ASIA
0 komentar:
Posting Komentar