Pengenalan Algoritma dan Struktur Data - Bab 2 Linked List

BAB 2 LINKED LIST

CPMK2/CO2: Mahasiswa mampu menjelaskan struktur data linier string, linked list, stack dan queue

2.1 Pendahuluan

Suatu program computer digunakan untuk memproses data. Pada saat pemrosesan ini, data tersimpan dalam memori komputer. Oleh karenanya diperlukan suatu mekanisme untuk menyimpan, mengorganisasikan, mengambil, dan mengatur data tersebut sehingga dapat digunakan secara efisien. Berbagai model penyimpanan data dibangun menirukan berbagai proses nyata dalam kehidupan sehari-hari. Model-model ini digunakan untuk berbagai keperluan secara spesifik. Pada modul pembelajaran ini dikenalkan mode penyimpanan: linked list (senarai berantai), stack (tumpukan), queue (antrian), dan tree (pohon). Pada Bab ini akan dipaparkan struktur data linked list.

2.2 Pointer (penunjuk)

Linked list merupakan struktur data dinamis yang pemesanannya dilakukan pada saat program berjalan. Hal ini berbeda dengan array yang pemesanannya dilakukan pada saat penulisan program. Array merupakan struktur data yang statis.

Penggunaan Linked list membutuhkan variable bertipe pointer. Variabel bertipe pointer akan berisi alamat dari suatu memori. Yang demikian ini dikatakan variable pointer menunjuk ke memori alamat tersebut. Pada saat variable pointer berisi nil, dikatakan bahwa variable pointer tersebut tidak menunjuk kemanapun.

2.3 Struktur data linked list

Struktur data linked list merupakan model penyimpanan data secara linier seperti array. Namun demikian tidak seperti array yang penempatan data berdasar nomor indeks, linked list menyimpan data dalam rangkaian simpul (node). Gambar 1 menunjukkan linked list A yang memiliki 4 simpul dengan masing-masing memuat sebuah data bilangan bulat. Setiap simpul terdiri atas 1) penyimpan data dan 2) penunjuk (pointer) ke simpul berikutnya seperti ditunjukkan pada Gambar 2.2. Variabel data digunakan untuk menyimpan data, variable next digunakan untuk menyimpan alamat memori simpul berikutnya. Dengan cara demikian, variable next akan menunjuk ke simpul berikutnya. Simpul terakhir tidak menunjuk ke manapun (berisi nil).

Gambar 1. Linked list

Gambar 2. Ilustrasi sebuah simpul dan representasi variabelnya

2.4 Penambahan data pada Linked list

Pembuatan sebuah linked list akan dimulai saat variable linked list belum mempunyai simpul. Pada kondisi ini variable linked list berisi nil (Gambar 3).

Gambar 3. Variabel A berisi nil

Penambahan data pada linked list dapat dikategorikan ke dalam 3 skema: penyimpanan data pertama, penambahan di awal, penambahan di tengah dan penambahan di akhir dari linked list.

2.5 Penyimpanan data pertama

Penyimpanan data pertama terjadi pada penambahan data ketika varable linked list masih kosong. Gambar 4 (a) menunjukkan variable A yang semula berisi nil, diisi dengan simpul Baru. Hal ini cukup dilakukan dengan operator penugasan (=) (Gambar 5). Perintah akan menghasilkan variable A dan Baru yang sama-sama berisi simpul yang membawa data 1 (Gambar 4 (b)).

Gambar 4. (a) Variabel A berisi nil dan variable Baru berisi simpul yang membawa data 1. (b)Variabel A dan Baru berisi simpul yang membawa data 1

Gambar 5. Program untuk mengarahkan variable A sehingga memiliki isi yang sama dengan Baru

2.6 Penambahan data di awal

Penambahan data di awal dilakukan dengan mekanisme berikut ini. Misal dipunyai variable A yang berisi simpul 1 (Gambar 6 (a)). Variabel Baru yang membawa simpul 9 akan ditambahkan ke A (Gambar 6 (b)). Langkah untuk melakukannya ditunjukkan pada Gambar 7.

Gambar 6. Penambahan simpul di awal

Gambar 7. Program untuk penambahan simpul di awal

2.7 Referensi

Rerung, R. R., Algoritma dan Struktur Data untuk Perguruan Tinggi. Solok: CV. Insan Cendekia Mandiri, 2018.

Buana, I. K. S., Nata, G. N. M., dan Arnawa, I. B. K. S., Struktur Data. Yogyakarta: Andi, 2018.

Jagtap, A. M. dan Mali, A. S., Data Structures Using C A Practical Approach for Beginners,

Amerika serikat: CRC Press, 2021.

Subscribe Our Newsletter