algoritma dan struktur data -...

31
Algoritma dan Struktur Data Linked List

Upload: vuongdat

Post on 22-Mar-2019

333 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Algoritma dan Struktur Data

Linked List

Page 2: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Syntax:

struct nama_struct {

tipe_data_1 nama_var_1;

tipe_data_2 nama_var_2;

tipe_data_3 nama_var_3;

……

};

2

Page 3: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

KONSEP ALOKASI MEMORY DINAMIS

1. Deklarasikan pointer yang menunjuk variabel yang

akan dibuat

2. Jika pada saat program berjalan variabel tersebut

dibutuhkan

Pesan slot memori untuk menyimpan variabel

(malloc)

Simpan alamat slot memori pada pointer no 1

Gunakan variabel sesuai kebutuhan dengan cara

akses tak langsung melalui pointer

Hapus variabel / lepas slot memori setelah

variabel selesai digunakan (free)

Page 4: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Contoh malloc()- float #include <stdio.h>

#include <conio.h>

#include <stdlib.h>

void main()

{

//deklarasi pointer

float *pjari, *pluas;

//memesan slot memori untuk membuat variabel jari & luas. Simpan alamatnya pada pointer

pjari = (float *)malloc(sizeof(float));

pluas = (float *)malloc(sizeof(float));

if (pjari != NULL && pluas != NULL){//jika berhasil memesan memori

//gunakan variabel jari dan luas melalui pointer

*pjari = 7;

*pluas = 3.14 * *pjari * *pjari;

printf("lingkaran dengan jari-jari : %f\n", *pjari);

printf("luasnya : %f\n", *pluas);

//menghapus atau melepaskan slot memori yang ditunjuk oleh pjari dan pluas

free(pjari);

free(pluas);

}

getch(); }

Page 5: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Linked List == kereta????

Page 5 5

Page 6: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Apakah Linked List itu ?

• Elemen (disebut dengan CELL, atau SEL dalam bahasa Indonesia) yang mungkin terletak terpisah-pisah di memory, disambungkan dengan pointer.

• Tiap sel berisi dua informasi : nilai dan pointer ke sel berikutnya

CELL

nilai Pointer to next CELL

nilai Pointer to next CELL

nilai Pointer to next CELL

Page 7: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

1. Mudah untuk menambahkan dan menghapus elemen(pada

array tidak mungkin menambahkan elemen, karena

banyaknya elemen sudah ditentukan dari awal)

2. Panjang list bisa diubah dengan bebas (panjang array fixed)

3. Mudah untuk menyambungkan beberapa list, maupun

memutuskannya (array tidak bisa)

4. Memungkinkan user mendesain struktur data yang

kompleks

Mengapa memakai Linked List ?

Page 8: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Struktur linked List

Node (elemen) linked list saling berkait

melalui pointer. Bagian next sebuah node

menunjuk alamat node selanjutnya

pHead: pointer yang menunjuk node

pertama

A pHead

B C

Page 9: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Struktur linked List

Node terakhir menunjuk NULL

Setiap node terdiri atas

Isi data

Next, yaitu pointer ke node selanjutnya

pada list

A pHead

B C

Page 10: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Struktur Sebuah Node

struct node {

//bagian data

tipedata data 1;

tipedata data 2;

tipedata data n;

//pointer ke node selanjutnya

struct node *next;

};

typedef struct node node;

Page 11: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Array vs linked list

Cara mengakses elemen

Elemen array diakses lewat indeks

Untuk mengakses elemen linked list, harus dilakukan

penelusuran elemen list

Banyaknya anggota

Banyaknya elemen array ditentukan di awal &

jumlahnya tetap

Elemen linked list dibuat di memori ketika

dibutuhkan (ingat Alokasi memory dinamis).

Jumlahnya dinamis, dapat bertambah dan

berkurang sesuai keperluan

Page 12: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Array vs Linked List

Array Linked List

Penambahan dan

penghapusan

elemen

Tidak mungkin

Mungkin

Panjang list Fixed

Bisa diubah

Akses ke elemen cepat (harus mengikuti pointer satu

demi satu)

lambat

Page 13: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Array vs Linked List

13

1 2 3

1 header

2

3

a[0]

a[1]

a[2]

int a[3];

int n;

Array Linked List

address 13 18

address 18 24

address 24

Address tidak berurutan

Akses ke tiap sel dimulai dari header

Address tiap sel berurutan

value Pointer ke sel berikutnya

(next)

next next value value

(NULL)

Page 14: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Cara menampilkan isi sel tertentu

• Pada array (misalnya nama array: a), isi sel tertentu dapat ditampilkan dengan cara a[nomer urut sel keberapa]. Misalnya a[5] akan menampilkan isi sel ke-6. Hal ini karena satu sel dengan sel yang lain terletak pada posisi yang berurutan di memory.

• Pada linked list, kita tidak tahu secara langsung, sel itu terletak dimana dalam memory.

Akses harus dilakukan satu persatu, urut mulai dari sel

terdepan

Page 15: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Cara menampilkan isi sel tertentu

header

pointer

Sel ke-1→ isi: value=4

address sel berikutnya=38

37 38 4 40 2 40 52 13 37 38 40 52

NULL

Sel ke-1

Tampilkan isi (value) sel ke-3 !

address

Page 16: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

NULL POINTER

• Nilai yang dimiliki sebuah pointer adalah address

pada memory dimana data tersimpan

• Pointer yang tidak menunjuk ke address manapun

disebut dengan NULL pointer. Maksudnya, satu

