This is My blog

SEARCHING

Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.

Sequential Search

Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal). Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
Misalnya terdapat array satu dimensi sebagai berikut:


Kemudian program akan meminta data yang akan dicari, misalnya 6. Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.


Binary Search


Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Binary Search adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian.
Prinsip pencarian biner adalah:

Sejarah dari Linked List

Linked List

Array VS Linked List

Bentuk Node Single Linked List non Circular

Pengertian:

Pembuatan Single Linked List

Deklarasi Node

typedef struct TNode{
int data;
TNode *next;
};

Penjelasan:
• Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
• Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

Pembuatan Node Baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;

Cara lain alokasi pointer
• Menggunakan alokasi memori secara manual
• Menggunakan header stdlib.h atau malloc.h
• Menggunakan fungsi:
*malloc(int size);



Single Linked List Menggunakan Head
• Dibutuhkan satu buah variabel pointer: head
• Head akan selalu menunjuk pada node pertama

Deklarasi Pointer Penunjuk Kepala Single Linked List

Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam linked list (dalam hal ini adalah head). Deklarasinya sebagai berikut:

TNode *head;

Fungsi Inisialisasi Single Linked List

void init(){
head = NULL;
}
Function untuk mengetahui kosong tidaknya Single
Linked List
Jika pointer head tidak menunjuk pada suatu node maka kosong

int isEmpty(){
if(head == NULL) return 1;
else return 0;
}

Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara: node head ditunjukkan ke node baru tersebut. Pada prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.

void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}
else {
baru->next = head;
head = baru;
}
cout<<”Data masuk\n”; }

Ilustrasi:
1. List masih kosong (head=NULL)

2. Masuk data baru, misalnya 5

3. Datang data baru, misalnya 20 (penambahan di depan)

Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali, node langsung ditunjuk oleh head. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui node terbelakang, kemudian setelah itu, dikaitkan dengan node baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
cout<<"Data masuk\n“; }

Ilustrasi :
1. List masih kosong (head=NULL)

2. Masuk data baru, misalnya 5

3. Datang data baru, misalnya 20 (penambahan di belakang)

4. Datang data baru, misalnya 25 (penambahan di belakang)

Bagaimana dengan penambahan di tengah?

void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<data<<" "; bantu=bantu->next;
}
cout<<“\n”; } else cout<<“Masih kosong\n“; }

Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai NULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti data masih kosong!

Function untuk menghapus data terdepan

void hapusDepan (){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = head->data;
head = NULL;
}
cout<<“%d terhapus\n“,d; } else cout<<"Masih kosong\n"; }

Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete. Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru). Jika head masih NULL maka berarti data masih kosong!

Hapus Belakang

void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
cout<<“%d terhapus\n“,d; } else cout<<“Masih kosong\n“; }

Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir. Pointer bantu akan digunakan untuk menunjuk ke nilai NULL. Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian pointer hapus diletakkan setelah pointer bantu. Setelah itu pointer hapus akan dihapus, pointe bantu akan menunjuk ke NULL.

Function untuk menghapus semua elemen Linked List
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
}

Single Linked List dengan HEAD & TAIL

Dibutuhkan dua buah variabel pointer: head dan tail. Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.

Inisialisasi LinkedList

TNode *head, *tail;

Fungsi Inisialisasi LinkedList

void init(){
head = NULL;
tail = NULL;
}

Function untuk mengetahui kosong tidaknya LinkedList

int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}

Pengkaitan node baru ke linked list di depan

Penambahan data baru di depan akan selalu menjadi head.

void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=tail=baru;
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
cout<<”Data masuk\n”; }


1. List masih kosong (head = tail = NULL)

2. Masuk data baru, misalnya 5

3. Datang data baru, misalnya 20

Penambahan Data di belakang

void tambahBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
cout<<"Data masuk\n“; }

Ilustrasi :
1. List masih kosong (head = tail = NULL)

2. Masuk data baru, misalnya 5

3. Datang data baru, misalnya 20

Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

Function untuk menampilkan isi linked list:

void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<<“%d\n”,bantu->data;
bantu=bantu->next;
}
cout<<“\n”; } else cout<<“Masih kosong\n“; }

Function untuk menghapus data di depan

void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head!=tail){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = tail->data;
head=tail=NULL;
}
cout<<“%d terhapus\n“,d; } else cout<<"Masih kosong\n“; }

Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan pointer hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru, kemudian menghapus pointer hapus dengan menggunakan perintah delete. Jika tail masih NULL maka berarti list masih kosong!

Function untuk menghapus data di belakang:

void hapusBelakang(){
TNode *bantu,*hapus;
int d;
if (isEmpty()==0){
bantu = head;
if(head!=tail){
while(bantu->next!=tail){
bantu = bantu->next;
}
hapus = tail;
tail=bantu;
d = hapus->data;
delete hapus;
tail->next = NULL;
}else {
d = tail->data;
head=tail=NULL;
}
cout<<<" terhapus\n"; } else cout<<"Masih kosong\n"; }

Function di atas akan menghapus data terbelakang (terakhir) yang ditunjuk oleh tail pada linked list. Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru. Setelah itu hapus pointer hapus dengan menggunakan perintah delete. Jika tail masih NULL maka berarti list masih kosong!

Function untuk menghapus semua elemen LinkedList

void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
tail = NULL;
}

by : Vivi Frismantini (080010231)

kelas : F081