linked list 6.3 & 7.3 nested loop - e-learning didi juardi · pdf filelinked list adalah...

Click here to load reader

Post on 22-Mar-2019

225 views

Category:

Documents

0 download

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