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.

Dan di 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:

–         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.