Graph

Graph pada java

Graf adalah salah satu jenis struktur data yang terdiri dari titik(vertex) dan garis(edge), dimana dalam graf tersebut, vertex vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge. Agar lebih jelas perhatikan gambar dibawah ini : Dalam gambar tersebut, terdapat beberapa kota yang berada dipulau jawa dimana kota kota tersebut dihubungkan oleh beberapa jalur jalur yang ada. Untuk contoh diatas kita bisa menganggap bawah kota kota yang ada merupakan vertex, dan jalur jalur yang menghubungkan kota kota tersebut sebagai edge. Sehingga secara keseluruhan peta diatas dapat dibuat pemodelannya sebagai sebuah graf. Ada terdapat beberapa jenis graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut : 

~ Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan 

~ Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah, sehigga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A. 

~ Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu. 

~ Graf Tak Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai. 

Untuk merepresentasikannya dalam pemrograman komputer, graf dapat disusun dari LinkedList yang berada dalam LinkedList. Perhatikan contoh graf berarah dibawah ini : Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan vertex yang ada. Dalam matrik diatas dapat kita lihat bahwa kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut. Untuk representasi dalam pemorgraman komputer, graf tersebut dapat digambarkan seperti dibawah ini :

JTree

Terminologi

binary tree

maaf saya menggunakan istilah asing untuk terminologinya. soalnya saya sudah terbiasa pakai istilah ini, kalaupun diterjemahkan kuq hasilnya malah jadi aneh…

Path
Bayangkan seperti orang yang berjalan dari node ke node lain melalui garis yang menghubungkannya. Garis-garis penghubung yang delewati itulah yang dinamakan dengan path.

Root
Node pada posisi paling atas disebut root. Dalam sebuah tree hanya terdapat satu root saja.

Parent
Setiap node (kecuali root) mempunyai cabang yang menguhubungkan tepat satu node lain di atasnya. Node di atasnya inilah yang disebut parent.
Child
Setiap node bisa mempunyai satu atau lebih cabang yang menghubungkan ke node lainnya. Node di bawahnya inilah yang disebut dengan child.
Leaf
Node yang tidak mempunyai child disebut dengan leaf. Dalam sebuah tree hanya ada satu root saja tetapi bisa mempunyai banyak leaf.
Subtree
Setiap node bisa dipertimbangkan menjadi root nya subtree, yang terdiri dari beberapa children, dan children nya children.
Visiting
Sebuah node dikatakan dikunjungi ketika kendali program sampai pada sebuah node, biasanya untuk tujuan menyelesaikan beberapa operasi pada node, seperti mengecek nilai datanya kemudian menampilkannya.
Traversing
Traverse maksudnya mengunjungi semua node dalam tree untuk tujuan tertentu, misalnya: untuk mengurutkan datanya.
Level
Level node adalah banyaknya generasi node yang dihitung mulai dari root. Jika kita mengasumsikan bahwa root adalah level 0, maka children adalah level 1, grandchildren adalah level 2, dan seterusnya.
Key
Medan data dalam sebuah objek biasanya didesain dengan menggunakan sebuah key. Nilai dari key ini digunakan untuk melakukan pencarian data atau operasi lainnya.

Tree menggunakan Java
Beberapa class untuk mendemonstrasikan binary tree di java

Class Node –> untuk membuat node
class Node
{
int iData;                  // data yang digunakan sebagai kunci
double fData;         // data lain
node childKiri;     // node child kiri
node childKanan;         // node child kanan
public void tampilNode()
{
// (bagian dari tubuh method)
}
}
Class Tree –> membuat susunan Tree nya dimana di dalamnya juga terdapat beberapa method untuk:
pencarian node
penyisipan node
penghapusan node

class Tree
{
private Node root;     // satu-satunya data dalam tree
public void cari(int key)
{
tempat penulisan statemen cari
}
public void sisip(int id, double dd)
{
tempat penulisan statemen sisip
}
public void hapus(int id)
{
tempat penulisan statemen hapus
}
// klo ada method laen tulis di sini
}    // akhir dari kelas tree

Heap

Heap Java

Pengertian:

Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.

 

Jenis-jenis heap:

Min Heap  : Nilai setiap node lebih kecil dari anak-anaknya

Contoh Min Heap:

Max Heap : Nilai setiap node lebih besar dari anak-anaknya

Operasi-operasi yang digunakan untuk heap adalah:

1. Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.  
2. Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul. 
3. Insert: menambahkan sebuah nilai ke dalam heap.  
4. Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut. 

Implementasi pada array:

1. Unsur-unsur disimpan berurutan dari indeks 1 sampai N dari atas ke bawah dan dari kiri ke kanan node pohon.
2. Root disimpan dalam indeks 1 (kita membiarkan indeks 0 menjadi kosong / tidak terpakai).

Representasi array:

Memasukkan Min-Heap

• Masukkan unsur baru pada akhir heap
• Naikkan heap baru/angka yang perlu dinaikkan

Penghapusan pada Min-Heap

• Perhatikan penghapusan elemen terkecil yang terletak pada akar.
• Ganti root dengan elemen terakhir dari heap
• Penurunan jumlah elemen dalam tumpukan
• Memperbaiki properti heap nya

