A. Linked list
Linked List adalah suatu struktur data linier. Berbeda
dengan array yang juga merupakan struktur data linier dan tipe data komposit,
linked list dibentuk secara dinamik. Pada saat awal program dijalankan elemen
linked list belum data. Elemen linked list (disebut node) dibentuk sambil jalan
sesuai instruksi. Apabila setiap elemen array dapat diakses secara langsung
dengan menggunakan indeks, sebuah node linked list diakses dengan menggunakan
pointer yang mengacu (menunjuk) ke node tersebut. Dalam struktur data algortima
linked list mempunyai beberapa jenis yaitu:
1.
Single
Linked List
Tempat yang
disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan
sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu
untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai
khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List dapat menggunakan 2
metode:
1.
LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
2.
FIFO (First In First Out), aplikasinya : Queue (Antrian)
Gambar 1.1 Single Linked List
2.
Double
Linked List
Salah satu
kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak
satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak
dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan
metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Gambar 1.2 Double Linked List
3.
Circular
Double Linked List
Merupakan double linked list yang simpul
terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk
ke simpul akhir sehingga membentuk suatu lingkaran. Operasi-Operasi yang ada
pada Linked List :
a.
Insert
Istilah Insert
berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
b.
IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
c. Find First
Fungsi ini mencari elemen pertama dari linked list
d. Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk
now
e.
Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan
oleh fungsi.
f.
Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
g. Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen
pertama dari linked list (head), head
akan berpindah ke elemen berikut.
h. Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
i.
Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda
ingin mengakhiri program yang menggunakan linked
list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada
program sebelumnya akan tetap tertinggal di dalam memori.
Gambar 1.3 Circular Double Linked List
4. Pointer
Pointer
adalah suatu variabel penunjuk, berisi nilai yang menunjuk alamat suatu lokasi
memori tertentu. Jadi pointer tidak
berisi nilai data, melainkan berisi suatu alamat memori atau null jika tidak
berisi data. Pointer yang tidak
diinisialisasi disebut dangling pointer. Lokasi memori tersebut bisa
diwakili sebuah variabel atau dapat juga berupa nilai alamat memori secara
langsung.
Operasi pada pointer
:
1. Operasi assignment
Antar variabel pointer
dapat dilakukan operasi assignment.
- Contoh 1: Assignment dan sebuah alamat dapat
ditunjuk oleh lebih dari satu pointer
- Contoh 2:
Mengisi variable dengan nilai yang ditunjuk oleh sebuah variabel pointer
- Contoh 3:
Mengoperasikan isi variable dengan menyebut alamatnya dengan pointer
- Contoh 4:
Mengisi dan mengganti variabel yang ditunjuk oleh pointer
2. Operasi
aritmatika
– Pada pointer dapat dilakukan operasi
aritmatika yang akan menunjuk suatu alamat memori baru.
– Hanya nilai
integer saja yang bias dioperasikan pada variabel pointer.
– Biasanya hanya
operasi penambahan/pengurangan saja.
– Misal pointer X bertipe int (2 bytes), maka X+1 akan menunjuk pada alamat
memori sekarang (mis. 1000) ditambah sizeof(X), yaitu 2, jadi 1002.
Pada array, pointer hanya perlu menunjuk pada alamat elemen pertama saja karena
letak alamat array sudah berurutan pada memori.Variabel pointer hanya perlu increment.
0 komentar:
Posting Komentar