pertemuan 10 linked list. 10 struktur data - fmipa usd - 2003 6 pert. 10 struktur data - fmipa usd -...
Post on 30-Apr-2019
314 Views
Preview:
TRANSCRIPT
Pert. 10 Struktur Data - FMIPA USD - 2003 1
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 1
Pertemuan 10
Linked List
Disusun oleh : PH. Prima Rosa, S.Si., M.Sc.
Sri Hartati Wijono, S.Si.
© 2003/2004
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 2
Review : Sifat ImplementasiLinear List dengan Array
• Pencarian dapat dilakukan dengan mudah. • Melihat elemen dalam list dapat dilakukan
dengan mudah• Membaca elemen dalam list dapat dilakukan
dengan mudah• Proses menyisipkan dan menghapus elemen
tidak mudah. Mengapa ?�Elemen-elemen harus digeser
• Sulit untuk memperkirakan jumlah array yang harus dibuat.
Pert. 10 Struktur Data - FMIPA USD - 2003 2
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 3
Review : Sifat ImplementasiLinear List dengan Array
• Bagaimana mengatasi kelemahan implementasilinear list dengan array?– Satu elemen dengan elemen yang lain
dihubungkan dengan “suatu penghubung(link)”
• Lahir gagasan linked list
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 4
Beberapa Struktur Data
(a) Matriks
(b) Linked List
(c) Tree (d) Jaringan
Pert. 10 Struktur Data - FMIPA USD - 2003 3
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 5
Implementasi linked list (list terhubung)
• Linked list merupakan rantai elemen• Tiap elemen punya :
– data– link yang menunjuk ke elemen berikut
(a) Suatu linked list dengan pointer kepala: pKepala
(b) Suatu linked list kosong
pKepala
pKepala
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 6
Node :Suatu elemen dari Linked List
1 node dgn 1 field data
1 node dgn 3 field data
Suatu structure dlm 1 node
nomor nama
nama alamat telepon
id rangking
Pert. 10 Struktur Data - FMIPA USD - 2003 4
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 7
Kepala & Node menggunakanStruktur Data Structure
• Kita perlu mendefinisikan 2 structure:– satu untuk kepala (head) list– satu untuk node list
(a) Structure utk kepala
(b) Structure utk node
jumlah kepala
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 8
Kepala dan Node : list integer sederhana
struct intlist {struct node *kepala;int jumlah;
}IntList;
struct node {int data;struct node *link;
}Node;
2
kepala jumlah
15
data link
99
data link
Pert. 10 Struktur Data - FMIPA USD - 2003 5
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 9
Kepala dan Node: list nama
struct IntList {struct node *kepala;int jumlah;
}IntList;
struct node {char *name;struct node *link;
}Node;
2
Andi
Boni
kepala jumlah
data link
data link
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 10
Kepala dan Node: structure sebagai data
struct Intlist {struct node *kepala;int jumlah;
};
struct node {struct person *data;struct node *link
}Node;
struct person {char *nama;int umur;
}
2
jumlah
Andi 15
data link
data link
Boni 19
kepala
Pert. 10 Struktur Data - FMIPA USD - 2003 6
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 11
Operasi-Operasi Utamadalam Ordered Linked List
� Buat List� Tambah node
– Di awal, tengah atau akhir� Hapus node
– Di awal, tengah atau akhir� Cari node� Melacak list (Membaca node-node)
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 12
Operasi (1) Buat list
(a) Sebelum buat
(b) Setelah buat
list.kepala = nulllist.jumlah = 0
jumlah kepala
jumlah kepala
Pert. 10 Struktur Data - FMIPA USD - 2003 7
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 13
Operasi (2) Tambah Node : Jika List Kosong
(a) Sebelum
tambah
(b) Sesudah
tambah
pBaru -> link = list.kepalalist.kepala = pBaru
jumlah kepala
jumlah kepala
pBaru
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 14
Operasi Tambah Node: DiAwal List
(a) Sebelum
tambah
(b) Sesudah
tambah
pBaru -> link = list.kepalalist.kepala = pBaru
jumlah kepala
pBaru
jumlah kepala
pBaru
Pert. 10 Struktur Data - FMIPA USD - 2003 8
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 15
Operasi Tambah Node : DiTengah List
kepalajumlah
pBarupSblm
pBarupSblm
kepalajumlah
pBaru -> link = pSblm -> linkpSblm -> link = pBaru
(a) Sebelum
tambah
(b) Sesudah
tambah
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 16
• Bandingkan operasi penambahanelemen dalam implementasi linear list dengan array dan dengan linked list
• Apa kesimpulan Anda?
Operasi Tambah node: DiTengah List
Pert. 10 Struktur Data - FMIPA USD - 2003 9
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 17
Operasi Tambah Node : DiAkhir List
kepalajumlah
pBarupSblm
pBarupSblm
kepalajumlah
pBaru -> link = pSblm->linkpSblm -> link = pBaru
(a) Sebelum
tambah
(b) Sesudah
tambah
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 18
Operasi (3) Hapus Node: DiAwal List
kepalajumlah
pSkrgpSblm
pSkrgpSblm
kepalajumlah
list.kepala = pSkrg -> link
(a) Sebelum
tambah
(b) Sesudah
tambah
Pert. 10 Struktur Data - FMIPA USD - 2003 10
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 19
Operasi Hapus Node : KasusUmum
kepalajumlah
pSkrgpSblm
pSkrgpSblm
kepalajumlah
pSblm -> link = pSkrg->link
(a) Sebelum
tambah
(b) Sesudah
tambah
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 20
(a) Pencarian sukses (return true)
Lokasi di depan Lokasi di tengah Lokasi di akhir
Operasi (4) Pencarian node
pSkrgpSblm pSkrgpSblm pSkrgpSblm
Pert. 10 Struktur Data - FMIPA USD - 2003 11
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 21
(b) Pencarian gagal (return false)
< elemen pertama > elemen terakhir
Operasi (4) Pencarian node
pSkrgpSblm pSkrgpSblm pSkrgpSblm
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 22
Operasi Melacak List
Dilakukan proses pelacakan / pembacaan untuk setiap node
Lokasi di depan Lokasi di tengah Lokasi di akhir
pSkrgpSblm pSkrgpSblm pSkrgpSblm
Pert. 10 Struktur Data - FMIPA USD - 2003 12
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 23
Mengapa harus denganpointer?
• Pada beberapa bahasa pemrogramanyang tidak memiliki tipe data pointer, linked list diimplementasikandengan array
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 24
Struktur Data :Implementasi Linked Lists Dengan Variabel Dinamis
Pert. 10 Struktur Data - FMIPA USD - 2003 13
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 25
Alokasi Memori Dinamis� Alokasi memori dinamis
– Memakai dan membebaskan memory selama proseseksekusi
� malloc– Mengalokasikan sejumlah byte untuk digunakan
• sizeof digunakan untuk menentukan ukuranobyek
– Akan mengembalikan pointer ke sebuah lokasi dimemori.• Jika tidak ada memori yang tersedia akan
mengembalikan NULL– P = (Node *)malloc( sizeof( struct Node ) );
• P akan menunjuk ke variabel dinamis barubertipe node yang telah dibuat.
Pert. 10 Struktur Data - FMIPA USD - 2003 Hal. 26
Alokasi Memori Dinamis
� free– Membebaskan memori yang dibuat dengan malloc yang
sudah tidak digunakan– free (P);
top related