Min-Max Heap

• Kondisi tumpukan bergantian antara tingkat minimum dan maksimum untuk tingkat
• Tujuan min-max tumpukan adalah untuk memungkinkan kita untuk menemukan keduaelemen terkecil 

   dan terbesar dari tumpukan pada waktu yang sama. 

Penghapusan pada Min-Max Heap

• Penghapusan elemen terkecil:
  - Ganti root dengan elemen terakhir dalam tumpukan.
  - Penurunan jumlah elemen dalam tumpukan.
  - Downheapmin dari root.

• Penghapusan elemen terbesar:
  - Ganti anak kiri atau kanan-anak dari akar (tergantung pada mana yang lebih besar) dengan elemen

     terakhir dalam tumpukan.
  - Penurunan jumlah elemen dalam tumpukan.
  - Downheapmax dari node.

Map pada JAVA

Suatu array yang berisi N elemen bisa juga dilihat sebagai asosiasi (pemetaan) antara elemennya dengan bilangan 0, 1, ..., N-1 yang merupakan indeksnya. Jika i adalah salah satu bilangan ini, maka kita bisa mengambil elemen yang dipetakan oleh bilangan i, dan juga kita bisa meletakkan elemen baru pada posisi ke-i.
Suatu peta (map) adalah generalisasi dari array. Seperti array, map juga memiliki operasi untuk mengambil dan meletakkan elemen. Akan tetapi pada map, operasi ini tidak dilakukan pada bilangan 0, 1, ... N-1, akan tetapi pada sembarang Object.
Beberapa bahasa pemrograman menggunakan istilah array asosiatif (associative array) karena kesamaan perintah dengan array biasa. Pada bahasa pemrograman tersebut, kita bisa menuliskan A["joko"] yang digunakan untuk memetakan "joko" pada suatu elemen di dalam array.
Java tidak menggunakan perintah yang sama pada map, akan tetapi idenya serupa : Map adalah seperti array yang indeksnya adalah objek sembarang, bukan integer. Pada map, objek yang digunakan sebagai "indeks" disebut kunci (key). Objek yang ditunjuk oleh indeks tersebut disebut nilai (value).
Satu kunci hanya boleh menunjuk pada satu nilai, akan tetapi satu nilai bisa ditunjuk oleh beberapa kunci.
Dalam Java, map didefinisikan dalam interface java.util.Map, yang memiliki beberapa metode untuk bekerja dengan map. Jika map adalah variabel dengan tipe Map, maka berikut ini adalah beberapa metodenya :

• map.get(kunci) -- mengembalikan Object yang ditunjuk oleh kunci. Jika map tidak memiliki nilai yang ditunjuk oleh kunci, maka nilai null akan dikembalikan. Tapi ingat juga bahwa mungkin saja kuncinya ada akan tetapi memang menunjuk pada nilai null. Menggunakan "map.get(kunci)" sama dengan perintah "A[kunci]" pada array A. (Akan tetapi pada map tidak ada pengecualian IndexOutOfBoundsException)
• map.put(kunci, nilai) -- Mengisi map dengan pasangan kunci dan nilai. Kedua-dua kunci dan nilai bisa berupa objek apa saja. Jika map tersebut telah memiliki kunci maka nilai yang ditunjuk akan diganti dengan yang baru diberikan. Perintah ini mirip dengan "A[kunci] = nilai" pada array.
• map.putAll(map2) -- jika map2 adalah map lain, maka perintah ini akan mengkopi semua isi pada map2 ke dalam map.
• map.remove(kunci) -- Jika map memiliki kunci yang menunjuk pada suatu nilai, perintah ini akan menghapus kunci beserta nilai yang ditunjuknya, atau dengan kata lain menghapus pasangan kunci dan nilai pada map sekaligus.
• map.containsKey(kunci) -- mengembalikan nilai boolean true jika map memiliki kunci yang merujuk pada suatu nilai
• map.containsValue(nilai) -- mengembalikan nilai boolean true jika map memiliki nilai yang ditunjuk oleh kunci apapun.
• map.size() -- mengembalikan int yang berisi jumlah pasangan asosiasi pada map.
• map.isEmpty() -- mengembalikan boolean true jika map tidak berisi pasangan asosiasi apa-apa.
• map.clear() -- menghapus semua pasangan asosiasi dalam map.

