Link List

LINK LIST

PENDAHULUAN

q  Dalam suatu linier list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.

q  Misalkan ada 1500 item yang merupakan elemen dari  suatu linier list. Jika elemen ke-56 akan kita  keluarkan, maka elemen  ke-1 s/d elemen  ke-55 tidak akan berubah posisinya pada linier list tersebut. Tetapi elemen ke–57akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu  elemen pada  posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.

q  Untuk menyatakan keadaan diatas  diperlukan suatu konsep yang berbeda  dengan konsep sekuensial sebelumnya.

Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu  data.

DEFINISI

q  Linked list (one  way  list) adalah suatu  kumpulan elemen  data (yang  disebut sebagai node) dimana  urutannya ditentukan  oleh  suatu pointer.

q  Setiap elemen  (node) dari  suatu linked list terdiri atas dua bagian, yaitu:

Ø  INFO berisi informasi tentang elemne data yang bersangkutan.

Ø  NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya     yang dituju.

OPERASI  DASAR PADA LINKED LIST

q  Ada beberapa  aturan yang didefinisikan pada operasi didalam linked list yaitu:

Ø Jika P adalah  suatu variabel pointer, maka nilainya  adalah alamat atau lokasi dari variabel lain yang  dituju.

Ø Operasi yang  didefinisikan  pada  suatu variabel pointer adalah:

1.            Test apakah  sama dengan NULL

2.            Test untuk kesamaan denganvariabel pointer lain

3.            Menetapkan  sama dengan NULL

4.            Menetapkan menuju ke node lain

q  Notasi yang didefinisikan sehubungan dengan operasi diatas  adalah

1. NODE (P), artinya node yang  ditunjuk oleh pointer P
2. INFO (P), artinya  nilai INFO dari node yang ditunjuk pointer  P
3. NEXT (P), artinya  hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P

Antrian data pada pemrograman

Queue

Adalah suatu bentuk khusus dari linear list dengan operasi penyisipan (insertion) hanya pada salah satu sisi ( Rear/ belakang) dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya (Front/ depan) dari list.

Antrean   Q  = [ Q1, Q2, Q3,……….., QT]

          Front(Q) = bagian depan dari antrean Q

          Rear(Q)  = bagian belakang dari antrean Q

          Noel(Q)  = Jumlah elemen di dalam antrean ( berharga integer)

          Jadi :  Front(Q) = QT

                    Rear(Q) = Q1

                    Noel(Q) = T

Antrean beroperasi secara FIFO ( First In First Out) yang pertama masuk, yang pertama keluar.

q  Operasi dasar pada Antrean :

1.   CREATE(Q)

Operator untuk membentuk suatu antrean hampa

Q = [,…….,]

NOEL(CREATE(Q)) = 0

FRONT(CREATE(Q)) = tidak didefinisikan

REAR(CREATE(Q)) = tidak didefinisikan

2.   ISEMPTY(Q)

Operator yang menentukan apakah antrean Q hampa atau tidak.

Operand dari operator ISEMPTY adalah antrean.

Hasilnya bertipe data Boolean

ISEMPTY(Q) =TRUE   jika Q adalah antrean hampa (NOEL(Q) = 0)

                        FALSE jika Q bukan antrean kosong (NOEL(Q) ¹ 0)

3.   INSERT(E,Q)

Operator yang menyisipkan elemen E ke dalam antrean Q

Catt :      Elemen Q ditempatkan pada bagian belakang antrean dan antrean menjadi lebih panjang

Q = [ A, B, C, D]

REAR(INSERT(E,Q)) = E

FRONT(Q) = A

NOEL(Q) = 5

ISEMPTY(INSERT(E,Q)) = FALSE

4.   REMOVE(Q)

Operator yang menghapus elemen bagian depan dari antrean Q dan antrean menjadi lebih pendek

Jika   NOEL(Q) = 0 maka

REMOVE(Q) = ERROR ( UNDERFLOW)