LINKED LIST

Linked List adalah jenis struktur data yang merupakan suatu rangkaian atau daftar record sejenis yang dihubungkan dengan menggunakan bantuan pointer. Adapun pengalokasian daftar  tersebut dilakukan secara dinamis sehingga isi dari daftar tersebut dapat dimanipulasi(ditambah maupun dikurangi). Itulah sebabnya mengapa harus mengenal pointer dan pengalokasian memori terlebih dahulu.

Untuk memudahkan dalam memahami pengertian linked list, coba bayangkan apabila anda mendeklarasikan array record dengan banyak 10 elemen. Setiap kali program dijalankan, program akan memesan ruang memori sebesar 10x ukuran record. Sekarang apabila kita hanya menggunakan 5 buah elemen array maka  program akan tetap mengalokasikannya untuk sepuluh elemen. hal ini merupakan suatu pemborosan memori yang seharusnya di hindari dalam pembuatan program.

Dalam pemrograman linked list dibedakan menjadi sua jenis yaitu singlu linked list dan doubly linked list. Berikut ini penjelasan  dari masing-masing jenis tersebut.

a.Singly Linked List

Singly Linked List didefinisikan sebagai suatu rangkaian record sejenis yang dihubungkan satu buah pointer. Untuk lebih memahami, coba perhatikan contoh pendefinisian record dibawah ini.

type

  TNode = record

       data : integer;

       next : ^TNode;

end;

            Pada kode diatas kita dapat mendefinisikan tipe record dengan nama TNode dimana didalamnya terdapat dua buah field, yaitu data (bertipe integer) dan pointer next (bertipe pointerTNode). Field data akan digunakan untuk menyimpan nilai sedangkan field next berfungsi untuk menyimpan alamat dari record TNode lainnya yang terdapat dalam rangkaian.

Stack(Tumpukan)

Stack merupakan jenis singly linked list yang menerapkan konsep LIFO (Last In First Out). Artinya , pada rangkaian jenis ini record yang ditambahkan teralhir kali memudahkan pemahaman materi ini, coba bayangkan sebuah tumpukan piring yyang baru selesai dicuci. Pada tumpukkan tersebut, piring yang diletakkan pertama kali pasti akan diambil terakhir kali. Sebaiknya, piring yang diletakkan  terakhir kali, akan diambil pertama kali.       

    

Queque (Antrian)

         Queque merupakan jenis singly linked list yang menerapkan konsep FIFO( First In First Out). Untuk memahami pengertian queque, coba bayangkan sebuah antrian yang terdapat dibank, loket tiket kerea api, bioskop maupun tempat antrian lainnya. Disana, orang yang datang berikutnya akan dilayani sesuai dengan urutan antrian. Hal tersebutjuga berlaku didalam queque, data yang dimasukkan terakhir juga akan diambil terakhir kali. Ini tentu bertolak belakang dengan konsep yang terdapat didalam stack.

b. Doubly Linked List

Doubly Linked List merupakan linked list yang memiliki dua buah pointer sebagai penghubung rangkaiannya. Dua buah pointer? Ya benar dua pointer. Untuk lebih memahami, perhatika  terlebih dahulu definis tipe record dibawah ini.

type

   TNode = record;

        prev : ^TNode;

        data  : integer;

        next  :  ^TNode;

end;

Record TNode diatas memiliki dua buah pointyer sebagai fieldnya yaitu prev dan next. Pointer prev akan digunakan untik menunjuk ke alamat record sebelumnya sedangkan pointer next digunakan untuk menunjuk ke alamat record berikutnya. Hal yang perlu diperhatikan adalah pointer prev yang terdapat pada record pertama dan pointer next yang terdapat pada record terakhir, keduanya harus memiliki nilai nil.

c. Mengimplementasukan Linekd List dengan Rekursi

Rekursi juga dapat digunakan untuk menambahkan struktur baru kedalam linked list maupun menampilkan kembali struktur-struktur yang terdapat dalam rangkaian tersebut. Namun, perlu hati-hati dalam menggunakan rekursi karena apabila data yang dimasukkan terlalu banyak, maka dapat menyebabkan terjadinya stack overflow. Asumsikan bahwa kita memiliki struktur TNode dan pointer PNode yang didefinisikan seperti dibawah ini.

type

   PNode  = ^TNode;

   TNode   : record

       data  : integer;

       next   : PNode;

end;

Sumber : Teknik Pemrograman Pascal revisi ketiga, Budi Raharjo