Metode put dan get jelas merupakan metode yang paling sering digunakan dalam map. Dalam banyak aplikasi, metode ini mungkin hanya metode ini yang kita butuhkan. Artinya, menggunakan map sama mudahnya dengan menggunakan array biasa.
Java memiliki dua kelas yang mengimplementasikan interface Map, yaitu : TreeMap dan HashMap.
Dalam TreeMap, pasangan kunci/nilai disimpan secara berurutan dalam pohon terurut, yaitu diurut berdasarkan kuncinya. Supaya bisa bekerja dengan benar, maka hanya objek yang bisa dibandingkan saja yang bisa digunakan sebagai kunci. Artinya kelas kunci harus berupa kelas yang mengimplementasikan interface Comparable, atau Comparator harus diberikan pada konstruktornya pada saat TreeMap dibuat.
HashMap tidak menyimpan pasangan kunci/nilai dalam urutan tertentu, sehingga tidak ada batasan objek apa yang bisa disimpan di dalamnya. Hampir semua operasi dapat berjalan lebih cepat pada HashMap dibandingkan dengan TreeMap.
Secara umum, lebih baik menggunakan HashMap kecuali kita butuh struktur data dalam urutan tertentu yang hanya bisa dilakukan dengan TreeMap. Atau dengan kata lain, jika kita hanya menggunakan perintah put dan get, gunakan HashMap.
Misalnya progrma direktori telefon, yaitu pada kelas BukuTelepon yang memiliki pasangan nama/nomor telepon. Kelas ini memiliki operasi tambahEntri(nama, nomor) dan ambilNomor(nama), di mana nama dan nomor bertipe String.
Dalam aplikasi pemrograman sebenarnya, kita tidak perlu lagi membuat kelas baru untuk mengimplementasikan BukuTelepon tersebut, artinya kita bisa langsung menggunakan Map. Akan tetapi menggunakan Map mungkin memiliki sedikit kerugian, karena kita dipaksa harus menggunakan Object bukan String.
Jika ini masalahnya, maka kita bisa membuat kelas baru yang menggunakan Map dalam implementasinya, seperti berikut :

import java.util.HashMap;
 
public class BukuTelepon {
 
    // Menyimpan data telepon
    private HashMap info = new HashMap();
 
    public void tambahEntri(String nama, String nomor) {
        // Menyimpan nomor telepon pada nama yang sesuai
        info.put(nama,nomor);
    }
 
    public String ambilNomor(String nama) {
        // Mengambil nomor telepon dari nama
        // Kembalikan null jika tidak ada nomor telepon untuk nama tsb
        return (String)info.get(nama);
    }
 
} // akhir kelas BukuTelepon

Dalam metode ambilNomor di atas, nilai kembalian dari info.get(nama) di-type-cast ke dalam String. Karena kembalian dari metode get() bertipe Object maka type cast menjadi penting sebelum nilainya bisa digunakan.
Dengan "membungkus" Map di dalam kelas BukuTelepon, kita menyembunyikan type-cast dalam implementasinya sehingga interaksi kelas ini dengan kelas lain yang menggunakannya menjadi lebih natural.

Search dan Sorting

SEQUENTIAL SEARCH
Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. Kelebihan dari proses pencarian secara sequential ini jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan. Pertama, jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya. Kedua, beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.
Contoh :
import java.util.Scanner;
public class sequential {
public static void main(String[]args)
{
int cepi[] = {11,1,8,50,120,5,3,100};
int n,tita,i;
Scanner input=new Scanner(System.in);
System.out.print(“Masukan Nilai  :”);n=input.nextInt();
tita=0;
i=0;
for(i=0;i<cepi.length;i++)
{
if (cepi[i]==n)
tita=1;
}
if (tita==1)
System.out.println(“Data Ditemukan”);
else
System.out.println(“Data Tidak Ditemukan”);
}
}
Penjelasan Klik Disini
Klik Disini Jika Terjadi Kesalahan
BUBBLE SORT
bubble sort adalah menempatkan (mengapungkan) nilai terbesar pada elemen paling kanan pada setiap tahap, sehingga nilai di bubblekan sebagai hasil proses tiap tahap.
sequential
Contoh :
public class bubble2{
public static void main(String a[]){
int i;
int cepi[] = {11,1,8,50,120,5,3,100};
System.out.println(“Cetakan isi array sebelum disort:”);
for(i = 0; i < cepi.length; i++)
System.out.print( cepi[i]+”  “);
System.out.println();
bubble_srt(cepi, cepi.length);
System.out.println(“”);
System.out.print(“Cetakan isi array setelah disort:\n”);
for(i = 0; i <cepi.length; i++)
System.out.print(cepi[i]+”  “);
}
public static void bubble_srt( int a[], int n ){
int i, j,t=0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}

Refensi : http://itbego.wordpress.com/2011/04/10/search-dan-sorting-dalam-pemograman-java/

Recursion

Definisi Recursive 

 

Recursive adalah proses pemanggilan dirinya sendiri (fungsi atau prosedur). Fungsi maupun prosedur yang memanggil dirinya disebut fungsi atau prosedur rekursif. Fungsi untuk suatu bagian program yang mengembalikan (menghasilkan) hanya satu nilai. Sebuah function call adalah suatu ekspresi jadi ia memberikan satu nilai.Procedure adalah suatu bagian program yang melakukan aksi/fungsi khusus, biasanya berdasarkan sekumpulan parameter. Sebuah procedure call adalah suatu statemen, jadi ia melakukan aksi. Banyak obyek dalam matematika didefinisikan dengan menampilkan suatu proses untuk  menghasilkan obyek-obyek tsb.

Misalnya : n faktorial (n!) didefinisikan sebagai produk dari semua integer diantara n dan 1. Contoh lain adalah bilangan asli. 1 adalah bilangan asli.Successor dari 1 adalah bilangan asli.

Perbedaan rekursi dengan prosedur/fungsi adalah rekursi bisa memanggil kedirinya sendiri tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur/fungsi. Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah tersebut dapat direduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil. Secara umum suatu algoritma rekursif selalu mengandung 2 macam kasus :

1. satu atau lebih kasus yang pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa yg lebih sederhana (menggunakan recursive call).
2. satu atau lebih kasus pemecahan masalahnya dilakukan tanpa recursive call. Kasus ini disebut kasus dasar atau penyetop. Supaya tidak terjadi rekursif tak hingga, maka setiap langkah rekursif haruslah mengarah ke kasus penyetop.

Sistem komputer mengikuti jalannya program yang rekursif biasanya dengan menggunakan suatu struktur data yang disebut stack. Ketika eksekusi program sampai pada suatu rekursif call, ia menghentikan sementara komputasi yg sedang dilaksanakannya sekarang untuk melakukan recursive call tsb, agar ia dapat kembali ke keadaan semula setelah recursive call itu selesai , ia harus menyimpan informasi yang cukup. Informasi yg diperlukan disebut activation frame.  Activation frame disimpan pada bagian memori yg diatur dalam benruk stack.  Rekursif yang berlapis-lapis dapat menghabiskan memori yang mengakibatkan stack overflow.  Masalah yg mempunyai solusi rekursif juga mempunyai solusi iteratif(menggunakan loop).  Versi iteratif seringkali lebih efisien daripada versi rekursif karena rekursif biasanya menggunakan memori yg lebih besar dan memerlukan waktu ekstra u/ penanganan stack of activation frame.

Contoh 1 menghitung faktorial :

Hasil Outputnya

Parameter and local Variable

Stacks  adalah Struktur data dimana data yang terkhir masuk adalah data yang akan diproses terlebih dahulu. Stack biasanya dimplementasikan dengan menggunakan sebuah array,dalam stack kita bisa menambah data dengan perintah operasi push,dan menghapus data dengan menggunakan perintah operasi pop

Fungsi Rekursi pada Matematika

Banyak fungsi matematika yang dapat didefinisikan dengan rekursi.

Contoh: fungsi faktorial dari n (n!), dapat didefinisikan secara iteratif :

0! Adalah 1 dan  n! Adalah n x (n-1)!, untuk n>0

Misal: 4! Adalah 4 x 3!, yang artinya 4 x 3 x 2 x 1, atau 24

Iteratif  dan  rekursi

1.      Persamaan dan perbedaan Iteraktif dan rekursif

• Persamaan

