Linked 6.3 & 7.3List NESTED LOOP
1
Linked List ( List yang di-Link satu dengan lainnya )
2
apa itu List ?
3
Contoh sebuah LIST 0
1
2
3
4
int A[5];
Array satu dimensi Disebut juga : Vector Kadang-kadang disebut juga : List
4
int A[5]; biasa diilustrasikan sebagai berikut : 0
1
2
3
4
Kadang-kadang diilustrasikan sebagai berikut : 0
1 2 3
4 5
int A[5];
List dengan 5 elemen 0
1
A[1]
2
3
4
A[4]
A[0]
secara umum : A[ I ]
6
int A[5]; List dengan 5 elemen, dengan alamat CONTIGUOUS 0
H21D8
1
2
3
H21DE
H21DA
4
H21E0
H21DC
#include<stdio.h> void main() { int A[5]; int I; for (I=0; I<=4; I++ ) printf( “\n%X”, &A[I] ); } Algo-1, jilid 2 hal. 10.03
akan tercetak : 21D8 21DA 21DC 21DE 21E0 Tiap elemen 2 BYTE
7
Apa itu alamat ?
8
Alamat atau Address adalah nomor Byte 0
1
2
3
4
RAM 64 MB
64*1024*1024-1 9
dengan: int A; terbentuk sebuah variabel (Elemen) sebesar 2 Byte
2 BYTE
Nomor BYTE pertama (paling kiri) - sering disebut MSB yang dipakai sebagai alamat
MSB = Most Significant Byte 10
int A[5];
List dengan 5 elemen 0
1
2
3
4
ini bukan Linked List bukan List yang di-link satu dengan yang lainnya tapi List yang bersisian atau bergandengan atau berurutan (contiguous) satu dengan lainnya, sedemikian rupa sehingga alamat tiap elemen bersambung satu dengan yang lainnya (contiguous). 11
Linked List List yang di-link satu dengan lainnya
Yang dimaksud dengan List disini adalah : sekumpulan elemen yang digabung menjadi satu kelompok yang disebut : structure,
setiap elemen mempunyai tipe data tersendiri
atau Vertex, atau Node, atau Titik, atau Record atau
Simpul
12
Linked List Contoh sebuah Simpul yang dinyatakan dengan: typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul;
INFO
LINK
Simpul dengan 2 elemen, INFO dan LINK
tipe : pointer, pointer untuk menunjuk node atau Simpul Tipe : integer untuk menyimpan data 13
typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul;
INFO
LINK
Tulisan dengan warna biru atau merah, adalah nama yang kita karang sendiri. Sedangkan tulisan dengan warna hitam adalah ketentauan dalam bahasa C
14
Contoh 4 buah simpul Linked List dalam memory tanda panah mengilustrasikan link
12 (2)
10 (4)
25 (1)
17 (3)
15
Proses pembuatan Simpul dan pembuatan Link sampai terbentuk sebuah Linked-List
16
Perhatikan memory berikut ini :
Belum ada Linked List
17
Akan dibuat sebuah Simpul Awal (simpul pertama)
18
Simpul pertama (1) sudah dibuat misal alamatnya = H1000
INFO LINK
(1) H1000
Bagaimana membuatnya akan diterangkan kemudian
19
Kemudian INFO akan diisi dengan nilai 25
INFO LINK
(1) H1000
20
INFO simpul pertama (1) sudah diisi dengan nilai 25
INFO LINK
25 (1) H1000
Bagaimana cara mengisinya akan diterangkan kemudian
21
Misal akan dibuat sebuah simpul baru (simpul kedua)
INFO LINK
25 (1) H1000
22
Sudah dibuat simpul kedua (2) Misal alamatnya = H0800 INFO LINK
H0800
(2)
INFO LINK
25 (1) H1000
Alamat simpul baru, tidak mesti lebih besar dari alamat simpul pertama
23
INFO simpul kedua (2) akan diisi dengan 12 INFO LINK
H0800
(2)
INFO LINK
25 (1) H1000
24
INFO simpul kedua (2) sudah diisi dengan nilai 12 INFO LINK
12 H0800
(2)
INFO LINK
25 (1) H1000
25
Akan di-link simpul pertama (1) dengan simpul kedua (2) INFO LINK
12 H0800
(2)
INFO LINK
25 (1) H1000
26
Simpul pertama (1) sudah di-link dengan simpul kedua (2)
LINK simpul pertama (1) diisi dengan alamat simpul kedua (2)
INFO LINK
12 H0800
(2)
INFO LINK
25
0800
(1) H1000
Bagaimana mengisi LINK simpul pertama dengan alamat simpul kedua akan diterangkan kemudian
27
INFO LINK
12 H0800
(2)
INFO LINK
25
0800
(1) H1000
Instruksi untuk meng-link yaitu mengisi alamat simpul (2) kedalam LINK simpul (1) termasuk intruksi atau tugas yang sulit
! 28
Kemudian :
Akan dibuat simpul (3), dan INFO simpul (3) diisi dengan 17 INFO LINK
12 H0800
(2)
INFO LINK
25
0800
(1) H1000
29
Sudah dibuat simpul ketiga (3) Misal alamatnya = H1400 INFO LINK
12 H0800
(2)
INFO LINK
25
0800
(1) H1000
INFO LINK
17 (3) H1400 30
Kemudian : Akan di-link simpul kedua (2) dengan simpul ketiga (3) INFO LINK
12 H0800
(2)
INFO LINK
25
0800
(1) H1000
INFO LINK
17 (3) H1400 31
Simpul kedua (2) sudah di-link dengan simpul ketiga (3) INFO LINK
12 H0800
1400
(2)
INFO LINK
25
0800
(1) H1000
INFO LINK
17 (3) H1400 32
Dan seterusnya dibuat simpul (4), INFO simpul (4) diisi 10 dan simpul (3) di-link dengan simpul (4) INFO LINK
12 H0800
1400
(2)
INFO LINK
INFO LINK
25
0800
(1) H1000
10 INFO LINK
17
(4) H1100
1100
(3) H1400 33
Sekarang sudah tercipta 4 buah simpul, dan sudah ter-link satu dengan lainnya, sehingga membentuk sebuah Linked List INFO LINK
12 H0800
1400
(2)
INFO LINK
INFO LINK
25
0800
(1) H1000
10 INFO LINK
17
(4) H1100
1100
(3) H1400 34
Untuk memudahkan melihat hubungan (link) antara satu simpul dengan simpul lainnya, maka semua isi LINK (yang berbentuk angka ) diganti atau direpresentasikan dengan tanda panah sehingga ilustrasinya menjadi sebagai berikut :
35
Sehingga:
Link dalam bentuk angka alamat tidak diperlukan lagi
INFO LINK
12 H0800
1400
(2)
INFO LINK
INFO LINK
25
0800
(1) H1000
10 INFO LINK
17
(4) H1100
1100
(3) H1400 36
INFO LINK
12 H0800
(2)
INFO LINK
10
25 (1) H1000
INFO LINK
INFO LINK
17
(4) H1100
(3) H1400 37
Alamat sebuah simpul, sebenarnya, tidak perlu diketahui atau dinyatakan INFO LINK
12 H0800
(2)
INFO LINK
10
25 (1) H1000
INFO LINK
INFO LINK
17
(4) H1100
(3) H1400 38
Linked List empat buah simpul dapat dinyatakan demikian ini, tanpa memperlihatkan alamat simpul secara fisik INFO LINK
12 (2) INFO LINK
10
25 (1)
INFO LINK
INFO LINK
(4)
17 (3)
39
25 (1)
12 (2)
17 (3)
LINK
INFO
LINK
INFO
LINK
INFO
LINK
INFO
Linked List empat buah simpul ini dapat disederhanakan gambarnya menjadi :
10 (4)
40
3. 01
Linked List adalah List yang di link satu dengan yang lainnya. Sedangkan list itu sendiri adalah merupakan gabungan beberapa elemen yang dijadikan satu structure atau record yang dibentuk dengan perintah struct Dalam buku ini akan dibicarakan 4 macam linked list sebagai berikut :
41
3. 01
I.
LINEAR SINGLY LINKED LIST
II. LINEAR DOUBLY LINKED LIST
III. CIRCULAR SINGLY LINKED LIST IV. CIRCULAR DOUBLY LINKED LIST
42
3. 01
I.
LINEAR SINGLY LINKED LIST LAST
FIRST
25
12
17
10
II. LINEAR DOUBLY LINKED LIST FIRST
LAST
25
12
17
10
43
3. 01
III. CIRCULAR SINGLY LINKED LIST LAST
FIRST
25
12
17
10
IV. CIRCULAR DOUBLY LINKED LIST LAST
FIRST
25
12
17
10
44
3. 02
LINKED LIST LURUS DENGAN POINTER TUNGGAL
45
LINEAR SINGLY LINKED LIST
3. 02
1.1. ILUSTRASI FIRST
LAST
25
(1)
12
(2)
17
10
(3)
(4)
atau LAST
FIRST
10
(4)
17
(3)
12
(2)
25
(1) 46
3. 02 FIRST
LAST
25
12
17
10
Urutan insert
(1)
(2)
(3)
(4)
Urutan delete
(1)
(2)
(3)
(4)
atau LAST
FIRST
10
17
12
25
Urutan insert
(4)
(3)
(2)
(1)
Urutan delete
(1)
(2)
(3)
(4) 47
3. 02
INSERT : Masuk, Simpan, Tulis DELETE : Keluar, Ambil, Baca atau Hapus
48
FIRST
LAST
Ilustrasi-1 25
12
17
10
Urutan insert
(1)
(2)
(3)
(4)
Urutan delete
(1)
(2)
(3)
(4)
LAST
FIRST
Ilustrasi-2 10
17
12
25
Urutan insert
(4)
(3)
(2)
(1)
Urutan delete
(1)
(2)
(3)
(4)
Pertanyaan :
Mana yang mengikuti prinsip STACK, dan mana yang mengikuti prinsip QUEUE, Linked List ilustrasi-1 atau Linked List ilustrasi-2 49
3. 02
1.1. ILUSTRASI LAST
FIRST
25 (1)
12 (2)
17
10 (4)
(3)
Keterangan :
Dari ilustrasi diatas, dapat diterangkan sebagai berikut: Ada 4 simpul, simpul no (1) sampai dengan no (4) Setiap simpul (record) terdiri dari dua elemen (field) yaitu : Field INFO misal bertipe integer. Field LINK bertipe pointer Yang Untuk simpul no (1), Field INFO berisi nilai 25 Field LINK berisi alamat record no (2)
diilustrasikan dengan panah yang menunjuk record no (2) 50
3. 02 LAST
FIRST
25
(1)
12
(2)
17
(3)
10
(4)
Simpul pertama no (1) ditunjuk oleh pointer FIRST dan simpul terakhir no (4) ditunjuk oleh pointer LAST Dari nama pointer FIRST dan LAST dapat diperkirakan bahwa record no (1) yang pertama kali dibuat dan record no (4) yang terakhir dibuat. Walaupun secra teknis dapat saja bukan demikian. 51
1.2 PROSES
2a. 2b. 2c. 2d. 2e. 2f. 2g.
Pembuatan Record Awal (inisialisasi) Insert Kanan (Insert Akhir) Insert Kiri (Insert Awal) Insert Tengah Delete Kanan Delete Kiri Delete Tengah
52
Ilustrasi sebuah Simpul (Vertex, atau Node, atau Record)
3.03
Simpul dengan 2 elemen atau field Nama field: LINK Tipe: pointer Isi: akan diisi dengan alamat record berikutnya Nama field: INFO Tipe: integer Isi: akan diisi data
Tipe data tentunya disesuaikan dengan keperluan. Disini diambil saja contoh yang sederhana dimana data yang akan disimpan adalah bernilai integer. 53
Struktur sebuah Simpul
3.03
Untuk „memberitahukan komputer „ bahwa kita memerlukan suatu Simpul atau record dengan tipe strukur demikian ini, perlu ditulis intruksi-instruksi sebagai berikut :
typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST; 54
3.03
typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST; Masih banyak cara penulisan lain untuk maksud yang sama. Disini diambil suatu cara yang dianggap paling sederhana.
Disiapkan 3 buah variabel pointer, yaitu : P, FIRST dan LAST yang kesemuanya berkaitan dengan simpul atau record atau node yang bertipe Simpul
55
typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST;
3.03
Disini :
Simpul Adalah nama tipe sebagaimana nama tipe yang telah
disediakan oleh Bahasa C seperti : int, long int, float, dan sebagainya. Bila int adalah nama tipe suatu variable, maka Simpul disini adalah nama tipe dari suatu structure atau record, dimana structure tersebut terdiri dari dua field, yaitu : INFO yang bertipe integer (int), dan LINK yang bertipe pointer (pakai *) untuk structure tersebut. 56
1.2.1. Pembuatan Simpul ( Baru )
3. 04
Perhatikan kembali instruksi untuk menyiapkan tipe sebuah simpul sebagai berikut : typedef struct Node { int INFO; struct Node *LINK;
}; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST;
57
1.2.1. Pembuatan Simpul ( Baru )
3. 04
Instruksi untuk membuat sebuah record baru : P = (Simpul *) malloc(sizeof(Simpul));
Terbentuk sebuah simpul yang alamatnya disimpan dalam pointer P atau disebut simpul yang ditunjuk oleh pointer P, yang dapat diilustrasikan sebagai berikut
P
58
3. 04
P = (Simpul *) malloc(sizeof(Simpul)); malloc : Maksudnya : memory allocation yaitu mengalokasikan memory sebesar atau seukuran (sizeof) yang diperlukan untuk Simpul
59
3. 04
P = (Simpul *) malloc(sizeof(Simpul)); INFO
LINK
H21C8
21C8
P
Alamat simpul dicatat dalam variabel P (P bertipe Pointer untuk menunjuk Simpul) 60
3. 04
INFO LINK
21C8
H21C8
P Ilustrasi fisik dalam memory diatas, dapat digambarkan dengan ilustrasi diagram sebagai berikut :
P
61
Contoh (sederhana) program selengkapnya untuk membuat sebuah record atau simpul yang alamat simpul tersebut dicatat dalam pointer P.
#include <stdio.h> #include <stdlib.h> #include
typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST; main() { int X; scanf(“%i”, &X); p = (Simpul *)alloc(sizeof(Simpul)); P->INFO = X; P->LINK = NULL; }
3. 04
62
3. 04
main() { int X; scanf(“%i”, &X); p = (Simpul *)alloc(sizeof(Simpul)); P->INFO = X; P->LINK = NULL; } Field LINK berisi NULL artinya pointer LINK tidak menunjuk kesuatu alamat tertentu
Terbentuk sebuah simpul yang alamatnya disimpan dalam pointer P atau disebut simpul yang ditunjuk oleh pointer P
Nilai X (misal 25 hasil input sebelumnya) disimpan dalam elemen INFO
P 25
63
3. 04
P->INFO = X; P->INFO
maksudnya :
Field INFO suatu simpul, yang simpulnya sedang ditunjuk oleh pointer P
dalam bahasa C, ditulis dengan dua karakter yaitu tanda - (minus) dan tanda > (tanda lebih besar)
P 25
64
3. 04
P->LINK = NULL;
P->LINK
field LINK suatu simpul, yang simpulnya sedang ditunjuk oleh pointer P
P 25
0 0 0 0 0 0 0 0
\0
karakter NULL nilai ASCIInya = 0 (nol) 65
3. 04
P 25
\0
Nilai pointer yang berisi NULL sering diilustrasikan sebagai panah „ground‟ sebagai berikut :
P 25
66
3.05
Perhatikan kembali LINEAR SINGLY LINKED LIST yang akan dibuat sebagai yang diilustrasikan berikut ini :
FIRST
LAST
25
(1)
12
(2)
17
(3)
10
(4)
67
3.05
1.2.2. Pembuatan Simpul Awal. Simpul awal, maksudnya adalah simpul yang pertama kali dibuat. Setelah itu simpul baru dapat ditambahkan baik disebelah kanan, maupun disebelah kiri simpul simpul yang sudah ada. LAST
FIRST
25
(1)
12
(2)
17
(3)
10
(4)
Simpul ini yang kita ambil sebagai contoh untuk simpul awal yang ditunjuk oleh pointer FIRST 68
Perhatikan kembali struktur sebuah simpul, dan variabel-variabel yang diperlukan typedef struct Node { int INFO; struct Node *LINK; }; typedef struct Node Simpul; Simpul *P, *FIRST, *LAST; int X;
3.05
Menyatakan struktur Simpul dan menyiapkan variabel
Dalam memory
P
FIRST
LAST
X
Perhatikan : Ada 3 buah pointer : P , FIRST, dan LAST 69
1.2.2. Pembuatan Simpul Awal.
3.05
Fungsi untuk membuat simpul awal
1) 2) 3) 4) 5)
void Awal (void) { int X; scanf(“%i”, &X); P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LINK = NULL; } Ada 5 intruksi pokok 70
1) 2) 3) 4) 5)
P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LINK = NULL;
3.05
Ada 5 instruksi pokok yang perlu kita perhatikan :
1) P = (Simpul *) malloc(sizeof(Simpul)); Terbentuk sebuah simpul yang ditunjuk oleh pointer P yang dapat diilustrasikan dengan gambar sebagai berikut :
P
71
3.05
1000
P
FIRST
LAST
X
1000
P
72
Sebuah simpul yang ditunjuk oleh pointer P ( alamatnya dicatat dalam pointer P )
3.05
P
P P P
P
P
Banyak cara menggambarkan ilustrasi pointer P menunjuk sebuah simpul
P
73
Sebuah simpul yang ditunjuk oleh pointer P ( alamatnya dicatat dalam pointer P )
3.05
P
Field ini namanya : P->LINK
Field ini namanya : P->INFO
74
1) 2) 3) 4) 5)
P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LINK = NULL;
3.05
2) P->INFO = X;
P 25
75
3.05
25 1000
P
FIRST
LAST
X
1000
P 25 76
P
3.05
25 Field ini namanya : P->LINK
Field ini namanya : P->INFO
Dengan perintah : printf(“%i”, P->INFO); Akan tercetak : 25
77
LAST
FIRST
25 (1)
12 (2)
17 (3)
10 (4)
Simpul pertama selalu ditunjuk Oleh pointer FIRST
78
1) 2) 3) 4) 5)
P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P P->LINK = NULL;
3.05 FIRST
25
3) FIRST = P; P
FIRST
P
25
25
FIRST
79
3.05
25 1000
P
FIRST
1000
1000
LAST
X
FIRST P
25 80
FIRST
3.05
P
25 Field ini namanya : P->LINK atau
FIRST->LINK
Field ini namanya : P->INFO
atau FIRST->INFO 81
LAST
FIRST
25 (1)
12 (2)
17 (3)
10 (4)
Simpul terakhir selalu ditunjuk Oleh pointer LAST
82
1) 2) 3) 4) 5)
P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST FIRST = P; LAST = P; P P->LINK = NULL;
3.05 LAST
25
4) LAST = P; FIRST
LAST FIRST
P
P 25
25
LAST 83
3.05
25 1000
P
FIRST
1000
1000
LAST
X
1000
LAST FIRST P
25 84
LAST
3.05
FIRST
P
25 Field ini namanya : P->LINK atau
Field ini namanya : P->INFO
atau FIRST->INFO atau LAST->INFO
FIRST->LINK atau LAST->LINK
85
1) 2) 3) 4) 5)
P=(Simpul*)malloc(sizeof(Simpul)); P->INFO = X; FIRST = P; LAST = P; P->LINK = NULL;
3.05
5) P->LINK = NULL; LAST FIRST
P 25
86
3.05
25 1000
P
FIRST
1000
1000
LAST
X
1000
LAST FIRST
Sudah terbentuk sebuah Simpul awal
P
25 87
3.05
LATIHAN DI KELAS
88
LAST
3.05
FIRST
P 25
Pertanyaan :
Ada berapa buah simpul yang terlihat
89
LAST
3.05
FIRST
P 25
Jawab : Ada 1 buah simpul
90
LAST
3.05
FIRST
P 25
Pertanyaan :
Ada berapa buah pointer yang terlihat - Apa nama masing-masing pointer - Apa isi masing-masing pointer
91
LAST
3.05
FIRST
P 3
2
1
Jawab : Ada 4 buah pointer
25 4
No Pointer
Nama Pointer
Isi pointer
1
P
&(1)
2
FIRST
&(1)
3
LAST
&(1)
4
P->LINK atau FIRST->LINK atau LAST->LINK
NULL 92
LAST
3.05
FIRST
P 3
2
TRUE atau FALSE Kondisi berikut ini
1
25 4
if( P == FIRST ) if( FIRST == LAST )
if( FIRST->LINK == LAST->LINK ) if( FIRST->INFO = 25 ) 93
