03/10/2013
STRUKTUR DATA By : Sri Rezeki Candra Nursari
2 SKS
Literatur • Sjukani Moh., (2007), “Struktur Data (Algoritma & Struktur Data 2) dengan C, C++”, Mitra Wacana Media • Utami Ema. dkk, (2007),”Struktur Data (Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux)”, Graha Ilmu • Hubbard Jhon, R., Ph.D, (2000), “Schaum’s Outline Of Theory and Problems of Data Structures With C++” McGraw-Hill • Bambangworawan Paulus., (2004), “Struktur Data Dengan C”, Andi Yogyakarta
1
03/10/2013
Materi 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Data dan Struktur Data Array Struktur dan Record Pointer Linked List Stack (Tumpukan) Queue (Antrian) Tree (Pohon) AVL Tree Heap dan B-Tree Sorting Search Hashing Graph
LINKED LIST Pertemuan 05
2 SKS
2
03/10/2013
Linked List • Struktur Linked List terbagi menjadi 4 macam, yaitu : 1. 2. 3. 4.
Linear Single Linked List Linear Double Linked List Circular Single Linked List Circular Double Linked List
22
28
63
RIGHT
LAST
LEFT INFO
RIGHT
LEFT INFO
RIGHT
LEFT INFO
FIRST
RIGHT
LEFT INFO
2. Linear Double Linked List
66
• Linear Double Linked List adalah doubly linked list lurus dengan pointer ganda, yaitu ada dua buah pointer. Jadi dalam struktur simpul ada dua elemen/field/variabel yang bertipe pointer. Yang pertama menunjuk atau berisi alamat simpul sebelumnya atau perivious node, dan yang kedua menunjuk simpul berikutnya atau next node
3
03/10/2013
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 1. 2. 3. 4. 5.
Inisialisasi linked list Pembuatan sebuah simpul Pembuatan simpul awal Melakukan insert kanan / sisip elemen terakhir Melakukan insert kiri / sisip elemen awal
6. 7.
Melakukan insert tengah / sisip elemen tengah Melakukan delete kanan / hapus elemen akhir
8. 9.
Melakukan delete kiri / hapus elemen awal Melakukan delete tengah / hapus elemen tengah
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 1.
Inisialisasi linked list
2.
Pembuatan sebuah simpul
. . . .
4
03/10/2013
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 3.
Pembuatan simpul awal
4.
Melakukan insert kanan / sisip elemen terakhir
.
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 5.
Melakukan insert kiri / sisip elemen awal
6. . . . . .
Melakukan insert tengah / sisip elemen tengah
5
03/10/2013
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 7. Melakukan delete kanan / hapus elemen akhir
8. . . . . .
Melakukan delete kiri / hapus elemen awal
2. Linear Double Linked List • Proses DLLL (Double Linked List Linear), adalah 7. Melakukan delete tengah / hapus elemen tengah
6
03/10/2013
3. Circular Single Linked List LAST FIRST
INFO LINK INFO LINK 22
28
INFO LINK 66
INFO LINK 63
• Circular Single Linked List adalah Single List List dimana link simpul terakhir bukan diisi dengan null, melainkan diisi dengan alamat simpul pertama yaitu simpul yang ditunjuk oleh pointer FIRST, sehingga menciptakan efek melingkar “sesuai arah jarum jam”
3. Circular Single Linked List • Proses SLLC (Single Linked List Circular), adalah 1. 2. 3. 4.
Pembuatan sebuah simpul Pembuatan simpul awal Melakukan insert kanan / sisip elemen terakhir Melakukan insert kiri / sisip elemen awal
5. 6.
Melakukan insert tengah / sisip elemen tengah Melakukan delete kanan / hapus elemen akhir
7. 8.
Melakukan delete kiri / hapus elemen awal Melakukan delete tengah / hapus elemen tengah
7
03/10/2013
3. Circular Single Linked List • Proses SLLC (Single Linked List Circular), adalah 1.
Pembuatan sebuah simpul
2. . . . . .
Pembuatan simpul awal
3. Circular Single Linked List • Proses SLLC (Single Linked List Circular), adalah 3.
Melakukan insert kanan / sisip elemen terakhir
4.
Melakukan insert kiri / sisip elemen awal
. . . . .
8
03/10/2013
3. Circular Single Linked List • Proses SLLC (Single Linked List Circular), adalah 5. Melakukan insert tengah / sisip elemen tengah
6.
Melakukan delete kanan / hapus elemen akhir
. . . . . .
3. Circular Single Linked List • Proses SLLC (Single Linked List Circular), adalah 7.
Melakukan delete kiri / hapus elemen awal
8. . , , , ,
Melakukan delete tengah / hapus elemen tengah
9
03/10/2013
22
28
63
RIGHT
LAST
LEFT INFO
RIGHT
LEFT INFO
RIGHT
LEFT INFO
FIRST
RIGHT
LEFT INFO
4. Circular Double Linked List
66
• Circular Double Linked List adalah doubly linked list dimana pointer RIGHT simpul paling kanan berisi alamat simpul paling kiri, dan pointer LEFT simpul paling kiri berisi alamat simpul paling kanan, sehingga menciptakan efek melingkar baik menurut ‘arah jarum jam’ maupun ‘arah kebalikannya’
4. Circular Double Linked List • Double Linked List Circular adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field/elemen, yaitu 1 field pointer yang menunjuk pointer berikutnya (next/right), 1 field menunjuk pointer sebelumnya (prev/left), serta sebuah field yang berisi data untuk node tersebut • Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular
10
03/10/2013
4. Circular Double Linked List • Pengertian Double Linked List Circular – Double: artinya field pointernya terdiri dari dua buah dan dua arah, yaitu prev/left dan next/right
–Linked List: artinya node-node tersebut saling terhubung satu sama lain –Circular: artinya pointer next dan prevnya menunjuk ke dirinya sendiri
4. Circular Double Linked List • Node – Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya – Untuk pembentukan node baru, mulanya pointer next/right dan prev/left akan menunjuk ke dirinya sendiri – Jika sudah lebih dari satu node, maka pointer prev/left akan menunjuk ke node sebelumnya, dan pointer next/right akan menunjuk ke node sesudahnya.
11
03/10/2013
4. Circular Double Linked List • Head –Dibutuhkan satu buah variabel pointer : head –Head akan selalu menunjuk pada node pertama
4. Circular Double Linked List • Fungsi untuk mengetahui kosong tidaknya DLLC (Double Linked List Circular) • Penamahan elemen/data didepan/diawal – Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya – Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan
node terdepan dibutuhkan pointer bantu.
12
03/10/2013
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 1. 2. 3. 4.
Pembuatan sebuah simpul Pembuatan simpul awal.b (simpulyang sudah dibuat, dijadikan sebagai simpul awal) Melakukan insert kanan / sisip elemen terakhir Melakukan insert kiri / sisip elemen awal
5. Melakukan insert tengah / sisip elemen tengah 6. Melakukan delete kiri / hapus elemen awal 7.
Melakukan delete kanan / hapus elemen akhir
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 1. Pembuatan sebuah simpul
13
03/10/2013
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 2.
Pembuatan simpul awal.b (simpulyang sudah dibuat, dijadikan sebagai simpul awal)
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 3.
Melakukan insert kanan / sisip elemen terakhir
14
03/10/2013
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 4.
Melakukan insert kiri / sisip elemen awal
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 5. Melakukan insert tengah / sisip elemen tengah
15
03/10/2013
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 6. Melakukan delete kiri / hapus elemen awal
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 7.
Melakukan delete kanan / hapus elemen akhir
16
03/10/2013
4. Circular Double Linked List • Proses DLLC (Double Linked List Circular), adalah 8.
Melakukan delete tengah / hapus elemen Tengah
17