          Sama-sama merupakan bentuk perulangan

          Dilakukan pengecekan kondisi terlebih dahulu sebelum mengulang

• Perbedaan

          Pada rekursi, dikenal adanya istilah recursive step

          Sedangkan pada iteratif ada decrement

Kelebihan dan kekurangan recursive

• Kelebihan

          solusi sangatlah efisien

          dapat memecahkan masalah yang sulit dengan tahapan yang mudah dan singkat

• Kelemahan

          sulit dipahami

          perlu stack besar (stack overrun)

Kasus Menara Hanoi 

Definisi menara hanoi

Menara Hanoi adalah problem di mana kita harus memindahkan balok yang mempunyai perbedaan ukuran dari suatu menara (tower) ke menara lainnya.

Masalah  :

1. Memindahkan n balok dari menara A ke menara C menggunakan menara B bila dibutuhkan.

2. Hal yang harus dicermati :

Hanya satu buah balok saja yang dapat dipindahkan dalam satu waktu  balok yang lebih besar tidak boleh diletakkan di atas balok yang lebih kecil

Stack dan Queue

STACK (TUMPUKAN)

Stack (tumpukan) sebenarnya secara mudah dapat diartikan sebagai list (urutan) dimana penambahan dan pengambilan elemen hanya dilakukan pada satu sisi yang disebut top (puncak) dari stack.
Dengan melihat definisi tersebut maka jelas bahwa pada stack berlaku aturan LIFO (Last In First Out), yaitu elemen yang terakhir masuk akan pertama kali diambil atau dilayani. Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selsnjutnya meletakkan piring kedua di atas piring pertama dan demikian seterusnya. Pada saat kita hendak mengambil satu piring dari tumpukan tersebut, tentu yang diambil adalah piring teratas (yang terakhir kali ditaruh), bukan yang terbawah (yang pertama kali diletakkan).

Dua operasi dasar pada stack adalah PUSH (operasi pemasukan elemen ke dalam stack) dan POP (operasi pengambilan satu elemen dari dalam stack). Di bawah ini diberikan contoh pemakaian operasi PUSH dan POP dan isi stack untuk setiap selesai eksekusi satu operasi.
(Untuk mempermudah penulisan, di bawah ini isi stack tidak dituliskan secara bertumpuk, tetapi dengan kesepakatan:

• elemen paling kanan adalah elemen yang ada pada TOS (Top Of the Stack)
• stack yang dipakai bernama S
• PUSH(S,B) berarti memasukkan elemen B ke dalam stack S
• POP(B,S) berarti mengambil elemen dari stack S dan menaruhnya ke dalam variabel B

Operasi yang dilakukan	Isi Stack	Keterangan
Kondisi Awal	kosong	-
PUSH(‘A’,S)	A	-
PUSH(‘B’,S)	AB	-
PUSH(‘C’,S)	ABC	-
POP(Data,S)	AB	Variabel Data berisi ‘C’
PUSH(‘D’,S)	ABD	-
POP(Data,S)	AB	Data berisi ‘D’
POP(Data,S)	A	Data berisi ‘B’

---

ke atas halaman

---

IMPLEMENTASI STACK DALAM BAHASA PASCAL

Implementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang adadi dalam array yang sekaligus menunjukkan TOS. Pada implementasi di bawah ini:

• konstanta maxelm menyatakan banyaknya elemen maksimum yang dapat ditampung oleh stack
• typeelemen adalah tipe data yang akan disimpan di dalam stack (bisa integer, word, real, boolean, char , string atau lainya)
• banyak adalah field yang menyatakan banyaknya elemen dalam stack saat itu, yang sekaligus menyatakan TOS

Deklarasi tipe untuk tumpukan (stack):
type tumpukan = record
banyak :0..maxelm;
elemen : array[1..maxelm] of typeelemen;
end;

Selain prosedur untuk POP dan PUSH, kita dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan diantaranya adalah fungsi PENUHS (untuk mengecek apakah stack penuh) fungsi KOSONGS (untuk mengecek apakah stack kosong) dan fungsi SIZES (untuk mengetahui banyaknya elemen di dalam stack). Masing-masing sub program di atas dapat disajikan pseudocode-nya sebagai berikut:

---

Procedure Inisialisasi(var S : tumpukan);
begin
S. banyak¬ 0
end;

---

Function PENUHS(S : tumpukan): boolean;
begin
Jika S.banyak = maxelm maka PENUHS ¬ true
else PENUHS ¬false
end;

---

Function KOSONGS(S : tumpukan):boolean;
begin
If S.banyak = 0 then KOSONGS ¬ true
else KOSONGS¬false
end;

---

Procedure PUSH(data : tipeelemen; var S : tumpukan);
begin
If not KOSONGS(S) then
begin

1. S.banyak ¬ S.banyak +1
2. S.elemen[S.banyak]¬data

end
else
Tampilkan pesan kesalahan “Stack Penuh”
end;

---

Procedure POP(var S : tumpukan; var data : typeelemen);
begin
If not KOSONGS(S) then
begin

1. data¬S.elemen[S.banyak]
2. S.banyak ¬ S.banyak – 1

end
else
Tampilkan pesan kesalahan “Stack kosong”
End;

---

ke atas halaman    ke menu utama

---

QUEUE (ANTRIAN)

Queue atau antrian sebenarnya juga merupakan suatu list. Salah satu sifat yang membedakan queue dengan stack adalah bahwa pada queue penambahan elemen dilakukan pada salah satu ujung (ujung depan) dan pengambilan dilakukan pada ujung yang lain (ujung belakang) . Dengan demikian queue menggunakan prinsip FIFO (First In First Out), yaitu elemen yang pertama masuk akan pertama kali pula dikeluarkan.
Seperti pada stack, operasi-operasi dasar pada queue adalah operasi penambahan elemen ( sebut “ADDQ”) dan operasi pengambilan elemen (sebut DELQ). Di bawah ini diberikan contoh pemakaian operasi PUSH dan POP dan isi stack untuk setiap selesai eksekusi satu operasi.
(Untuk mempermudah penulisan, di bawah ini isi queue tidak dituliskan secara bertumpuk, tetapi dengan kesepakatan:

• elemen paling kanan adalah elemen yang ada pada ujung belakang (yang terakhir kali masuk)
• queue yang dipakai bernama Q
• ADDQ(Q,B) berarti memasukkan elemen B ke dalam queue Q
• DELQ(B,Q) berarti mengambil elemen dari queue Q dan menaruhnya ke dalam variabel B

Operasi yang dilakukan	Isi Queue	Keterangan
Kondisi Awal	kosong	-
ADDQ(‘A’,Q)	A	-
ADDQ(‘B’,Q)	AB	-
ADDQ(‘C’,Q)	ABC	-
DELQ(Data,Q)	BC	Variabel Data berisi ‘A’
ADDQ(‘D’,Q)	BCD	-
DELQ(Data,Q)	CD	Data berisi ‘B’
POP(Data,S)	D	Data berisi ‘C’

---

ke atas halaman

---

IMPLEMENTASI QUEUE DALAM BAHASA PASCAL

Implementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array. Pada implementasi di bawah ini:

• konstanta maxelm menyatakan banyaknya elemen maksimum yang dapat ditampung oleh queue
• typeelemen adalah tipe data yang akan disimpan di dalam queue(bisa integer, word, real, boolean, char , string atau lainya)
• banyak adalah field yang menyatakan banyaknya elemen dalam queue saat itu
• queue diimplementasikan sebagai array linier dengan memandang bahwa elemen terdepan selalu berada pada sel pertama (implementasi fisik), sehingga bila terjadi pengambilan satu elemen maka semua elemen di belakang elemen terambil (bila ada) harus digeser ke depan satu langkah

Deklarasi tipe untuk antrian (queue):
type antrian= record
banyak :0..maxelm;
elemen : array[1..maxelm] of typeelemen;
end;

Selain prosedur untuk ADDQ dan DELQ, kita dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan diantaranya adalah fungsi PENUHQ (untuk mengecek apakah antrian penuh) fungsi KOSONGQ (untuk mengecek apakah antrian kosong) dan fungsi SIZEQ (untuk mengetahui banyaknya elemen di dalam queue). Masing-masing sub program di atas dapat disajikan pseudocode-nya sebagai berikut:

---

Procedure Inisialisasi(var q : antrian);
begin
Q. banyak ¬ 0
end;

---

Function PENUHQ(q : antrian): boolean;
begin
Jika Q.banyak = maxelm maka PENUHQ ¬ true
else PENUHQ¬false
end;

---

Function KOSONGQ(q : antrian):boolean;
begin
If Q.banyak = 0 then KOSONGQ ¬ true
else KOSONGQ ¬ false
end;

---

Procedure ADDQ(data : tipeelemen; var q : antrian);
begin
If not PENUHQ(Q) then
begin

1. Q.banyak¬ Q.banyak+1
2. Q.elemen[Q.banyak] ¬ data

end
else
Tampilkan pesan kesalahan “Antrian Penuh”
end;

---

Procedure DELQ(var q : antrian; var data : typeelemen);
begin
If not KOSONGS(Q) then
begin

1. data ¬Q.elemen[1]
2. for i:= 2 to Q.banyak
   Q.elemen[i-1] ¬ Q.elemen[i]
3. Q.banyak ¬ Q.banyak- 1

end
else
Tampilkan pesan kesalahan “Antrian kosong”
End;

---

ke atas halaman

---

Dengan melihat implementasi di atas kita dapat merasakan adanya ketidakefisienan, yaitu bahwa untuk mengambil satu elemen dari queue kita harus menggeser sisa elemen yang sebenarnya tidak menjadi perhatian kita. Untuk data yang sedikit mungkin ini tidak terasa, tetapi untuk data yang banyak maka ketidakefisienan ini akan tampak jelas.
Untuk mengatasi permasalahan di atas kita dapat menggunakan implementasi queue berputar, yaitu dengan membiarkan sel tetap kosong bila elemen pada sel tersebut baru saja diambil. Bagaimanakah implementasi queue berputar? Perhatikan implementasi di bawah ini.

type antrian_putar= record
depan,belakang,banyak :0..maxelm;
elemen : array[1..maxelm] of typeelemen;
end;
Field depan dan belakang masing-masing adalah untuk mencatat lokasi elemen terdepan (yang akan diambil berikutnya) dan lokasi elemen paling belakang (elemen terakhir kali masuk)

---

Procedure ADDQ(data : tipeelemen; var q : antrian_putar);
begin
If not PENUHQ(Q) then
begin

1. Q.belakang ¬ (Q.belakang mod maxelm)+1
2. Q.elemen[Q.belakang] ¬ data

end
else
Tampilkan pesan kesalahan “Antrian Penuh”
end;

---

Procedure DELQ(var q : antrian_putar; var data : typeelemen);
begin
If not KOSONGS(Q) then
begin

1. data ¬ Q.elemen[Q.depan]
2. Q.banyak ¬ Q.banyak- 1
3. Q.depan ¬ (Q.depan mod maxelm)+1

end
else
Tampilkan pesan kesalahan “Antrian kosong”
End;

LinkedList

LinkedList

Introduction

The java.util.LinkedList class operations perform we can expect for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Class declaration

Following is the declaration for java.util.LinkedList class:

public class LinkedList<E>

   extends AbstractSequentialList<E>

      implements List<E>, Deque<E>, Cloneable, Serializable

Parameters

Following is the parameter for java.util.LinkedList class:

• E -- This is the type of elements held in this collection.

Field

Fields inherited from class java.util.AbstractList.

Class constructors

S.N.	Constructor & Description
1	LinkedList() This constructs constructs an empty list.
2	LinkedList(Collection<? extends E> c) This constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Class methods

S.N.	Method & Description
1	boolean add(E e) This method appends the specified element to the end of this list.
2	void add(int index, E element) This method inserts the specified element at the specified position in this list.
3	boolean addAll(Collection<? extends E> c) This method appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
4	boolean addAll(int index, Collection<? extends E> c) This method inserts all of the elements in the specified collection into this list, starting at the specified position.
5	void addFirst(E e) This method returns inserts the specified element at the beginning of this list..
6	void addLast(E e) This method returns appends the specified element to the end of this list.
7	void clear() This method removes all of the elements from this list.
8	Object clone() This method returns returns a shallow copy of this LinkedList.
9	boolean contains(Object o) This method returns true if this list contains the specified element.
10	Iterator<E> descendingIterator() This method returns an iterator over the elements in this deque in reverse sequential order.
11	E element() This method retrieves, but does not remove, the head (first element) of this list.
12	E get(int index) This method returns the element at the specified position in this list.
13	E getFirst() This method returns the first element in this list.
14	E getLast() This method returns the last element in this list.
15	int indexOf(Object o) This method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
16	int lastIndexOf(Object o) This method returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
17	ListIterator<E> listIterator(int index) This method returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
18	boolean offer(E e) This method adds the specified element as the tail (last element) of this list.
19	boolean offerFirst(E e) This method inserts the specified element at the front of this list.
20	boolean offerLast(E e) This method inserts the specified element at the end of this list.
21	E peek() This method retrieves, but does not remove, the head (first element) of this list.
22	E peekFirst() This method retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
23	E peekLast() This method retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
24	E poll() This method retrieves and removes the head (first element) of this list.
26	E pollFirst() This method retrieves and removes the first element of this list, or returns null if this list is empty.
27	E pollLast() This method retrieves and removes the last element of this list, or returns null if this list is empty.
28	E pop() This method pops an element from the stack represented by this list.
29	void push(E e) This method pushes an element onto the stack represented by this list.
30	E remove() This method retrieves and removes the head (first element) of this list.
31	E remove(int index) This method removes the element at the specified position in this list..
32	boolean remove(Object o) This method removes the first occurrence of the specified element from this list, if it is present.
33	E removeFirst() This method removes and returns the first element from this list.
34	boolean removeFirstOccurrence(Object o) This method removes the first occurrence of the specified element in this list (when traversing the list from head to tail).
35	E removeLast() This method removes and returns the last element from this list.
36	boolean removeLastOccurrence(Object o) This method removes the last occurrence of the specified element in this list (when traversing the list from head to tail).
37	E set(int index, E element) This method replaces the element at the specified position in this list with the specified element.
38	int size() This method returns the number of elements in this list.
39	Object[] toArray() This method returns an array containing all of the elements in this list in proper sequence (from first to last element).
40	<T> T[] toArray(T[] a) This method returns an array containing all of the elements in this list in proper sequence (from first to last element), the runtime type of the returned array is that of the specified array.

 Linked List
• Linked List adalah salah satu bentuk struktur
data, berisi kumpulan data (disebut node atau
simpul) biasanya dalam bentuk struct, yang
tersusun secara sekuensial dan saling
menyambung.
• Linked List sering disebut juga Senarai Berantai.
• Linked List diimplementasikan menggunakan
variabel pointer, sehingga cacah data yang
disimpan dapat bersifat dinamis.
Array VS Linked List Linked List
(Single Linked List Non-Circular - SLLNC)
Pengertian:
• Single: field pointer-nya hanya satu buah dan satu arah.
• Linked List: node-node tersebut saling terhubung satu sama
lain. Setiap node pada linked list mempunyai field yang berisi
pointer ke node berikutnya, dan juga memiliki field yang berisi
data.
• non Circular: pada akhir node maka pointernya menunjuk NULL,
digunakan sebagai kondisi berhenti saat membaca isi linked list.
Single Linked List non-Circular – deklarasi (1/3)
Contoh 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.
Single Linked List non-Circular – deklarasi (2/3)
• Menggunakan keyword new untuk
menyiapkan sebuah node baru berserta
alokasi memorinya, kemudian node ini
diisi data dan pointer nextnya menunjuk
ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Single Linked List non-Circular
deklarasi (3/3) - contoh program
SLLNC MENGGUNAKAN HEAD
inisialisasi (1/2)
• Dibutuhkan sebuah variabel pointer yaitu head (kepala)
• Head selalu menunjuk pada node pertama
• Manipulasi linked list tidak bisa dilakukan langsung ke
node yang dituju, harus menggunakan suatu pointer
penunjuk ke node pertama dalam linked list (disini adalah
head). Deklarasinya adalah: TNode *head;
SLLNC MENGGUNAKAN HEAD
inisialisasi (2/2)
Fungsi Inisialisasi Single LinkedList
void init(){
head = NULL;
}
Function untuk mengetahui kosong tidaknya Single LinkedList
Jika pointer head tidak menunjuk pada suatu node, maka data masih kosong
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}
SLLNC MENGGUNAKAN HEAD
menambah data di depan
Menambah data di depan
• Pada saat pertama kali (saat data masih
kosong), maka penambahan data dilakukan
dengan cara node head ditunjukkan ke node
baru tersebut.
• Untuk menambah data selanjutnya dengan cara
menambah node baru yang akan dikaitan di
node paling depan
• Prinsip mengkaitkan node baru dengan head,
kemudian head akan menunjuk pada data baru
tersebut sehingga head tetap menjadi data
terdepan.
SLLNC MENGGUNAKAN HEAD
menambah data di depan - ilustrasi
SLLNC MENGGUNAKAN HEAD
menambah data di depan - contoh program
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;
}
printf(”Data masuk\n”);
}
SLLNC MENGGUNAKAN HEAD
menambah data di belakang
Menambah data di belakang
• Pada saat pertama kali (saat data masih kosong), maka
penambahan data dilakukan dengan cara node head
ditunjukkan ke node baru tersebut.
• Untuk menambah data berikutnya, menambah data di
belakang lebih sulit karena butuh pointer bantu untuk
mengetahui node paling belakang. Selanjutnya pointer
bantu dikaitkan dengan node baru.
• Catatan untuk mengetahui data paling belakang perlu
digunakan proses perulangan.
SLLNC MENGGUNAKAN HEAD
menambah data di belakang – ilustrasi (1/2)
SLLNC MENGGUNAKAN HEAD
menambah data di belakang – ilustrasi (2/2)
SLLNC MENGGUNAKAN HEAD
menambah data di belakang - contoh program
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;
}
printf("Data masuk\n“);
}
SLLNC MENGGUNAKAN HEAD
menampilkan seluruh isi list
• Menampilkan seluruh isi list dengan cara menelusuri
linked list satu-persatu dari awal sampai akhir node
menggunakan pointer bantu.
• Catatan pointer head yang menjadi tanda awal linked
list tidak boleh berubah atau berganti posisi.
• Penelusuran dilakukan terus sampai dengan node
terakhir menunjuk ke nilai NULL. Jika tidak NULL, maka
node bantu akan berpindah ke node selanjutnya dan
membaca isi data menggunakan field next.
• Catatan jika head masih NULL berarti data masih
kosong.
SLLNC MENGGUNAKAN HEAD
menampilkan seluruh isi list - contoh program - ilustrasi
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<data<<" ";
bantu=bantu->next;
}
printf(“\n”);
} else printf(“Masih kosong\n“);
}
SLLNC MENGGUNAKAN HEAD
menghapus data pertama (terdepan)
• Menghapus node/data pertama (terdepan) yang
ditunjuk oleh head pada linked list.
• Menghapus node terdepan tidak boleh dilakukan jika
node sedang ditunjuk oleh pointer, sehingga harus
menggunakan pointer lain untuk menunjuk node yang
akan dihapus, contoh pointer hapus, kemudian
menghapus pointer hapus menggunakan perintah
delete.
• Catatan sebelum data terdepan dihapus, head harus
menunjuk ke node sesudahnya agar list tidak putus.
Head akan menunjuk ke node data terdepan yang baru.
• Jika head NULL maka berarti data telah kosong.
SLLNC MENGGUNAKAN HEAD
menghapus data pertama (terdepan) - contoh program - ilustrasi
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;
}
printf(“%d terhapus\n“,d);
} else cout<<"Masih kosong\n";
}
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang)
• Membutuhkan 2 pointer tambahan yaitu: pointer bantu
dan pointer hapus.
• Pointer hapus untuk menunjuk node yang akan dihapus.
• Pointer bantu untuk menunjuk node sebelum node yang
dihapus yang kemudian menjadi node terakhir.
• Pointer bantu selalu bergerak sampai sebelum node yang
akan dihapus, kemudian pointer hapus diletakkan setelah
pointer bantu. Selanjutnya pointer hapus akan dihapus,
sedangkan pointer bantu menunjuk ke NULL.
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang) - ilustrasi
SLLNC MENGGUNAKAN HEAD
menghapus data terakhir (paling belakang) – contoh program
Function untuk menghapus data paling 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;
}
printf(“%d terhapus\n“,d);
} else printf(“Masih kosong\n“);
}
SLLNC MENGGUNAKAN HEAD
menghapus semua data (semua elemen linked list) – contoh program
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;
}

