Pointer dan Linked List

Pointer adalah suatu variabel yang menunjuk ke alamat memori yang digunakan untuk menampung data yang akan diproses.

Deklarasi Variabel Pointer :
Var <Nama Variabel> : ^<Tipe Data>

Contoh Pendeklarasian :
Var
JumlahData : ^Integer;
NamaSiswa : ^String[25];
NilaiSiswa : ^Real;

Pendeklarasian variabel pointer tidak jauh berbeda dengan pendeklarasian variabel biasa, hanya perlu ditambahkan simbol topi ( ^ ) – biasa juga disebut ceret atau circumflex. Simbol topi tersebut menandakan bahwa variabel tersebut menunjuk ke lokasi tertentu di memori.

Varibel Biasa vs Variabel Pointer
Variabel Pointer adalah suatu variabel yang menunjuk ke alamat memori yang digunakan untuk menampung data yang akan diproses, seperti digambarkan dibawah ini:


P adalah variabel pointer yang menunjuk ke alamat memori 100 yang berisi data bertipe string “Aku”. Apabila anda ingin menambah data dengan menggunakan variabel yang berbeda, maka anda dapat mendeklarasikan variabel pointer baru misalnya Q dan R dst sehingga tampak sbb :

Untuk membedakan antara variabel pointer dengan variabel biasa, perhatikan contoh berikut :





Operasi Pada Pointer
Pada pointer ada dua operasi dasar yang dapat dilakukan yaitu :
1. Operasi mengkopi simpul
2. Operasi mengkopi isi simpul

Variabel Dinamik
Variabel dinamik dibentuk dengan menggunakan variabel pointer yang telah dialokasikan. Pengalokasian variabel ini menggunakan statement New(). Jika kita tidak membutuhkan variabel dinamik yang telah kita bentuk maka kita dapat menghapusnya dari memory dengan menggunakan statemen Dispose(). Sampa saat ini kita baru membentuk satu buah variabel dinamik. Jika kita memakai banyak variabel dinamis maka kita akan membutuhkan banyak variabel pointer. Oleh karena itu ada baiknya jika kita hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut dengan linked list.

Linked List

Apabila setiap kali anda ingin menambahkan data selalu dengan menggunakan variabel pointer yang baru, anda akan membutuhkan banyak sekali variabel pointer(penunjuk). Oleh karena itu ada baiknya jika anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Jika diterjemahkan, maka berarti suatu daftar isi yang saling
berhubungan. Untuk lebih jelasnya perhatikan gambar di bawah ini :

Pada gambar diatas tampak bahwa sebuah data terletak pada sebuah lokasi memory area. Tempat yang disediakan pada suatu area memory tertentu untuk menyimpan data dikenal dengan sebutan node/simpul. Pada setiap node memiliki pointer(penunjuk) yang menunjuk ke simpul berikutnya sehingga terbentuk suatu untaian dan dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List. (ket: Nill tak memiliki nilai apapun. Biasanya linked list pada titik akhirnya akan menunjuk ke Nill).

Linked list merupakan suatu variabel yang bertipe pointer yang membentuk suatu untaian yang saling berhubungan. Tiap untaian tersebut diletakkan pada memory. Tempat yang disediakan pada suatu area memori tertentu untuk menyimpan data dikenal dengan sebutan Node/Simpul. Linked list juga disebut dengan seranai beranai merupakan suatu variabel pointer yang simpulnya bertipe
Record.


Deklarasi Linked List di dalam Pascal :
Type
PSimpul = ^Simpul
Simpul = Record
Info : Tipe Data;
Next : PSimpul;
End;
Var
Head, Tail : PSimpul;

Variabel Head dan Tail selanjutnya dialokasikan dengan statement New(), yang dihasilnya nantinya merupakan linked list yang sudah terbentuk. Ada beberapa hal yang harus diketahui mengenai linked list, diantaranya adalah :
1. Linked list selalu memiliki pointer petunjuk yang selalu menunjuk pada awal dari list yang disebut Head.
2. Linked list juga selalu memiliki pointer petunjuk menunjuk pada akhir dari list yang disebut Tail, kecuali untuk jenis circular.
3. Setiap simpul yang terbentuk selalu memiliki nilai NIL, kecuali jika simpul tersebut sudah ditunjuk oleh simpul yang lainnya (Linked list belum terhubung).
4. Posisi simpul terakhir pada linked list selalu bernilai NIL karena ia tidak menunjuk pada simpul yang lainnya, kecuali bentuk circular.
5. Operasi yang dapat dilakukan pada Linked List diantaranya adalah :
a. Menambah Simpul (di Depan, Belakang dan Tengah).
b. Menghapus Simpul (di Depan, Belakang dan Tengah).
c. Membaca isi linked list (Membaca maju dan mundur).

 

Ada berbagai jenis linked list :
1. Single Linked List / Linked list satu arah (One Way List)
Disebut demikian karena pada setiap simpul hanya memiliki satu buah field yang berhubungan dengan simpul berikutnya. Dalam pembuatan Single Linked List dapat menggunakan 2 metode, yaitu:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
LIFO adalah suatu metode pembuatan Linked List dimana data yang masuk paling akhir adalah data yang keluar paling awal.
• FIFO (First In First Out), aplikasinya : Queue (Antrian)
LIFO adalah suatu metode pembuatan Linked List dimana data yang masuk paling awal adalah data yang keluar paling awal juga.
Linked list ini memiliki beberapa variasi lain diantaranya :
a. Header Single Linked List : Jenis single linked list yang memiliki simpul tambahan pada awal simpul yang berguna untuk informasi tambahan.
Contoh di bawah ini merupakan header single linked list yang pada simpul header-nya berisi informasi mengenai banyaknya simpul di dalam list.

b. Circular Single Linked List : Jenis single linked list yang tidak pernah mempunyai tail atau tidak pernah NIL selalu berputar Head = Tail;
 

c. Header Circular Single Linked List : Jenis circular single linked list yang memiliki simpul tambahan di awal sebagai informasi tambahan. Contoh di bawah ini merupakan circular header single linked list yang pada simpul headernya berisi informasi mengenai banyaknya simpul di dalam list.








 2. Double Linked List / Linked list dua arah (Two Way List)
Linked List ini memiliki dua buah field yang digunakan untuk menunjuk ke simpul sebelumnya dan ke simpul sesudahnya. Banyak digunakan untuk mempermudah proses pencarian simpul dalam suatu seranai beranai. Linked list ini memiliki beberapa variasi lain diantaranya :
a. Header Double Linked List : Jenis double linked list yang memiliki simpul tambahan pada awal simpul yang berguna untuk informasi tambahan.
b. Circular Double Linked List : Jenis double linked list yang tidak pernah mempunyai tail atau tidak pernah NIL selalu berputar Head = Tail;
c. Header Circular Double Linked List : Jenis circular double linked list yang memiliki simpul tambahan di awal sebagai informasi tambahan.