4/9/2012
IF-UTAMA
1
Overview 2
LIST BERKAIT(LINKED LIST)
Pertemuan : 13-14 Dosen Pembina : Danang Junaedi
Tujuan Instruksional Pendahuluan Pembentukan List Berkait Menampilkan Data pada List Berkait Studi Kasus Tugas Individu
Program Studi Teknik Informatika – Universitas Widyatama IF-UTAMA
Tujuan Instruksional 3
Pendahuluan (1) 4
Mahasiswa akan dapat Menjelaskan pengertian dan manfaat list berkait Menjelaskan pengelolaan list berkait (Membentuk, Menampilkan data, Mencari dan Menghapus data) Mengimplementasikan pengelolaan list berkait (Membentuk, Menampilkan data, Mencari dan Menghapus data)
List atau disebut juga Pointer
Cara pendeklarasian : Algoritma :
: ^Data C/C++: *
Jenis List/Pointer :
IF-UTAMA
variabel yang berisi alamat memori sebagai nilainya. berisi alamat dari variabel yang mempunyai nilai tertentu. tidak secara langsung berisi suatu nilai tetapi berisi alamat memori dari nilai tersebut
List Tunggal (Single List) terdiri dari maksimum 1 komponen yaitu komponen yang mencatat alamat dari suatu nilai
IF-UTAMA
1
4/9/2012
Pendahuluan (2)
Pendahuluan (3)
5
6
Contoh List Tunggal (Single List) int I = 5;
I
I
5
0012FED4
5
IPointer
int *IPointer;
0012FED6
IPointer
IPointer 0012FED6
IPointer = &I;
IPointer
I
5
0012FED4
List Berkait (Linked List) terdiri dari 2 komponen utama yaitu komponen nilai/info dari list itu sendiri dan komponen yang mencatat alamat dari suatu nilai/list berikutnya. Gambar Elemen Dasar Sebuah Linked List Informasi
0012FED4
I
Pada umumnya suatu linked list memiliki sejumlah elemen, di mana salah satu elemen yang paling awal (elemen kepala atau head) bersifat agak khusus dan tidak digunakan untuk menyimpan data.
5
Alamat di memori
Pointer
Struktur ini terdiri atas rangkaian elemen yang saling berhubungan /berkaitan, dimana setiap elemen dihubungkan dengan elemen lainnya, oleh sebuah pointer. Jadi setiap elemen dalam linked list selalu berisi/mengandung pointer. Pointer adalah sebuah sel dalam suatu elemen yang berfungsi sebagai penunjuk letak elemen yang lain (nilainya merupakan alamat elemen yang lain).
IF-UTAMA
Pendahuluan (5)
Pendahuluan (4) 7
8
Jenis List/Pointer (Lanjutan):
Head
Single Linked List Contoh Info
Info Next
Next_List
Double Linked List Multiple Linked List Circular Linked List
NULL (kosong/List terakhir)
Gambar Contoh sebuah List yang Berisi Beberapa Elemen List
di bahas pada mata kuliah Struktur Data & Algoritma Lanjut
NULL berarti komponen yang mencatat alamat list berikutnya bernilai kosong
Berikut ini diberikan contoh penulisan suatu struktur data list : Algoritma
C/C++
Type simpul= ^mylist mylist = record Info :char Next : simpul End
typedef struct{ Info : char; Next : simpul; } mylist ; Mylist *simpul;
IF-UTAMA
2
4/9/2012
Pembentukan List Berkait (1)
Pembentukan List Berkait (2)
9
10
Pendeklarasian List
struct { ; *; }; Contoh : a. Struct List{ int Info; Info List Next; }; Atau b. Struct Simpul{ int No_Urut; char Nama[25]; float IPK; Simpul *Berikutnya; };
Nama Info
Nama Pointer
Berisi alamat dari list berikutnya
Berisi Nilai dari List
Pembentukan List Baru = new Contoh berdasarkan pendeklarasian di atas a. Baru = new List //perintah untuk membuat list baru Baru -> Info =25 atau cin>>Baru -> info //Masukan data ke Info 25 / Nilai yang di-input-kan
Berisi alamat dari list berikutnya
Next
b. Simpul Anyar = new Simpul //perintah untuk membuat Simpul baru
Simpul Anyar -> No_Urut = 001 atau cin>> Simpul Anyar -> No_Urut
Berisi Nilai dari List
Simpul Anyar -> Nama = “Saya” atau cin>> Simpul Anyar -> Nama Simpul Anyar -> IPK = 3.56 atau cin>> Simpul Anyar -> IPK No_Urut
Nama
IPK
Berikutnya
Berisi alamat dari list berikutnya
Berisi Nilai dari List
IF-UTAMA
001 Saya 3.56 Operator untuk menunjukan posisi komponen yang sedang aktif/digunakan
Algoritma : ^.
C/C++ : ->
IF-UTAMA
Pembentukan List Berkait (3)
Pembentukan List Berkait (4)
11
12
Penambahan List Baru ke dalam Elemen List
List Kosong (Awal/Head = NULL) Awal/Akhir Awal
List Isi (lanjutan)
Tambah di Akhir
25
25
1
3
25
Baru
25
45
Baru
3. Baru -> Next = NULL
35
3
2
45
List Isi Tambah di Awal Awal Akhir
1. Akhir -> Next = Baru
Awal/Head Akhir 25
25 Baru
35
2. Akhir = Baru
1
Akhir
Akhir
1. Awal = Baru Baru
Awal
Awal
Akhir 2
2
Baru 35
2. Akhir = Baru 1. Baru -> Next = Awal
3. Baru -> Next = NULL
2. Awal = Baru 1
35 IF-UTAMA
IF-UTAMA
3
4/9/2012
Pembentukan List Berkait (5)
Menampilkan Data pada List Berkait
13
14
List Isi (lanjutan) Tambah di Tengah
Awal/Head
1 Akhir
35
25
PSbl 35
45
Baru 15
2
Arah Penelusuran/Pergeseran
Pnow
Awal
Awal
Pnow
Akhir
25
45
35
25
15
45
Telusuri dari posisi awal sampai ditemukan posisi paling akhir (NULL), Tampilkan &
3
gunakan Pnow (Pointer saat ini) sebagai pointer bantu penelusuran
Baru
Pnow = Awal
15 1. Telusuri dari posisi awal sampai ditemukan posisi yang sesuai atau posisi paling akhir (NULL)
while (Pnow != NULL)
& gunakan Psbl (Pointer sebelum) dan Pnow (Pointer saat ini) sebagai pointer bantu
{
penelusuran
cout << Pnow -> Info
Psbl = NULL ; Pnow = Awal
Pnow = Pnow -> Next
while (Pnow != NULL && ) {Psbl = Pnow ;Pnow = Pnow -> Next}
}
2. Psbl = Baru 3. Baru -> Next = Pnow IF-UTAMA
IF-UTAMA
Studi Kasus I 15
Pencarian Data pada List Berkait 16
Awal
Buat Algoritma & Program (gunakan list berkait) untuk kasus di bawah ini (pilih salah satu) Data Nilai Mahasiswa Data Barang Data Penjualan Dimana data harus terurut secara Ascending berdasarkan aturan tertentu, kemudian tampilkan datanya
IF-UTAMA
Pnow 35
Arah Penelusuran/Pergeseran 15
25
45
Secara garis besar, proses untuk mencari data yang terdapat pada suatu list hampir sama dengan proses membaca isi list, tetapi perlu ditambah dengan test untuk menentukan apakah data yang dicari ada pada seranai. Ada 2 Kemungkinan Proses Pencarian a. Data Tidak Terurut Pnow = Awal while (Pnow != NULL && Cari_Data != Pnow -> Info) {Pnow = Pnow -> Next} if (Pnow != NULL) cout<<“Data ditemukan else cout<<“Data tidak ditemukan”
b. Data Terurut Pnow = Awal while (Pnow != NULL && Cari_Data > Pnow -> Info) { Pnow = Pnow -> Next} if (Pnow->info == Cari_Data) cout<<“Data ditemukan else cout<<“Data tidak ditemukan”
IF-UTAMA
4
4/9/2012
Menghapus Data pada List Berkait (1) 17
Menghapus Data pada List Berkait (2) 18
Dari hasil pencarian data di atas, kemungkinan proses penghapusan data pada List Berkait yaitu :
List Isi dan tersisa > 1 data
List Kosong (Awal/Head = NULL) printf(“LIST KOSONG”); List Isi dan hanya tersisa 1 data (Awal = Akhir)
Hapus di Awal Awal
Awal
Akhir 45
25
35
Awal Akhir
Awal
Akhir
25
1 HapusNow
Akhir
2
1
45
25
35 1. Awal -> Next = NULL
1. HapusNow = Awal
2
2. Akhir = Awal
2. Awal = HapusNow -> Next IF-UTAMA
IF-UTAMA
Menghapus Data pada List Berkait (3) 19
Menghapus Data pada List Berkait (4) 20
List Isi dan tersisa > 1 data (lanjutan)
Hapus di Akhir
Awal
Akhir 35
45
25
Awal
Telusuri Sampai HapusNow->info == Data yang akan dihapus dan jika HapusNow == Akhir, maka langkah penghapusannya adalah :
HapusNow
HapusSbl 35
1 25
45
Hapus di Tengah Akhir
35
1. HapusSbl -> Next = NULL 2. Akhir = HapusSbl
Awal
List Isi dan tersisa > 1 data (lanjutan)
Awal
HapusSbl 35
25
45
HapusNow 25
55
Akhir 45
55
Akhir 2 1
Telusuri Sampai HapusNow->info == Data yang akan dihapus dan jika HapusNow != Akhir, maka langkah penghapusannya adalah : 1. HapusSbl -> Next = HapusNow -> Next
IF-UTAMA
IF-UTAMA
5
4/9/2012
Untuk bahan renungan bersama
Studi Kasus II 21
22
Lanjutkan Studi Kasus I dengan menambahkan fungsi-fungsi sebagai berikut:
Data Nilai Mahasiswa (data terurut & tidak terurut)
Mencari Jumlah barang tertinggi dan terendah kemudian tampilkan kode barangnya Menghitung Jumlah Barang rata-rata Hapus Data Barang dengan jumlah barang terendah
Data Penjualan (data terurut & tidak terurut)
IF-UTAMA
Mencari IPK tertinggi dan terendah kemudian tampilkan NIM-nya Menghitung IPK rata-rata Hapus Data Nilai Mahasiswa dengan IPK terendah
Data Barang (data terurut & tidak terurut)
Mencari Jumlah Penjualan tertinggi dan terendah kemudian tampilkan kode sales dan kode barangnya Menghitung rata-rata penjualan Hapus Data Penjualan dengan jumlah penjualan terendah
Siapakah orang yang rugi? Orang yang rugi adalah orang yang sudah sampai usia pertengahan namun masih berat untuk melakukan ibadat dan amal-amal kebaikan. Maka hargailah waktumu dan bersegeralah Siapakah orang yang paling cantik/Tampan? Orang yang paling cantik/Tampan adalah orang yang mempunyai akhlak yang baik. Maka peliharalah akhlakmu dari dosa dan noda Siapakah orang yang mempunyai rumah yang paling luas? Orang yang mempunyai rumah yang paling luas adalah orang yang mati membawa amal-amal kebaikan dimana kuburnya akan di perluaskan sejauh mata memandang. Maka beramal shalehlah selagi sempat dan mampu Siapakah orang yang mempunyai rumah yang sempit lagi dihimpit ? Orang yang mempunyai rumah yang sempit adalah orang yang mati tidak membawa amalamal kebaikkan lalu kuburnya menghimpitnya. Maka ingatlah akan kematian dan kehidupan setelah dunia Siapakah orang yang mempunyai akal ? Orang yang mempunyai akal adalah orang-orang yang menghuni syurga kelak, karena telah menggunakan akal sewaktu di dunia untuk menghindari siksa neraka. Maka peliharalah akal sehatmu dan pergunakan semaksimal mungkin untuk mengharap ridho-Nya
IF-UTAMA
6