ini adalah contoh yang berhasil aku buat.. mohon maaf bila syntax setelah diposting berubah:hehehehe

#include <conio.h>

#include <iostream.h>



struct TNode //deklarasi awal LINKED LIST

{

int data;

TNode *next;

};



TNode *head;



void init()

{

head = NULL;

}



int isEmpty()

{

if(head == NULL) return 1;

else return 0;

}



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<<endl;

cout<<" Data masuk...\n";

getch();

}



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<<endl;

cout<<" Data "<<d<<" terhapus...\n";

}

else

{

cout<<endl;

cout<<endl;

cout<<" Linked List Masih kosong...\n";

}

getch();

}



void search(int caridata)

{

TNode *bantu;

bantu = head;

int ketemu = 0;

int index=0;

if(isEmpty()==0)

{

while(bantu!=NULL)

{

bantu->data;



if (caridata == bantu->data)

{

cout<<endl;

cout<<" Data Ditemukan..."<<endl;

cout<<" Index Ke - "<<index;

ketemu = 1;

break;

}

bantu=bantu->next;

index++;



}

cout<<endl;

if (ketemu == 0)

cout<<" Data Tidak Ditemukan..."<<endl;



cout<<endl;

} else cout<<" Linked List Masih kosong...\n";

getch();

}



void tampil()

{

TNode *bantu;

bantu = head;

if(isEmpty()==0)

{



cout<<" Data Linked List"<<endl;

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



while(bantu!=NULL)

{

cout<<" --> "<<bantu->data<<" ";

bantu=bantu->next;

}

cout<<" --> NULL";

cout<<endl;

} else cout<<" Linked List Masih kosong...\n";

getch();

}



void main()

{

int pil,dataku,cari;

init(); //inisialisasi awal

do

{

clrscr();

cout<<" SINGLE LINKED LIST"<<endl;

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

cout<<" 1. Insert List"<<endl;

cout<<" 2. Delete Front"<<endl;

cout<<" 3. Show Linked List"<<endl;

cout<<" 4. Search Data"<<endl;

cout<<" 5. Exit"<<endl;

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

cout<<endl;

cout<<"Pilihan Anda = "; cin>>pil;



switch (pil)

{

case 1 :

cout<<endl;

cout<<" Insert Data --> "; cin>>dataku;

insertDepan(dataku);

break;

case 2 :

hapusDepan();

break;

case 3 :

cout<<endl;

cout<<endl;

tampil();

break;

case 4 :

cout<<endl;

cout<<" Data yg Dicari --> "; cin>>cari;

search(cari);

break;

};

}