inf202: struktur data linked list (senarai...

31
Pertemuan 12: INF202: Struktur Data LINKED LIST (Senarai Berantai) Dosen: Wayan Suparta, PhD

Upload: tranthu

Post on 24-Aug-2019

269 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Pertemuan 12:

INF202: Struktur Data

LINKED LIST (Senarai

Berantai)

Dosen: Wayan Suparta, PhD

Page 2: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

1. Dasar Teori

Linked List merupakan deretan elemen yang

berdampingan di memori namun masih terpencar-pencar.

Untuk mengakses semua elemen digunakan pointer

tunggal.

Masing-masing elemen terdiri dari dua bagian, yaitu

sebuah data dan sebuah pointer yang disebut dengan

pointer next.

Dengan menggunakan struktur two-member seperti ini,

linked list dibentuk dengan cara menunjuk pointer next

suatu elemen ke elemen yang mengikutinya. Pointer next

pada elemen terakhir merupakan NULL, yang

menunjukkan akhir dari suatu list.

Elemen pada awal suatu list disebut head, dan elemen

terakhir dari suatu list disebut tail.

Page 3: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Ketika sebuah variabel dideklarasikan, terlebih dahulu

harus diinisialisasi termasuk juga ’pengalokasian secara

dinamis’.

Fungsi untuk mengalokasikan sebuah node baru: fungsi

allocate_node() menggunakan malloc() untuk

mendapatkan memori aktual, yang akan menginisialisasi

suatu field data.

next selalu diinisialisasi sebagai NULL.

Untuk melihat kemungkinan alokasi memori gagal, maka

fungsi allocate_node menghasilkan 0, sebaliknya 1 jika

berhasil.

Untuk membebaskan node digunakan fungsi free_node.

Fungsi dari alokasi node adalah sebagai berikut :

Page 4: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 5: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Inisialisasi LIST setelah alokasi untuk node pertama sebagai

berikut:

Fungsi free_node() akan menghancurkan node yang

menunjuk ke pointer yang dilewati karena itu pointer

didefinsikan dengan NULL:

Page 6: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

2. Operasi Pada Linked List

Opearsi penting pada Linked List:

Insert

Delete

Fungsi INSERT meliputi

insert sebagai node awal (head) dari linked list

insert setelah node tertentu

insert sebelum node tertentu

insert sebagai node akhir (tail) dari linked list.

Fungsi DELETE meliputi

delete sebagai simpul pertama(head) dari linked list

delete setelah simpul tertentu

delete simpul terakhir

Page 7: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(a) Insert sebagai node awal (head) dari linked list

Page 8: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(b) Insert setelah node tertentu

Page 9: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 10: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 11: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(c) Insert sebelum node tertentu

Statement untuk insert setelah node tertentu dari linked list adalah

Page 12: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 13: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 14: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(d) Insert di akhir (tail) dari linked list

Page 15: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

do

Page 16: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen
Page 17: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(2) Fungsi DELETE

(a)

Langkah

penghapusan

1. Pointer first

diarahkan data

ke-2

2. Pointer p

diarahkan pada

data ke-1

3. Bebaskan

pointer p

(secara otomatis

data ke-1

terhapus)

Page 18: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(b)

Page 19: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

(c)

Langkah-langkah untuk proses di atas adalah sebagai berikut:

1. Telusuri simpul s/d first->next = NULL

2. Arahkan pointer p ke first

3. Bebaskan pointer p->next (Simpul Terakhir)

4. Arahkan p->next ke NULL

Page 20: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

3. MERUBAH ISI DARI SUATU SIMPUL PADA

LINKED LIST

1. Menulusuri linked list sampai didapatkan simpul yang akan dirubah.

Page 21: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Contoh KASUS Polinomial

Pertimbangkan dua polinomial f(x) dan g(x), yang dapat diwakili

menggunakan linked list.

h (x) dapat direpresentasikan dengan h(x)= f(x)+ g(x)=

f(x) = ax3 + bx + c dan g(x) = mx4 + nx3 + ox2 + px + q

Yaitu menambahkan konstanta dari polynomial yang sesuai dari

eksponensial sama.

Kedua polinomial dapat ditambahkan dengan:

h(x)= f(x)+ g(x)= mx4 + (a + n) x3 + ox 2 + (b + p)x + (c + q)

yaitu menambahkan konstanta dari polinomial yang sesuai dari

eksponensial sama.

Hasil dari H(x) dapat dijabarkan seperti gambar berikut:

Page 22: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Contoh Program 1:

Menambah data di depan dan di akhir

//Program linked list for Node Insert Kiri dan Insert Kanan #include <iostream> #include <cstdlib> #include <stdlib.h> #include <conio.h> using namespace std; struct node { int urut; node *next; }; node *awal_ptr = NULL; node *posisi; //digunakan untuk membaca sepanjang list int option = 0;

//Tambah data di depan void tambah_awal_list() { node *baru; baru = new node; cout << "Masukkan Data : "; cin >> baru->urut; baru->next = NULL; if(awal_ptr == NULL) { awal_ptr=baru; awal_ptr->next = NULL; } else { baru->next = awal_ptr; awal_ptr = baru; } }

Page 23: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

//Tambah data di akhir

void menambah_node_di_akhir()

{

node *temp, *temp2; // Temporary pointers

// menciptakan node baru

temp = new node;

cout << "Masukkan urut : ";

cin >> temp->urut;

temp->next = NULL;

// Set up link pada node

if (awal_ptr == NULL) {

awal_ptr = temp;

posisi = awal_ptr; }

else

{ temp2 = awal_ptr;

// node tidak NULL – list tidak kosong

while (temp2->next != NULL)

{ temp2 = temp2->next;

// Memindahkan pada next link dalam rantai

}

temp2->next = temp; }

}

//Menampilkan data

void display_list()

{

node *temp;

temp = awal_ptr;

cout << endl;

cout << "DATA [";

if (temp == NULL)

cout << "List kosong!" << endl;

else

{

while (temp != NULL)

{ // Menampilkan detail data

cout << "" << temp->urut <<

",";

if (temp == posisi)

cout << " <<<< posisi node";

// cout << endl;

temp = temp->next; }

cout << "] ";

cout << "Akhir list!" << endl;

}

}

Page 24: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

//Inisialisasi Nilai

int init(int nilai){

node *baru;

baru = new node;

baru->urut=nilai;

baru->next = NULL;

if(awal_ptr == NULL)

{

awal_ptr=baru;

awal_ptr->next = NULL;

}

else

{

baru->next = awal_ptr;

awal_ptr = baru;

}

}

//Program Utama

int main()

{

cout << "===================" << endl;

cout << "STRUKTUR DATA - LINKED LIST"

<< endl;

cout << "===================" << endl;

awal_ptr = NULL;

init(10); //data kanan

init(12);

init(5);

init(7);

init(22); //data kiri

do {

// clrscr();

display_list();

cout << endl;

cout << "MENU PILIHAN : " << endl;

cout << "1. Tambah Sebelah Kiri" << endl;

cout << "2. Tambah Sebelah Kanan" <<

endl;

cout << "3. EXIT" << endl;

cout << endl << " Pilihan >> ";

cin >> option;

Page 25: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

switch (option)

{

case 1 : tambah_awal_list();

break;

case 2 : menambah_node_di_akhir();

break;

}

}

while (option != 3);

}

Output Program:

Tambah data kiri: Tambah data kanan:

Page 26: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

Contoh Program 2: Fungsi lainnya

//Hapus data di depan

void hapus_awal_node()

{

node *temp;

temp = awal_ptr;

awal_ptr = awal_ptr->next;

delete temp;

}

//Hapus data di akhir

void hapus_akhir_node()

{

node *temp1, *temp2;

if (awal_ptr == NULL)

cout << "List kosong!" << endl;

else

{

temp1 = awal_ptr;

if (temp1->next == NULL)

{

delete temp1;

awal_ptr = NULL;

}

else

{

while (temp1->next != NULL)

{

temp2 = temp1;

temp1 = temp1->next;

}

delete temp1;

temp2->next = NULL;

}

}

}

Page 27: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

//Pindah pointer ke posisi sebelumnya

void pindah_posisi_sebelumnya()

{

if (posisi->next == NULL)

cout << “Pointer berada di akhir list" << endl;

else

posisi = posisi->next;

}

//Pindah pointer ke posisi berikutnya

void pindah_posisi_berikutnya()

{

if (posisi == awal_ptr)

cout << “Pointer berada pada awal list" <<

endl;

else

{

node *previous; // deklarasi pointer

previous = awal_ptr;

while (previous->next != posisi)

{ previous = previous->next; }

posisi = previous; }

}

//Tambah data di tengah

void tambah_tengah_list()

{ node *baru, *bantu;

int posisi_sisip;

if(awal_ptr != NULL) {

cout<<"Akan diinsert setelah Data

Ke ? ";

cin>>posisi_sisip;

baru =new node;

bantu=awal_ptr;

for(int i=1;i<posisi_sisip-1;i++) {

if(bantu->next != NULL)

bantu=bantu->next;

else

break; }

cout << "Masukkan urut : ";

cin >> baru -> urut;

baru->next = bantu -> next;

bantu->next=baru; }

else

{ cout<<"Belum ada data !! silahkan

isi data dulu....";

getch(); } }

Page 28: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

//Hapus data di posisi tengah

void Hapus_tengah_list()

{

int bykdata,posisi_hapus,poshapus;

node *hapus, *bantu;

if(awal_ptr != NULL)

{

cout<<" Akan dihapus pada data ke : ";

cin>>posisi_hapus;

bykdata=1;

bantu=awal_ptr;

while(bantu->next != NULL)

{

bantu=bantu->next;

bykdata++;

}

if((posisi_hapus<1)||(posisi_hapus>bykdata))

{

cout<<"Belum ada data !! Boleh

memasukkan data.\n";

}

else

{

bantu=awal_ptr;

poshapus=1;

while(poshapus<(posisi_hapus-1))

{

bantu=bantu->next;

poshapus++;

}

hapus=bantu->next;

bantu->next=hapus->next;

delete hapus;

}

}

else

cout<<"Data Masih kosong, tidak

bisa menghapus data dari tengah! ";

getch();

}

Page 29: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

//Program Utama Lengkap

display_list();

cout << endl;

cout << "MENU PILIHAN: " << endl;

cout << "1. Tambah data di awal" << endl;

cout << "2. Tambah data di akhir." << endl;

cout << "3. Tambah data di tengah."<< endl;

cout << "4. Hapus data di awal" << endl;

cout << "5. Hapus data di akhir" << endl;

cout << "6. Hapus data di tengah" << endl;

cout << "7. Pindah posisi pointer ke

berikutnya" << endl;

cout << "8. Pindah posisi pointer ke

sebelumnya" << endl;

cout << "9. EXIT" << endl;

cout << endl << " Pilihan >> ";

cin >> option;

switch (option)

{

case 1 : tambah_awal_list();

break;

case 2 : menambah_node_di_akhir();

break;

case 3 : tambah_tengah_list();

break;

case 4 : hapus_awal_node();

break;

case 5 : hapus_akhir_node();

break;

case 6 : Hapus_tengah_list();

break;

case 7 : pindah_posisi_sebelumnya();

break;

case 8 : pindah_posisi_berikutnya();

}

}

