LINKED LIST

Pada bab sebelumnya telah dijelaskan mengenai variabel array yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah di atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali. Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian.

Bentuk Umum:

                        typedef struct telmtlist

                         {

                              infotype info;

                              address next;

                         }elmtlist;

infotype >> sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list

next      >> address dari elemen berikutnya (suksesor)

Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu

dengan notasi :

                                    first (L)

Sebelum digunakan harus dideklarasikan terlebih dahulu :

                                       #define first (L)    (L)

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :

            info (P)      deklarasi             #define info (P)    (P) -> info

            next(P)      deklarasi             #define next(P)    (P) -> next

Beberapa Definisi :

     1. List l adalah list kosong, jika First(L) = Nil

     2. Elemen terakhir dikenali, dengan salah satu cara adalah karena

                   Next(Last) = Nil

Nil adalah pengganti Null, perubahan ini dituliskan dengan                    #define Nil 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)

LIFO ( Last In First Out)

Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini. Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan dibawah ini. Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di

belakang, dikenal dengan istilah INSERT.

FIFO (Fisrt In Fisrt Out)

FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan sehari-hari), misalnya saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket. Jika linked list dibuat dengan metode FIFO, terjadi penambahan / Insert simpul didepan.

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, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Circular Double Linked List

Ini adalah 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 adalah

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