Linked List

Linked List

—  Disebut juga one way list (bentuk linear dari kumpulan nilai data)

—  Linked list = nodes yang saling berkait

—  Setiap nodes dibagi menjadi 2 bagian :

            1. nilai data (INFO)

            2. pengait (LNK), disebut juga link field atau nextpointer field yang berisi alamat element berikutnya dalam daftar

            node terakhir berisi pengait dengan nilai spesial yang disebut dgn null pointer, yaitu “x” atau “0”.

Alokasi memori dan Operasi pada linked list

—  Apa itu AVAIL ?

—  Avail = free storage list

—  Avail = lokasi yang siap dimasukan nilai data baru (lokasi yg belum pernah dipakai atau lokasi yang kosong yang sudah pernah dipakai sebelumnya)

—  Garbage collection (koleksi sampah) = tehnik mengumpulkan seluruh lokasi yang telah di hapus ke dalam avail, yang dilakukan oleh sistem operasi

—  Informasi digunakan untuk memberitakan overflow error atau underflow error

—  Overflow, terjadi ketika dilakukan pemasukan data, avail = null

—  Underflow, terjadi ketika dilakukan penghapusan data, start = null

Penambahan node

—  Penambahan atau penyisipan node dalam sebuah linked list umumnya dilakukan di akhir daftar, namun, dapat pula dilakukan dibagian depan, belakang maupun diantara dua node.

—  Setiap operasi penambahan node akan berakibat berubahnya nilai dari LNK.

 

Penghapusan node

—  Sama hal nya dengan penambahan, operasi penghapusan dapat dilakukan dimana saja di dalam daftar, dan akan berakibat berubahnya nilai dari LNK yang terkait.

Two way list

—  Koleksi elemen data secara linear yang disebut dengan nodes

—  Setiap elemennya dibagi atas tiga bagian utama :

—  1. nilai data atau informasi (INFO)

—  2. penunjuk ke node sebelumnya (BACK)

—  3. penunjuk ke node berikutnya (FORW)

—  LOC = alamat node

—  FORW (LOCA) = LOCB                 BACK (LOCB) = LOCA

—  Atau dengan pengertian : lokasi berikutnya dari node A adalah lokasi node B, jika lokasi sebelumnya dari node B adalah lokasi node A.

Queues

—  Queues : bentuk dari linear list

—  Queues : penghapusan elemen dilakukan dari depan (FRONT), sedangkan penambahannya dilakukan dari belakang (REAR).

—  Penambahan elemen dalam Queues dapat mengakibatkan berubahnya nilai  rear.

—  Penghapusan elemen dalam Queues dapat mengakibatkan berubahnya nilai  front.

—  Penambahan berlebihan akan mengakibatkan overflow, sedangkan penghapusan dalam keadaan kosong akan mengakibatkan underflow.

—  Queues adalah bentuk berputar (circular)

—  Prinsip Queues = FIFO (first in first out)

—  Membuat Queues                    : CREATE (Q)

—  Menambah elemen                  : QINSERT

—  Menghapus elemen                 : QDELETE