linked list 6.3 & 7.3 nested loop - e-learning didi juardi · pdf filelinked list adalah...
Post on 22-Mar-2019
225 views
Embed Size (px)
TRANSCRIPT
1
6.3 & 7.3 NESTED LOOP
Linked List
2
Linked List ( List yang di-Link
satu dengan
lainnya )
3
apa itu List ?
4
Contoh sebuah LIST
int A[5];
0 1 2 3 4
Array satu dimensi Disebut juga : Vector Kadang-kadang disebut juga : List
5
int A[5];
0 1 2 3 4
biasa diilustrasikan sebagai berikut :
Kadang-kadang diilustrasikan sebagai berikut :
0
1
2
3
4
6
0 1 2 3 4
int A[5];
A[0]
List dengan 5 elemen
A[1] A[4]
secara umum : A[ I ]
7
0 1 2 3 4
int A[5]; List dengan 5 elemen, dengan alamat CONTIGUOUS
H21D8 H21DA
H21DC
H21DE H21E0
#include void main() { int A[5]; int I; for (I=0; I
8
Apa itu alamat ?
9
Alamat atau Address adalah nomor Byte
RAM 64 MB
0 1 2 3 4
64*1024*1024-1
10
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
11
0 1 2 3 4
int A[5]; List dengan 5 elemen
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).
12
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,
atau Vertex, atau Node, atau Titik, atau Record atau
Simpul
setiap elemen mempunyai tipe data tersendiri
13
Linked List
Contoh sebuah Simpul yang dinyatakan dengan:
INFO LINK
typedef struct Node {
int INFO;
struct Node *LINK;
};
typedef struct Node Simpul;
Tipe : integer untuk menyimpan data
tipe : pointer, pointer untuk menunjuk node atau Simpul
Simpul dengan 2 elemen, INFO dan LINK
14
INFO LINK
typedef struct Node {
int INFO;
struct Node *LINK;
};
typedef struct Node Simpul;
Tulisan dengan warna biru atau merah, adalah nama yang kita karang sendiri. Sedangkan tulisan dengan warna hitam adalah ketentauan dalam bahasa C
15
Contoh 4 buah simpul Linked List dalam memory
25
12
17
10
(1)
(2)
(3)
(4)
tanda panah mengilustrasikan link
16
Proses pembuatan Simpul dan pembuatan Link sampai terbentuk
sebuah Linked-List
17
Perhatikan memory berikut ini :
Belum ada Linked List
18
Akan dibuat sebuah Simpul Awal (simpul pertama)
19
Simpul pertama (1) sudah dibuat misal alamatnya = H1000
H1000
INFO LINK
(1)
Bagaimana membuatnya akan diterangkan kemudian
20
H1000
INFO LINK
Kemudian INFO akan diisi dengan nilai 25
(1)
21
25
H1000
INFO LINK
INFO simpul pertama (1) sudah diisi dengan nilai 25
(1)
Bagaimana cara mengisinya akan diterangkan kemudian
22
25
Misal akan dibuat sebuah simpul baru (simpul kedua)
H1000
INFO LINK
(1)
23
25
H1000
INFO LINK
Sudah dibuat simpul kedua (2) Misal alamatnya = H0800
H0800
INFO LINK
(1)
(2)
Alamat simpul baru, tidak mesti lebih besar dari alamat simpul pertama
24
25
H1000
INFO LINK
H0800
INFO LINK
INFO simpul kedua (2) akan diisi dengan 12
(1)
(2)
25
25
H1000
INFO LINK
INFO simpul kedua (2) sudah diisi dengan nilai 12
12
H0800
INFO LINK
(1)
(2)
26
25
H1000
INFO LINK
Akan di-link simpul pertama (1) dengan simpul kedua (2)
12
H0800
INFO LINK
(1)
(2)
27
25 0800
H1000
INFO LINK
Simpul pertama (1) sudah di-link dengan simpul kedua (2)
12
H0800
INFO LINK
LINK simpul pertama (1) diisi dengan alamat simpul kedua (2)
(1)
(2)
Bagaimana mengisi LINK simpul pertama dengan alamat simpul kedua akan diterangkan kemudian
28
25 0800
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
Instruksi untuk meng-link yaitu mengisi alamat simpul (2) kedalam LINK simpul (1) termasuk intruksi atau tugas yang sulit !
29
25 0800
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
Kemudian : Akan dibuat simpul (3), dan INFO simpul (3) diisi dengan 17
30
25 0800
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
Sudah dibuat simpul ketiga (3) Misal alamatnya = H1400
17
H1400
INFO LINK
(3)
31
25 0800
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
Akan di-link simpul kedua (2) dengan simpul ketiga (3)
Kemudian :
17
H1400
INFO LINK
(3)
32
25 0800
H1000
INFO LINK
12 1400
H0800
INFO LINK
(1)
(2)
Simpul kedua (2) sudah di-link dengan simpul ketiga (3)
17
H1400
INFO LINK
(3)
33
25 0800
H1000
INFO LINK
12 1400
H0800
INFO LINK
(1)
(2)
17 1100
H1400
INFO LINK
(3)
Dan seterusnya dibuat simpul (4), INFO simpul (4) diisi 10 dan simpul (3) di-link dengan simpul (4)
10
H1100
INFO LINK
(4)
34
25 0800
H1000
INFO LINK
12 1400
H0800
INFO LINK
(1)
(2)
17 1100
H1400
INFO LINK
(3)
10
H1100
INFO LINK
(4)
Sekarang sudah tercipta 4 buah simpul, dan sudah ter-link satu dengan lainnya, sehingga membentuk sebuah Linked List
35
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 :
36
25 0800
H1000
INFO LINK
12 1400
H0800
INFO LINK
(1)
(2)
17 1100
H1400
INFO LINK
(3)
10
H1100
INFO LINK
(4)
Link dalam bentuk angka alamat tidak diperlukan lagi
Sehingga:
37
25
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
17
H1400
INFO LINK
(3)
10
H1100
INFO LINK
(4)
38
25
H1000
INFO LINK
12
H0800
INFO LINK
(1)
(2)
17
H1400
INFO LINK
(3)
10
H1100
INFO LINK
(4)
Alamat sebuah simpul, sebenarnya, tidak perlu diketahui atau dinyatakan
39
25
INFO LINK
12
INFO LINK
(1)
(2)
17
INFO LINK
(3)
10
INFO LINK
(4)
Linked List empat buah simpul dapat dinyatakan demikian ini, tanpa memperlihatkan alamat simpul secara fisik
40
25
INFO
LINK
12
(1) (2)
17
(3)
10
(4)
Linked List empat buah simpul ini dapat disederhanakan gambarnya menjadi :
INFO
LINK
INFO
LINK
INFO
LINK
41
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 :
42
3. 01
I. LINEAR SINGLY LINKED LIST
II. LINEAR DOUBLY LINKED LIST
III. CIRCULAR SINGLY LINKED LIST
IV. CIRCULAR DOUBLY LINKED LIST
43
3. 01
I. LINEAR SINGLY LINKED LIST
25
FIRST
12 17 10
LAST
II. LINEAR DOUBLY LINKED LIST
25
FIRST
12 17 10
LAST
44
3. 01 III. CIRCULAR SINGLY LINKED LIST
25
FIRST
12 17 10
LAST
IV. CIRCULAR DOUBLY LINKED LIST
25
FIRST
12 17 10
LAST
45
3. 02
LIN