03 LINKED LIST Slide
0
voice
Pada perkuliahan ini kita akan membahas topik linked list atau senarai berkait.
Slide
1
voice
Terdapat tujuh bilangan bulat yang nilainya terurut secara menaik (ascending) di dalam sebuah larik bilangan bulat (array of integer) berkapasitas seribu. Ke dalam larik ini akan ditambahkan sebuah bilangan bernilai 23 dan setelah ditambahkan semua nilai harus tersusun menaik. Bagaimana prosesnya?
Slide
2
voice
Langkah pertama: geser ke kanan semua bilangan yang nilainya lebih besar daripada 23. Penggeseran dimulai dari bilangan yang bernilai paling besar. Bilangan bernilai 38 akan menempati posisi [7]. Bilangan bernilai 33 akan menempati posisi [6] dan seterusnya. Posisi [3] menjadi kosong.
© Thompson Susabda Ngoen
1|Page
Slide
3
voice
Langkah kedua: Masukkan bilangan 23 di tempat yang kosong, yaitu di posisi [3].
Slide
4
voice
Kasus lain. Terdapat tujuh bilangan bulat yang nilainya terurut secara menaik (ascending) di dalam sebuah larik bilangan bulat (array of integer) berkapasitas seribu. Salah satu bilangan yaitu yang bernilai 15 akan dihapus dari larik. Setelah dihapus larik tidak boleh bolong di tengah dan semua nilai harus tersusun menaik. Bagaimana prosesnya?
Slide
5
voice
Langkah ke-1 Pindahkan ke kiri satu posisi atau salin ke kiri semua bilangan yang nilainya lebih besar daripada 15, mulai dari bilangan bernilai 21. Bilangan bernilai 21 akan menempati posisi [1], bilangan 23 akan menempati posisi [2] dst.
© Thompson Susabda Ngoen
2|Page
Slide
6
voice
Langkah kedua Hapus bilangan di posisi [7].
Slide
7
voice
Pada kedua kasus kita melihat bahwa ada sejumlah data yang perlu digeser. Apakah terdapat cara lain yang lebih efisien sehingga penambahan data atau penghapusan data tidak memerlukan penggeseran sejumlah data lain? Ada, dengan menggunakan struktur data SENARAI BERKAIT atau LINKED LIST.
Slide
8
voice
Bentuk sebuah linked list atau senarai berkait yang paling sederhana adalah sekumpulan nodes (simpul-simpul) yang membentuk sebuah struktur linier seperti sebuah rantai. Setiap node (simpul) mengandung sebuah field berjenis pointer, yang biasa diberi nama next. Pointer next ini menunjuk atau mengacuh simpul berikutnya. Pointer next ini berfungsi seperti kait, mengait satu simpul ke simpul berikutnya.
Pointer next simpul terakhir tidak menunjuk simpul lain melainkan diberi nilai NULL atau 0. NIlai NULL atau 0 ini menandakan bahwa simpul tersebut tidak menunjuk simpul lain. Pada setiap node (simpul) selain terdapat pointer next juga terdapat elemen-elemen data lainnya.
© Thompson Susabda Ngoen
3|Page
Slide
9
voice
Simpul pertama sebuah linked list disebut head dari linked list tersebut. Simpul terakhir sebuah linked list disebut tail dari linked list tersebut. Pada saat diimplementsi dalam penulisan program, simpul pertama ini ditunjuk oleh atau diacu dengan sebuah variabel pointer yang umumnya diberi nama head, dan simpul terakhir ditunjuk oleh atau diacu dengan sebuah variabel pointer yang umumnya diberi nama tail. Pointer tail bersifat opsional. Pada gambar terlampir, kotak berwarna kuning menandakan variabel pointer.
Slide
10
voice
Terdapat dua jenis linked list yaitu singly-linked list atau senarai berkait tunggal dan doubly-linked list atau senarai berkait ganda. Pada singly-linked list setiap simpul mempunyai satu kait, maksudnya terdapat satu field yang berjenis pointer, digunakan untuk menunjuk ke atau mengait ke simpul berikutnya. Pada doubly-linked list setiap simpul mempunyai dua kait, maksudnya terdapat dua field yang berjenis pointer, yang satu digunakan untuk menunjuk ke atau mengait ke simpul berikutnya, dan yang lain digunakan untuk menunjuk ke atau mengaitkan ke simpul sebelumnya. Pada gambar terlampir, kotak berwarna kuning menandakan variabel pointer.
Slide
11
voice
Bagaimana dengan pemakaian memori oleh linked list? Pointer head dan pointer tail berada di local stack memory, di lokasi yang sama dengan variable lainnya. Simpul-simpul linked list berada di heap memory. Simpulsimpul linked list dibentuk atau dialokasi secara dinamis. Dialokasi secara dinamis maksudnya adalah ketika sebuah simpul mau dibuat maka barulah pada saat itu memory yang diperlukan untuk itu dimintakan dari operating system.
© Thompson Susabda Ngoen
4|Page
Slide
12
voice
Pada ilustrasi linked list, pointer next, pointer head, pointer tail digambarkan sebagai sebuah panah. Sebetulnya apa isi pointer-pointer tersebut? Seperti kita ketahui, variabel pointer atau disingkat sebagai pointer adalah variabel yang berisi alamat memori. Pointer tidak berisi data seperti bilangan bulat, bilangan pecah, atau karakter ASCII. Pointer berisi alamat memori komputer. Pada ilustrasi berikut pointer head menunjuk ke simpul bernilai 17. Misalkan Secara fisik simpul bernilai 17 ini menempati heap memory mulai dari address 2000. Maka variabel pointer head berisi address 2000. Misalkan secara fisik simpul bernilai 92 menempati heap memory mulai dari address 2800 maka pointer next pada simpul bernilai 17 berisi address 2800. Pointer next simpul terakhir, simpul bernilai 45 tidak menunjuk simpul lain maka pointer next simpul ini berisi nilai nol.
Slide
13a
voice
Selanjutnya kita melihat coding untuk singly-linked list. Akan dibentuk dua class yaitu StringLinkedList dan class StringNode. Coding ini membentuk sebuah class bernama StringNode yang simpulnya terdiri atas dua field atau dua data member yaitu sebuah string bernama elem dan sebuah pointer bernama next. Class StringNode tidak mempunyai member function. Class StringNode digunakan untuk membentuk objek atau simpul yang menjadi elemen data class StringLinkedList. Karena data member (variabel) di dalam StringNode ini akan diakses langsung oleh StringLinkedList maka pada deklarasi StringN StringNode ode ditambahkan instruksi friend class StringLinkedList.
Slide
13b
voice
Class StringLinkedList mempunyai sebuah data member bertipe pointer to StringNode yang bernama head. Class ini mempunyai constructor, destructor, dan empat function member lain yaitu empty(), front(), addFront(), dan removeFront().
© Thompson Susabda Ngoen
5|Page
Slide
14
voice
Constructor memberi nilai NULL kepada pointer head, untuk menandakan bahwa linked list kosong, belum ada simpul satu pun. Destructor bertugas menghapus simpul yang ada satu per satu sampai habis. Penghapusan simpul ini dilakukan dengan memanggil function removeFront(). Function empty() akan mengembalikan nilai true jika linked list kosong dan akan mengembalikan nilai false jika linked list ada simpul. Caranya adalah dengan membandingkan pointer head dengan NULL. Function front() akan mengembalikan elemen data simpul pertama, yaitu simpul yang ditunjuk pointer head.
Slide
15
voice
Function addFront() bertujuan menambah simpul baru di posisi depan linked list. Setelah ditambahkan maka simpul baru menjadi simpul pertama atau simpul terdepan linked list. Perhatikan ilustrasi berikut. Terdapat sebuah singly-linked list yang terdiri atas tiga simpul dengan nilai MSP, ATL, dan BOS. Simpul pertama yang bernilai MSP ditunjuk pointer head. Ke dalam linked list ini akan ditambahkan sebuah simpul baru bernilai LAX di depannya. Setelah ditambahkan maka jumlah simpul menjadi empat. Simpul pertama atau simpul terdepan bernilai LAX ditunjuk pointer head. Pointer next pada simpul LAX menunjuk simpul MSP dan seterusnya. Proses menambah simpul di depan singly-linked list terdiri atas empat langkah: 1) memesan atau mengalokasi memori untuk simpul baru berjenis hStringNode dengan menggunakan instruksi new. Simpul baru ini ditunjuk pointer v. 2) Copy-kan elemen data e ke dalam data member elem pada simpul baru yang ditunjuk pointer v. 3) Pointer next simpul baru diberi nilai seperti pointer head. Akibatnya pointer next simpul baru akan menunjuk ke simpul yang ditunjuk pointer head, yaitu menunjuk simpul pertama. Dengan proses ini maka simpul baru menjadi terhubung dengan simpul-simpul lain. 4) Pointer head diberi nilai seperti pointer v. Akibatnya pointer head menunjuk ke simpul baru.
Slide
16a
voice
Slide ini mengilustrasikan proses penambahan simpul baru ke dalam singly-linked list yang masih kosong. Kotak yang berwarna kuning menandakan tipe data pointer. Kotak kuning berisi garis miring menandakan NULL pointer. Kotak yang berwarna biru menandakan tipe data string. Perhatikan gambar ke-1. Karena linked list masih kosong maka pointer head diilustrasikan sebagai kotak kuning dengan garis miring. Pesan satu simpul baru bertipe StringNode dan tunjuk simpul ini dengan pointer v. Intruksinya StringNode* v = new StringNode
Simpul ini mempunyai dua field, satu field untuk data tipe string dan yang satu lagi bertipe pointer. Tanda Tanya pada kedua field ini menandakan bahwa kedua field berisi sampah memori. Simpul baru ini ditunjuk pointer v.
© Thompson Susabda Ngoen
6|Page
Slide
16b
voice
Langkah ke-2 Copy isi parameter e ke dalam field elem pada simpul yang ditunjuk pointer v. Dalam ini berisi BOS. Instruksinya: v -> elem = e Langkah ke-3, ubah pointer next pada simpul baru ini sehingga bernilai sama demgam head. Dengan perkataan lain Pointer next pada simpul yang ditunjuk pointer v diberi nilai seperti pointer head. Instruksinya: v -> next = head Langkah ke-4, ubah pointer head sehingga menunjuk ke simpul baru ini. Dengan perkataan lain, pointer head diberi nilai seperti pointer v. Instruksi: head = v
Slide
17
voice
Slide ini mengilustrasikan proses penambahan simpul baru ke dalam singly-linked list yang sudah ada simpul. Keempat statement-nya sama dengan statement pada slide sebelumnya. Langkah ke-1. instruksi new StringNode membentuk sebuah simpul atau sebuah objek bertipe StringNode. Simpul ini ditunjuk pointer v. Langkah ke-2 Copy isi parameter e ke dalam field elem. Langkah ke-3, ubah pointer next pada simpul baru sehingga menunjuk ke simpul pertama. Langkah ke-4, ubah pointer head sehingga menunjuk ke simpul baru.
© Thompson Susabda Ngoen
7|Page
Slide
18
voice
Kita akan melihat bagaimana cara menghapus simpul pertama atau terdepan singly linked list. Sebagai ilustrasi terdapat singly linked list dengan empat simpul. Simpul terdepan yang berdata LAX mau dihapus dari linked list. Pointer head harus dipindahkan simpul kedua yang bernilai MSP. Setelah itu simpul LAX dihapus.
Slide
19
voice
Langkah ke-1 Sediakan sebuah pointer, misalnya old. Pointer ini digunakan untuk menunjuk ke simpul pertama linked list. Dalam ilustrasi ini pointer old menunjuk ke simpul berdata LAX. Dengan perkataan lain, Sediakan sebuah pointer, misalnya old. Pointer old diberi nilai seperti pointer head. Instruksinya: StringNode* old = head Langkah ke-2 Pointer head menunjuk simpul berikut. Dalam ilustrasi ini menunjuk ke simpul berdata MSP. Dengan perkataan lain, Pointer head diberi nilai seperti pointer next pada simpul yang ditunjuk pointer head pada gambar satu Instruksinya: head = head -> next Langkah ke-3 Hapus simpul yang pertama yaitu simpul yang ditunjuk pointer old. Instruksinya: delete old
Slide
20
voice
Ini adalah deklarasi class SNode yang akan menjadi simpul linked list. Simpul atau objek yang dibentuk dari class SNode mempunyai dua data member atau dua variabel yaitu elem yang bertipe data generik dan next yang bertipe data pointer. Perhatikan data member elem yang bertipe data E. Pas di atas deklarasi class SNode terdapat statement template
. Deklarasi ini menyatakan bahwa E adalah tipe data yang bersifat generik, maksudnya dapat ditentukan oleh user sesuai kebutuhan.
Instruksi friend clas SLinkedList<E> menyatakan class SLinkedList dapat langsung mengakses data member elem dan next. Karena class SNode ini bersifat generik maka class SLinkedList juga harus bersifat generik. Karena class SLinkedList bersifat generik maka harus ditambahkan dua statement yang berwarna biru sebelum deklarasi class SNode.
© Thompson Susabda Ngoen
8|Page
Slide
21
voice
Slide ini dan dua slide berikutnya berisi definisi class SLinkedList. Definisi class ini me-include header file SNode.h. Class SLinkedList hanya mempunyai satu data member yaitu head. Class ini mempunyai constructor, destructor, dan empat member function lain. Constructor SLinkedList memberi nilai NULL kepada pointer head.
Slide
22
voice
Destructor bertujuan menghapus semua simpul yang ada, dengan cara memanggil function removeFront() berkalikali sampai linked list menjadi kosong. Function empty() mengembalikan nilai true jika linked list kosong alias belum mempunyai simpul satu pun. Function empty() mengembalikan nilai false jika ada simpul di dalam linked list. Algoritmanya adalah dengan membandingkan pointer head dengan NULL. Function front() mengembalikan elemen data simpul pertama, yaitu simpul yang ditunjuk pointer head. Function front() tidak menyebabkan perubahan isi linked list. Function addFront() menambah simpul baru pada bagian depan linked list. Pada slide sebelumnya kita sudah membahas hal ini.
Slide
23
voice
Function removeFront() menghapus simpul pertama, yaitu simpul yang ditunjuk pointer head. Pada slide sebelumnya kita sudah membahas hal ini.
© Thompson Susabda Ngoen
9|Page
Slide
24
voice
Program example 03-01 membentuk singly linked list yang elemen datanya bertipe string. Setiap string (kata) yang diketikkan user ditambahkan di depan linked list dengan cara memanggil function addFront(). Akibatnya string (kata) yang terakhir diketikkan menjadi simpul yang pertama ketika diakses. Selanjutnya simpul linked list dihapus semua dengan mengulangi dua proses berkut: 1. mencetak elemen data pada simpul terdepan 2. menghapus simpul terdepan.
Slide
25
voice
Program example 03-02 mirip dengan program example 03-01, bedanya adalah pada tipe data simpul yang berupa integer.
Slide
26
voice
Mind Twister 03-01 Anda diminta untuk mengembangkan class SLinkedList dengan menambahkan 5 member function. Function addBack() berfungsi menambah simpul di ujung atau posisi akhir linked list. Function removeBack() berfungsi menghapus simpul yang terakhir linked list. Function insertAfter() berfungsi menambah simpul baru pas setelah simpul dengan nilai tertentu. Function removeCertain() berfungsi menghapus simpul bernilai tertentu. Function printList() berfungsi mencetak isi simpul satu persatu.
© Thompson Susabda Ngoen
10 | P a g e
Slide
27
voice
Mind twister 03-02. Buat sebuah class bernama OrderedList yang mengatur penambahan simpul ke dalam linked list sehingga nilai simpul terurut menaik. Selain itu juga buat sebuah program yang menggunakan OrderedList tersebut.
Slide
28
voice
Doubly linked list adalah senarai berkait yang simpulsimpul dapat ditelusuri dari dua arah: Forward atau arah maju, mulai dari simpul pertama, kedua, sampai dengan simpul terakhir. Backward atau arah mundur, mulai dari simpul terakhir, simpul kedua dari akhir, mundur sampai dengan simpul pertama. Simpul pembentuk doubly-linked list mempunyai dua data member yang bertipe pointer, yaitu next dan prev. Pointer next digunakan menunjuk simpul berikutnya. Pointer prev digunakan untuk menunjuk simpul sebelumnya. Biasanya double-linked list ditunjuk dua pointer yaitu header atau head dan trailer atau tail. Pointer head digunakan untuk menunjuk simpul pertama dan pointer tail digunakan untuk menunjuk simpul terakhir.
Slide
29
voice
Slide berikut menjelaskan cara menyisipkan (insert) sebuah simpul di posisi setelah simpul tertentu. Terdapat simpul berelemen data v, simpul ini bukan simpul terakhir. Simpul berelemen data Z akan disisipkan di posisi setelah simpul berelemen data V sehingga simpul berelemen data Z akan berada di antara simpul berelemen data V dan W.
© Thompson Susabda Ngoen
11 | P a g e
Slide
30
voice
Untuk menyisipkan Z setelah V perlu mengubah empat pointer atau kait yang ditunjuk panah berwarna merah. Urutannya harus benar agar tidak ada kait yang terputus atau simpul menjadi hilang.
Slide
31
voice
Urutannya adalah 1. ubah pointer prev pada simpul z agar menunjuk simpul v 2. ubah pointer next pada simpul z agar menunjuk simpul w 3. ubah pointer prev pada simpul w agar menunjuk simpul z 4. ubah pointer next pada simpul v agar menunjuk simpul z Satu hal yang perlu diklarifikasi adalah bahwa sebuah pointer yang menunjuk sebuah simpul, selalu menunjuk ke awal simpul meskipun di dalam ilustrasi mungkin tergambar menunjuk ke field yang di tengah atau menunjuk pointer next.
Slide
32
voice
Langkah pertama, Ubah pointer prev pada simpul yang mau disisipkan sehingga menunjuk ke simpul yang di dalamnya terdapat data v. Dengan perkataan lain, Ubah pointer prev pada simpul yang ditunjuk pointer node sehingga menunjuk ke simpul yang ditunjuk pointer curr. Instruksinya: node -> prev = curr
© Thompson Susabda Ngoen
12 | P a g e
Slide
33
voice
Langkah kedua Ubah pointer next pada simpul yang mau disisipkan sehingga menunjuk ke simpul yang di dalamnya terdapat data w. Dengan perkataan lain, Ubah pointer next pada simpul yang ditunjuk pointer node sehingga menunjuk ke simpul yang ditunjuk pointer next pada simpul yang ditunjuk pointer curr. Instruksinya: node -> next = curr -> next
Slide
34
voice
Langkah ketiga Ubah pointer prev pada simpul yang di dalamnya terdapat data w sehingga menunjuk ke simpul yang di dalamnya terdapat data z. Dengan perkataan lain, Ubah pointer prev pada simpul yang ditunjuk pointer next pada simpul yang ditunjuk pointer node sehingga menunjuk simpul yang ditunjuk pointer node. Instrukinya: node->next->prev = node ATAU Ubah pointer prev pada simpul yang ditunjuk pointer next pada simpul yang ditunjuk pointer curr sehingga menunjuk simpul yang ditunjuk pointer node. Instrukinya: curr->next->prev = node
Slide
35
voice
Langkah keempat Ubah pointer next pada simpul yang di dalamnya terdapat data v sehingga menunjuk simpul berdata z. Dengan perkataan lain, Ubah pointer next pada simpul yang ditunjuk pointer curr sehingga menunjuk ke simpul yang ditunjuk pointer node. Instruksinya: curr -> next = node
© Thompson Susabda Ngoen
13 | P a g e
Slide
36
voice
Berikut adalah ilustrasi menghapus sebuah simpul yang diapit dua simpul lain. Dalam contoh ini menghapus simpul yang didalamnya terdapat data v. Proses yang dilakukan adalah 1. mengubah pointer prev pada simpul yang di dalamnya terdapat data w sehingga menunjuk ke simpul yang di dalamnya terdapat data u, 2. mengubah pointer next pada simpul yang di dalamnya terdapat data u sehingga menunjuk ke simpul yang di dalamnya terdapat data w, 3. menghapus simpul v.
Slide
37
voice
Langkah pertama Ubah pointer prev pada simpul yang di dalamnya terdapat data w sehingga menunjuk ke simpul yang di dalamnya terdapat data u. Atau dengan pernyataan lain Ubah pointer prev pada simpul yang ditunjuk oleh pointer next pada simpul yang ditunjuk pointer next sehingga menunjuk ke simpul yang ditunjuk pointer curr Instruksinya: node->next->prev = curr
Slide
38
voice
Langkah kedua, Ubah pointer next dari simpul yang di dalamnya terdapat data u sehingga menunjuk ke simpul yang di dalamnya terdapat data w. Dengan perkataan lain, ubah pointer next pada simpul yang ditunjuk pointer curr sehingga menunjuk ke simpul yang ditunjuk oleh pointer next pada simpul yang ditunjuk pointer node. Instruksinya: curr-> next = node->next
© Thompson Susabda Ngoen
14 | P a g e
Slide
39
voice
Langkah ke-3, Menghapus simpul yang ditunjuk pointer node dengan menggunakan instruksi delete node
Slide
40
voice
Simulasikan / ilustrasikan / gambarkan keempat proses berikut pada doubly-linked list. Diasumsikan bahwa linked list tidak kosong, sudah mempunyai simpul (node) satu atau lebih. Pointer head menunjuk simpul pertama dan pointer tail menunjuk simpul terakhir. 1. addFront, menambah simpul baru di depan (awal) linked list. 2. addBack, menambah simpul baru di ujung (akhir) linked list 3. removeFront, menghapus simpul pertama linked list 4. removeBack, menghapus simpul terakhir linked list
Slide
41
voice
Sebagian bahan powerpoint ini bersumber dari buku nd berjudul Data Structures and Algorithm in C++, 2 edition yang menjadi buku teks mata kuliah ini.
© Thompson Susabda Ngoen
15 | P a g e
