Lalu, bagaimana implementasinya menggunakan Java, ketika Java tidak mengenal teknologi pointer? Dalam kenyataannya, kita dapat memperlakukan suatu objek sebagai pointer. Dengan demikian, struktur Node mungkin memiliki elemen data atau elemen-elemen lain yang merujuk ke Node lainnya. Node lain yang ditunjuk disebut sebagai simpul anak (child node), sedangkan Node itu sendiri disebut sebagai simpul induk (parent node). istilah child node dan parent node cukup penting dipahami secara mendalam karena akan sangat membantu kita mempelajari bahasan java selanjutnya.
Cara terbaik untuk memahami struktur data Node adalah menerapkannya secara langsung dengan program java. Node yang akan kita buat adalah Node anak (child node),
yang hanya memiliki satu pointer, dan selanjutnya akan kita gunakan
sebagai basis untuk membuat struktur-struktur data lainnya, terutama LinkedList dan DoublyLinkedList. Kode Java untuk Node kita adalah sebagai berikut :
Perhatikan kode pOneChild di atas lebih mendalam lagi, demikian halnya dengan isi definisi kelas pOneChildNodee bahwa sesungguhnya dalam bagian terbesar hanyalah merupakan metoda/fungsi set() dan get() biasa. Data/atribut yang dimiliki kelas pOneChildNode adalah data dan next. Atribut data tentu saja digunakan untuk menyimpan data pada Node itu sendiri, sedangkan atribut next menyimpan pointer ke Node berikutnya. Perhatikan pula bahwa next memiliki tipe data yang sama dengan nama kelasnya (perhatikan pernyataan protected pOneChildNode next;)
sehingga ia secara efektif menunjuk pada objek lain yang berasal dari
kelas yang sama. Hal inilah yang merupakan implementasi konsep pointer
pada Java dalam bentuk rujukan ke objek berikutnya.
Metode String toString() merupakan
metode standar yang dimiliki oleh Java untuk mencetak sesuatu. Jika
objek-objek akan dicetak dengan cara lain, metoda toString() akan
didefinisikan dengan perintah-perintah lain yang berkaitan dengan
bagaimana caranya mencetak objek yang bersangkutan. Dalam kasus ini,
kita hanya ingin menyimpan nilai data. Penambahan data dengan tanda
kutip secara otomatis akan mengkonversikannya menjadi bertipe String, dengan harapan data kita juga akan memiliki metoda toString() yang didefinisikan di dalamnya. Tanpa metoda toString() tersebut, kita tidak akan memperoleh representasi nyata atribut data milik kelas Node ini.
Struktur data berbasis Node (kelas pOneChildNode)
tersebut memungkinkan kita melakukan penambahan/penyisipan elemen
secara dinamis, begitu pula dengan pengurangan/penghapusan elemen secara
dinamirs, yang merupakan kunci bagi banyak algoritma yang kompleks saat
ini. Sekarang ini, setelah kita tahu bagaimana caranya
mengimplementasikan Node dalam java, kita akan menggunakannya untuk
mengimplementasikan salah satu List (LinkedList ataupun DoublyLinkedList).
Banyak program aplikasi melandaskan dirinya pada LinkedList sebagai tempat penyimpanannya. Sebagai contoh, ArrayList yang diimplementasikan menggunakan LinkedList, sehingga ukurannya dapat bertambah dan berkurang secara dinamis. Dengan demikian, ukuran ArrayList, termasuk struktur-struktur data lain yang berbasis pada LinkedList, dapat bertambah dengan cara yang hampir-hampir tak terbatas, setara dengan kapasitas memori komputer yang digunakan.
ADT LinkedList sesungguhnya hanyalah suatu Node kelas pOneChildNode, dengan karakteristik tertentu sedemikian rupa sehingga Node tersebut memiliki kaitan (link) terhadap Node yang mengikutinya (Perhatikan gambar 1.1)
Gambar 1.1 LinkedList (Senarai Berkait)
Dengan demikian, suatu LinkedList dapat dirujuk dari salah satu Node, dimana Node yang pertama biasanya dirujuk sebagai Head (kepala) dari List, sedangkan Node yang terakhir pada LinkedList, yang berupa untaian Node, yang sering dinamakan sebagai Tail,
biasanya memiliki fitur khusus yang memungkinkan program Java yang akan
kita buat bisa mengetahuinya. Fitur khusus untuk Tail ini pada umumnya
adalah nilai null pada atribut/data next, sedangkan fitur khusus dari Head adalah objek pertama dalam List, yang tersimpan dalam atribut/data next. Selanjutnya, dalam contoh program Java dibawah ini, kita akan membuat suatu LinkedList yang basisnya adalah pada kode Java untuk Node (kelas pOneChildNode).
public class SinglyLingkedListClass {
protected pOneChildNode head;
protected int number;
//konstruktor
public SinglyLingkedListClass(){
head = null;
number = 0;
}
/*metoda untuk menentukan
* Linked listberisi atau kosong
*/
public boolean isEmpty(){
return head == null;
}
/*
* Metoda untuk menentukan banyak
* Node yang ada di dalam LinkedList
*/
public int size(){
return number;
}
/*
* Metoda untuk menambahkan Node baru
* di bagian awal LinkedList
*/
public void insert(Object o){
head = new pOneChildNode(o, head);
number++;
}
/*
* Metoda untuk menghapus Node
* di bagian awal LinkedList
*/
public Object remove(){
if(isEmpty())
return null;
pOneChildNode tmp = head;
head = tmp.getNext();
number--;
return tmp.getData();
}
/*
* Metoda untuk menambahkan Node
* di bagian Akhir LinkedList
*/
public void insertEnd(Object obj){
if(isEmpty())
insert(obj);
else{
pOneChildNode t = head;
while(t.getNext() != null)
t = t.getNext();
pOneChildNode tmp = new pOneChildNode(obj, t.getNext());
t.setNext(tmp);
number++;
}
}
/*
* Metoda untuk menghapus Node
* di bagian akhir LinkedList
*/
public Object removeEnd(){
//Jika LinkedList Kosong
if (isEmpty())
return null;
//jika LinkedList hanya berisi satu node
if(head.getNext() == null)
return remove();
pOneChildNode t = head;
//perulangan menuju Node terakhir
while(t.getNext().getNext() != null)
t = t.getNext();
//mengambil data dari node yang akan dihapus
Object obj = t.getNext().getData();
/*
* Melakukan pengaturan sehingga
* parent node untuk node yang akan dihapus
* bernilai Null
*/
t.setNext(t.getNext().getNext());
//mengurangi ukuran LinkedList
number--;
//mengembalikan nilai Node
//ke metoda pemanggil
return obj;
}
/*
* Metoda untuk mengambil nilai data di Node
* (tanpa menghapusnya)
*/
public Object peek(int n){
pOneChildNode t = head;
for(int i=0; i<="" t="">
Pengujian merupakan hal yang mutlak dilakukan pada langkah terakhir, segera setelah kita dapat mengimplementasikan berbagai metoda yang penting di atas. Dengan logika seperti itu, kita membuat kelas SinglyLinked berikut ini untuk melakukan pengujian. dan untuk lebih memahaminya, perhatikan juga hasilnya di gambar 1.2
t = t.getNext();
return t.getData();
}
}
Kita dapat temukan definisi untuk dua komponen Head dan number pada uraian yang terlihat dalam kode-kode di atas. Head merupakan Node yang pertama dalam LinkedList, sedangkan number merupakan jumlah keseluruhan Node yang ada dalam LinkedList. number terutama digunakan untuk metoda size(). Dalam hal ini, konstruktor SinglyLinkedListClass digunakan untuk melakukan inisialisasi. Metoda-metoda size() dan isEmpty() juga relatif mudah difahami. Selanjutnya, yang merupakan metoda-metoda yang cukup sulit adalah metoda-metoda insert(), yang bermanfaat untuk menyisipkan suatu objek tertentu dalam LinkedList, dan remove(), yang bermanfaat untuk menghapus suatu objek tertentu dari LinkedList.
Untuk penjelasan metoda-metoda utama dalam kelas SinglyLinkedListClass tersebut adalah sebagai berikut :
- Metoda insert(Object) membuat suatu objek dari kelas pOneChildNode baru dengan pointer next objek yang baru tersebut menunjuk ke head saat ini, kemudian data merupakan nilai data nyata yang akan disisipkan ke dalam LinkedList. Selanjutnya, metoda insert(Object) akan melakukan pengaturan sedemikian rupa sehingga simpul head menunjuk pada simpul (Node) yang baru tersebut (perhatikan pernyataan Head = new pOneChildNode(obj, head);). Jika kita memikirkan algoritma/logika pemrogramannya, kita dapat melihat bahwa head tetap tersimpan dalam LinkedList, sementara Node yang baru akan menunjuk padanya, sehingga dapat kita simpulkan bahwa penambahan Node akan dilakukan pada bagian depan LinkedList.
- Dalam hal di atas, metoda Object remove() bekerja dengan
logika serupa, tetapi dalam upaya melakukan penyisipan, ia melakukan
penghapusan. Untuk melakukan tugasnya, metoda Object remove() pertama kali memanggil metoda isEmpty() untuk melihat apakah LinkedList sedang kosong atau berisi. Kemudian, jika LinkedList tersebut berisi, dalam hal ini head tidak bernilai null, metoda Object remove() akan menyimpan Node Head saat ini, lalu kemudian mengubahnya untuk mengakomodasi penghapusan ( perhatikan perintah pOneChildNode tmp = head; dan head = tmp.getNext();),
mengurangi nilai number, dan kemudian mengembalikan data dari Node yang
sebelumnya tersimpan. Adapun logika penghapusan yang terutama adalah
dengan melakukan pengaturan sedemikian rupa sehingga Node head bergeser
ke Node anaknya, sehingga dengan demikian dapat disimpulkan bahwa metoda Object(remove) tersebut melakukan penghapusan untuk Node yang berada di bagian awal LinkedList (Node yang ada segera setelah head).
Perhatikan bahwa dalam Java kita tidak perlu secara eksplisit melakukan pelenyapan Node yang dihapus dari memori komputer, dimana hal ini, dalam bahasa-bahasa pemrograman lain kadang perlu dilakukan (biasanya menggunakan metoda destruktor yang merupakan lawan dari metoda konstruktor). Dalam Java, pelenyapan Node yang dihapus secara otomatis akan dilakukan oleh suatu fiturnya yang dinamakan garbage collections sehingga memori yang digunakan oleh Node yang dihapus itu bisa langsung dimanfaatkan oleh aplikasi/program lainnya, tanpa intervensi apapun dari pemrogram.
Dalam metoda insertEnd(Object), kita melakukan penyisipan pada bagian akhir LinkedList. Pertama kali, metoda insertEnd(Object) juga menggunakan metoda isEmpty() untuk menentukan apakah LinkedList berisi atau kosong (Head bernilai null), dan jika kosong metoda insertEnd(Object) akan melakukan penyisipan secara reguler. Hal ini terjadi karena kita tidak perlu menentukan akhir dari LinkedList saat Linked List tersebut kosong. Jika LinkedList berisi (Head tidak bernilai null), metoda insertEnd(Object) akan melakukan perulangan (iterasi) menggunakan perintah (while(t.getNext() != null) (t=t.getNext();) sedemikian rupa untuk menentukan akhir LinkedList yang ditentukan dengan memeriksa apakah pointer next berisi null atau tidak.
Saat metoda insertEnd(Object) yakin bahwa ia sudah berada di Node yang terakhir, ia kemudian akan membuat Node yang baru, kemudian menyisipkan Node yang baru tersebut di akhir LinkedList menggunakan perintah pOneChildNode tmp = new pOneChildNode(obj,t.getNext()); dan perintah t.setNext(tmp);. Selanjutnya, metoda insertEnd(Object) juga melakukan penyesuaian terhadap nilai number yang merupakan objek yang menyimpan nilai ukuran LinkedList. - Metoda Object removeEnd() bekerja dengan cara serupa dengan metoda insertEnd(Object). Metoda Object removeEnd() juga harus melintasi keseluruhan LinkedList untuk mencari Node yang terakhir. Awalnya, metoda Object removeEnd() juga memeriksa apakah LinkedList berisi atau kosong menggunakan metoda isEmpty(). Selanjutnya, metoda Object removeEnd() juga melakukan pemeriksaan untuk melihat apakah hanya ada satu Node dalam LinkedList. jika memang demikian, maka metoda Object removeEnd() akan melakukan penghapusan reguler menggunakan metoda remove(). Kemudian jika Node yang akan dihapus bukan satu-satunya Node dalam LinkedList, metoda Object removeEnd() akan melakukan perulangan (iterasi) sedemikian rupa untuk mengetahui Node mana yang sesungguhnya merupakan Node terakhir.
Sangatlah penting untuk mengerti bahwa ketika sudah mendapatkan Node yang terakhir, kita tidak dapat begitu saja menghapusnya, sesungguhnya kita memerlukan informasi tentang Node induk dari Node yang terakhir ini (Perhatikan perintah dalam metoda Object removeEnd() yang tertulis sebagai : t.setNext(t.getNext.getNext());), dimana perintah ini juga berarti bahwa Node induk di atur sedemikian rupa hingga berubah identitas menjadi Node yang terakhir. Saat kita dapat menemukan Node yang terakhir tersebut, kita mengambil data-nya, melakukan pengaturan ulang LingkedList menggunakan perintah t.setNext(t.getNext().getNext());, dan kemudian mengembalikan data ke bagian program lainnya yang memanggil metoda Object removeEnd() ini. Perhatikan kembali bahwa dalam Java, kita tidak perlu secara eksplisit melakukan pelenyapan (destroy) Node yang dihapus.
Metoda Object peek(int) secara sederhana akan melakukan penelusuran terhadap LinkedList hingga dapat menemukan elemen yang dicari (atau mungkin suatu saat menemukan akhir LinkedList). Saat metoda Object peek() mencapai akhir LinkedList, ia seharusnya mendapatkan nilai null, jika tidak, metoda Object peek() akan mengembalikan data yang benar dalam LinkedList menggunakan perintah return t.getData();.
Pengujian merupakan hal yang mutlak dilakukan pada langkah terakhir, segera setelah kita dapat mengimplementasikan berbagai metoda yang penting di atas. Dengan logika seperti itu, kita membuat kelas SinglyLinked berikut ini untuk melakukan pengujian. dan untuk lebih memahaminya, perhatikan juga hasilnya di gambar 1.2
package singlylinked;
import java.io.*;
import ClassSingly.SinglyLingkedListClass;
/**
*
* @author saddam
*/
public class SinglyLinked {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//menginstanisasi pLinkedList
SinglyLingkedListClass s1 = new SinglyLingkedListClass() ;
Integer j = null;
int i;
System.out.println("starting. . .");
for(int x=0; x<4; x++){
//membuat bilangan-bilangan acak
j = new Integer((int)(Math.random()*100));
/*
* menyisipkan bilangan-bilangan bulat
* acak di depan list
*/
s1.insert(j);
System.out.println("Insert : "+j);
}
for(int x=0; x<4; x++){
//membuat bilangan-bilangan acak
j = new Integer((int)(Math.random()*100));
/*
* menyisipkan bilangan-bilangan bulat
* acak di belakang list
*/
s1.insertEnd(j);
System.out.println("InsertEnd : "+j);
}
/*
* menampilkan bilangan-bilangan bulat
* (tanpa menghapusnya)
*/
for(int x=0; x<="">
System.out.println("peek "+x+" : "+s1.peek(x));
}
/*
* menampilkan bilangan-bilangan bulat
* di depan list
* (sekaligus menghapusnya
*/
for(i=0; i<5; i++)
System.out.println("remove : "+((Integer)s1.remove()));
/*
* Menampilkan bilangan-bilangan bulat
* di belakang list
* (sekaligus menghapusnya
*/
while(!s1.isEmpty())
System.out.println("removeEnd : "+((Integer)s1.removeEnd()));
System.out.println("Done. . .:D");
}
}
Gambar 1.2 Hasil dari program SinglyLinked
Tidak ada komentar:
Posting Komentar