kondisi khusus dimana pointer itu belum diset

dengan sebuah address tertentu

• Pada stdio.h biasanya didefinisikan dengan nilai 0

• Saat fungsi fopen,malloc dieksekusi, jika terdapat

error, maka nilai yang dikembalikan adalah NULL

Pada kuliah ini, NULL disimbolkan

dengan kotak yang diberi garis diagonal

Page 17: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Deklarasi head

Sebelum membuat linked list, perlu dideklarasikan

dan diinisialisasikan head, yaitu pointer yang

menunjuk node pertama dari linked list

node *pHead = NULL;

Page 18: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Potongan kode – linked list statis

struct motor {

float volts;

float amps;

struct motor *next;

};

typedef struct motor motor;

void main()

{

motor *pm1, *pm2, *pm3;

}

1. Isi volts dan amps pada pm1, pm2 dan pm3 dengan data sembarang

2. Isi pm1.next dengan alamat pm2, pm2.next dengan alamat pm3, dan pm3.next dengan NULL

3. Tampilkan isi pm2 hanya dengan menggunakan pointer pm1

4. Tampilkan isi pm3 hanya dengan menggunakan pointer pm2

5. Tampilkan isi pm3 hanya dengan menggunakan pointer pm1

Page 19: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Operasi dasar linked list

1. Menambah sebuah node.

2. Menghapus sebuah node.

3. Mencari sebuah node.

4. List tranversal

Page 20: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menambahkan node ke list kosong

Before: Code:

pNew -> next = pHead; // set link to NULL

pHead = pNew;// point list to first node

After:

39 pNew

pHead

pPre

39 pNew

pHead

pPre

Page 21: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menambahkan node ke awal list

Before: Code (same): pNew -> next = pHead; // set link to NULL

pHead = pNew;// point list to first node

After:

39 pNew

pHead

pPre

75 124

39 pNew

pHead

pPre

75 124

Page 22: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menambahkan node di tengah list

Before: Code pNew -> next = pPre -> next;

pPre -> next = pNew;

After:

64 pNew

pPre

55 124

64 pNew

pPre

55 124

Page 23: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menambahkan node akhir list

Before: Code pNew -> next = NULL;

pPre -> next = pNew;

After:

144 pNew

pPre

55 124

144 pNew

pPre

55 124

Page 24: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menambahkan node pada linked list

Terdapat empat tahap untuk menambah node linked list:

• Membuat node baru.

• Mendapatkan node yang terletak sebelum node baru disisipkan (pPre)

• Atur next node baru agar menunjuk node sesudah posisi penyisipan.

• Atur next pPre agar menunjuk node baru.

Page 25: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Kode untuk menambah data ke linked list

• Untuk menambah data pada linked list, harus diketahui head pointer (pHead), pointer yang menunjuk node sebelum tempat penyisipan (pPre) data yang akan disisipkan (item).

//insert a node into a linked list

struct node *pNew;

pNew = (struct node *) malloc(sizeof(struct node));

pNew -> data = item;

if (pPre == NULL){

//add before first logical node or to an empty list

pNew -> next = pHead;

pHead = pNew;

}

else {

//add in the middle or at the end

pNew -> next = pPre -> next;

pPre -> next = pNew;

}

Page 26: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menghapus node dari linked list

• Untuk menghapus sebuah node:

– Cari node yang akan dihapus (pCur) dan node

pendahulunya (pPre).

– Ubah pPre->next agar menunjuk pCur->next.

– Hapus pCur menggunakan fungsi free

Page 27: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menghapus node pertama dari linked list

Before: Code:

pHead = pCur -> next;

free(pCur);

After:

pHead

pPre

75 124

pCur

pHead

pPre

Recycled 124

pCur

Page 28: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Menghapus node dari linked list – kasus umum

Before: Code:

pPre -> next = pCur -> next;

free(pCur);

After:

75 124 96

pPre pCur

75 124 Recycled

pPre pCur

Page 29: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Kode untuk menghapus node dari linked list

• Untuk menghapus node dari linked list, harus diketahui head

pointer (pHead), node yang akan dihapus (pCur), serta

pendahulunya,

//delete a node from a linked list

if (pPre == NULL)

//deletion is on the first node of the list

pHead = pCur -> next;

else

//deleting a node other than the first node of the list

pPre -> next = pCur -> next;

free(pCur).

Page 30: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Mencari node yang mengandung data tertentu

dari linked list

• Operasi insert dan delete membutuhkan pencarian pada list untuk menentukan posisi penyisipan atau pointer yang menunjuk data yang akan dihapus

//search the nodes in a linked list

pPre = NULL;

pCur = pHead;

//search until the target value is found or the end of the list is reached

while (pCur != NULL && pCur -> data != target) {

pPre = pCur;

pCur = pCur -> next;

}

//determine if the target is found or ran off the end of the list

if (pCur != NULL)

found = 1;

else

found = 0;

Page 31: Algoritma dan Struktur Data - eriq.lecture.ub.ac.ideriq.lecture.ub.ac.id/files/2012/03/Linked_List.pdfMudah untuk menambahkan dan menghapus elemen(pada array tidak mungkin menambahkan

Traversing a Linked List

• mengunjungi semua node yang ada pada list dari head sampai

node terakhir

//traverse a linked list

Struct node *pWalker;

pWalker = pHead;

printf(“List contains:\n”);

while (pWalker != NULL){

printf(“%d ”, pWalker -> data);

pWalker = pWalker -> next;

}