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.
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:
–
LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
–
FIFO (First In First Out), aplikasinya : Queue (Antrean)
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.
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 :
– Insert
Istilah Insert berarti menambahkan
sebuah simpul baru ke dalam suatu linked list.
– IsEmpty
Fungsi ini menentukan apakah linked
list kosong atau tidak.
– Find
First
Fungsi ini mencari elemen pertama
dari linked list
– Find
Next
Fungsi ini mencari elemen sesudah
elemen yang ditunjuk now
– Retrieve
Fungsi ini mengambil elemen yang
ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
– Update
Fungsi ini mengubah elemen yang
ditunjuk oleh now dengan isi dari sesuatu.
– Delete
Now
Fungsi ini menghapus elemen yang
ditunjuk oleh now. Jika yang dihapus adalahelemen pertama dari linked list
(head), head akan berpindah ke elemen berikut.
– Delete
Head
Fungsi ini menghapus elemen yang
ditunjuk head. Head berpindah ke elemen sesudahnya.
– 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.
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 memorit ersebut 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
1.
Operasiaritmatika
–
Pada pointer dapat dilakukan operasi aritmatika yang akan menunjuk suatu alamat
memori baru.
–
Hanya nilai integersaja yang bias dioperasikan pada variabel
pointer.
–
Biasanya hanya operasi penambahan/pengurangansaja.
–
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.