while (option != 9);

}

Page 30: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

LATIHAN 18 A. Diketahui:

P1 = 6x8 + 8x7 + 5x5 + x3 + 15

P2 = 3x9 + 4x7 + 3x4 + 2x3 + 2x2 + 10

P3 = x2 + 5

Representasikan bilangan polinom dengan menggunakan

linked list dan buatlah prosedur-prosedur untuk :

• Menyisipkan simpul di awal jika pangkat yang dimasukkan

lebih dari pangkat tertinggi dari bilangan polinomial.

• Menyisipkan simpul di tengah jika pangkat dari bilangan yang

kita sisipkan berada di tengah.

• Menyisipkan simpul di akhir jika pangkat dari bilangan yang

disisipkan adalah 0.

• Menghapus simpul, baik di awal, di tengah, ataupun di akhir.

Page 31: INF202: Struktur Data LINKED LIST (Senarai Berantaiocw.upj.ac.id/files/Handout-INF202-INF202-Struktur-Data-Wayan-Pertemuan-12.pdf · 1. Dasar Teori Linked List merupakan deretan elemen

B. Dari contoh program 1 dan 2, gabungkan program tersebut

dengan output proram:

C. Implementasikan sebuah single linked list yang dapat

merepresentasikan data mahasiswa. Data mahasiswa berupa NIM,

Nama, Alamat dan Indeks Prestasi. Buatlah fungsi-fungsi untuk

menelusuri, menambah simpul dan menghapus simpul.

MENU PILIHAN:

1. Tambah data di awal

2. Tambah data di akhir

3. Tambah data di tengah

4. Hapus data di awal

5. Hapus data di akhir

6. Hapus data di tengah

7. EXIT