Linked List 6.3 & 7.3 NESTED LOOP - E-Learning Didi Juardi · Linked List adalah List yang di link...
-
Upload
phamnguyet -
Category
Documents
-
view
238 -
download
0
Transcript of Linked List 6.3 & 7.3 NESTED LOOP - E-Learning Didi Juardi · Linked List adalah List yang di link...
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
7
0 1 2 3 4
int A[5]; List dengan 5 elemen, dengan alamat CONTIGUOUS
H21D8 H21DA
H21DC
H21DE H21E0
#include<stdio.h> void main() { int A[5]; int I; for (I=0; I<=4; I++ ) printf( “\n%X”, &A[I] ); }
akan tercetak :
21D8 21DA 21DC 21DE 21E0
Tiap elemen 2 BYTE Algo-1, jilid 2 hal. 10.03
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
19
Simpul pertama (1) sudah dibuat misal alamatnya = H1000
H1000
INFO LINK
(1)
Bagaimana membuatnya akan diterangkan kemudian
21
25
H1000
INFO LINK
INFO simpul pertama (1) sudah diisi dengan nilai 25
(1)
Bagaimana cara mengisinya akan diterangkan kemudian
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
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:
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
46
3. 02
1.1. ILUSTRASI
LINEAR SINGLY LINKED LIST
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
10
FIRST
17 12 25
LAST
(4) (3) (2) (1)
atau
47
3. 02
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
10
FIRST
17 12 25
LAST
(4) (3) (2) (1)
atau
(1) (2) (3) (4)
(1) (2) (3) (4)
Urutan insert
Urutan delete
Urutan insert
Urutan delete
49
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
10
FIRST
17 12 25
LAST
(4) (3) (2) (1)
(1) (2) (3) (4)
(1) (2) (3) (4)
Urutan insert
Urutan delete
Urutan insert
Urutan delete
Ilustrasi-1
Ilustrasi-2
Pertanyaan : Mana yang mengikuti prinsip STACK, dan mana yang mengikuti prinsip QUEUE, Linked List ilustrasi-1 atau Linked List ilustrasi-2
50
3. 02 1.1. ILUSTRASI
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
Untuk simpul no (1), Field INFO berisi nilai 25 Field LINK berisi alamat record no (2)
Yang diilustrasikan dengan panah yang menunjuk record no (2)
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
51
3. 02
25
FIRST
12 17 10
LAST
(1) (2)
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.
Simpul pertama no (1) ditunjuk oleh pointer FIRST dan simpul terakhir no (4) ditunjuk oleh pointer LAST
(3) (4)
52
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
53
3.03 Ilustrasi sebuah Simpul (Vertex, atau Node, atau Record)
Nama field Tipe Isi
: LINK : pointer : akan diisi dengan alamat record berikutnya
Nama field Tipe Isi
: INFO : integer : akan diisi data
Tipe data tentunya disesuaikan dengan keperluan. Disini diambil saja contoh yang sederhana dimana data yang akan disimpan adalah bernilai integer.
Simpul dengan 2 elemen atau field
54
3.03 Struktur sebuah Simpul
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;
55
3.03
typedef struct Node {
int INFO;
struct Node *LINK;
};
typedef struct Node Simpul;
Simpul *P, *FIRST, *LAST;
Disiapkan 3 buah variabel pointer, yaitu : P, FIRST dan LAST yang kesemuanya berkaitan dengan simpul atau record atau node yang bertipe Simpul
Masih banyak cara penulisan lain untuk maksud yang sama. Disini diambil suatu cara yang dianggap paling sederhana.
56
3.03 typedef struct Node {
int INFO;
struct Node *LINK;
};
typedef struct Node Simpul;
Simpul *P, *FIRST, *LAST;
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.
57
3. 04
typedef struct Node {
int INFO;
struct Node *LINK;
};
typedef struct Node Simpul;
Simpul *P, *FIRST, *LAST;
1.2.1. Pembuatan Simpul ( Baru )
Perhatikan kembali instruksi untuk menyiapkan tipe sebuah simpul sebagai berikut :
58
3. 04 1.2.1. Pembuatan Simpul ( Baru )
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
59
3. 04
P = (Simpul *) malloc(sizeof(Simpul));
malloc :
Maksudnya : memory allocation yaitu mengalokasikan memory sebesar atau seukuran (sizeof) yang diperlukan untuk Simpul
60
3. 04
P = (Simpul *) malloc(sizeof(Simpul));
21C8
P
INFO LINK
H21C8
Alamat simpul dicatat dalam variabel P (P bertipe Pointer untuk menunjuk Simpul)
61
3. 04
21C8
P
INFO LINK
H21C8
P
Ilustrasi fisik dalam memory diatas, dapat digambarkan dengan ilustrasi diagram sebagai berikut :
62
3. 04 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 <ctype.h>
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;
}
63
3. 04
main()
{ int X;
scanf(“%i”, &X);
p = (Simpul *)alloc(sizeof(Simpul));
P->INFO = X;
P->LINK = NULL;
}
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
Field LINK berisi NULL artinya pointer LINK tidak menunjuk kesuatu alamat tertentu
25
P
64
3. 04
P->INFO = X;
25
P
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)
65
3. 04
P->LINK = NULL;
25 \0
P
P->LINK field LINK suatu simpul, yang simpulnya
sedang ditunjuk oleh pointer P
0 0 0 0 0 0 0 0 karakter NULL nilai ASCIInya = 0 (nol)
66
3. 04
25 \0
P
Nilai pointer yang berisi NULL sering diilustrasikan sebagai panah „ground‟ sebagai berikut :
25
P
67
3.05 Perhatikan kembali LINEAR SINGLY LINKED LIST yang akan dibuat sebagai yang diilustrasikan berikut ini :
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
68
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.
25
FIRST
12 17 10
LAST
(1) (2) (3) (4)
Simpul ini yang kita ambil sebagai contoh untuk
simpul awal yang ditunjuk oleh pointer FIRST
69
3.05 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;
Dalam memory
P FIRST LAST X
Menyatakan struktur Simpul dan menyiapkan variabel
Perhatikan : Ada 3 buah pointer : P , FIRST, dan LAST
70
3.05
void Awal (void)
{ int X;
scanf(“%i”, &X);
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
}
Fungsi untuk membuat simpul awal
1)
2)
3)
4)
5)
1.2.2. Pembuatan Simpul Awal.
Ada 5 intruksi pokok
71
3.05
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
1)
2)
3)
4)
5)
P = (Simpul *) malloc(sizeof(Simpul));
Ada 5 instruksi pokok yang perlu kita perhatikan :
1)
Terbentuk sebuah simpul yang ditunjuk oleh pointer P yang dapat diilustrasikan dengan gambar sebagai berikut :
P
73
3.05
P
Sebuah simpul yang ditunjuk oleh pointer P ( alamatnya dicatat dalam pointer P )
P
P
P
P
P
P
Banyak cara menggambarkan
ilustrasi pointer P menunjuk sebuah simpul
74
3.05
P
Sebuah simpul yang ditunjuk oleh pointer P ( alamatnya dicatat dalam pointer P )
Field ini namanya :
Field ini namanya : P->LINK
P->INFO
75
3.05
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
1)
2)
3)
4)
5)
P->INFO = X; 2)
25
P
77
3.05
25
P
Field ini namanya :
Field ini namanya : P->LINK
P->INFO
Dengan perintah : printf(“%i”, P->INFO); Akan tercetak : 25
79
3.05
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
1)
2)
3)
4)
5)
FIRST = P; 3)
25
P
FIRST
25
P
FIRST
25
P
FIRST
81
3.05
25
FIRST
Field ini namanya :
Field ini namanya : P->LINK atau FIRST->LINK
P->INFO atau FIRST->INFO
P
83
3.05
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
1)
2)
3)
4)
5)
LAST = P; 4)
25
P
FIRST
LAST
25
P
FIRST
25
P
LAST
LAST
FIRST
85
3.05
25
FIRST
Field ini namanya :
Field ini namanya : P->LINK atau FIRST->LINK atau LAST->LINK
P->INFO atau FIRST->INFO atau LAST->INFO
P
LAST
86
3.05
P=(Simpul*)malloc(sizeof(Simpul));
P->INFO = X;
FIRST = P;
LAST = P;
P->LINK = NULL;
1)
2)
3)
4)
5)
P->LINK = NULL; 5)
25
P
FIRST
LAST
91
3.05
25
P
FIRST
LAST
Pertanyaan : Ada berapa buah pointer yang terlihat
- Apa nama masing-masing pointer
- Apa isi masing-masing pointer
92
3.05
25
P
FIRST
LAST
1 2 3
4
Jawab : Ada 4 buah pointer
1
2
3
4
No Nama Isi Pointer Pointer pointer
P &(1)
FIRST &(1)
LAST &(1)
P->LINK atau FIRST->LINK atau LAST->LINK
NULL