Algoritma dan Struktur Data : List dan ADT List
Singly Linked List
Kelas MyNode
Kelas pertama yang akan kita buat adalah kelas MyNode. Kelas ini merepresentasikan sebuah node dalam Singly Linked List kita.
Hal yang perlu diperhatikan pada kode kelas MyNode di atas adalah tipe data dari atribut info. Atribut info tersebut memiliki tipe data Object. Apa alasannya? Alasannya adalah agar Linked List ini dapat menyimpan objek dari kelas apapun . Hal ini dapat dilakukan karena Object adalah superclass dari semua kelas di Java (termasuk kelas yang kita definisikan sendiri). Bila anda lupa mengenai kelas Object ini, anda dapat me-review-nya kembali pada bahan polymorphism.
Efek lain dari penggunaan Object sebagai tipe data dari atribut info adalah atribut info hanya dapat menyimpan tipe reference. Sebagai contoh, info dapat menyimpan objek-objek dari kelas Integer,Float,String, Array,String dan lain-lain karena mereka merupakan tipe reference. Namun atribut info tidak dapat menyimpan tipe-tipe primitif seperti int, float,char, boolean, dan tipe-tipe primitif lainnya. Penjelasan lebih lanjut mengenai hal ini akan diberikan pada saat kita mulai membuat kelas Tester.
Kelas MyLinkedList dan Tester
Setelah kita membuat kelas MyNode, kita akan membuat kelas MyLinkedList yang merepresentasikan sebuah Singly Linked List. Karena ada banyak method yang perlu diuji, maka flow dari modul ini akan dibuat sebagai berikut :
- Implementasikan sebuah method kelas MyLinkedList
- Uji method-method tersebut dengan menggunakan kelas Tester
- Kembali ke langkah pertama
Kerangka awal dari kelas MyLinkedList adalah sebelum kita menambahkan method apapun adalah sebagai berikut :
addLast dan printAllInfo
Buatlah sebuah method dengan nama addFirst yang akan berfungsi untuk menyisipkan sebuah node pada akhir dari list. Header dari method ini adalah :
public void addLast(Object info)
Berikut ini adalah potongan kode dari method addLast :
Method public void printAllInfo berfungsi untuk mengeluarkan semua info yang ada pada nodenode linked list ini dimulai dari node head sampai dengan node terakhir. Implementasi dari method ini adalah sebagai berikut :
Pengujian method addLast dan printAllInfo pada kelas Tester
Kita akan menguji method-method tersebut dengan memanggilnya pada kelas Tester. Di bawah ini adalah contoh tester sederhana yang akan menyimpan 3 buah bilangan bulat dalam list dan mengeluarkan isi dari list tersebut :
Bila method addLast dan printAllInfo anda sudah benar maka keluaran dari Tester ini adalah :
5 2 3
Anda akan perlu menguji method-method lainnya yang akan kita implementasikan dengan cara yang sama. Anda dapat menggunakan printAllInfo untuk melihat isi dari list pada saat ini.
Perhatikan kembali bahwa MyLinkedList hanya dapat menyimpan info-info yang bertipe reference dan addLast memiliki parameter masukan bertipe Object. Oleh karena itu, untuk menyimpan bilangan bulat “1” dalam list, kita tidak dapat menyimpannya sebagai tipe primitif int. Kita perlu menyimpannya dalam sebuah objek dari kelas Integer. Itulah sebabnya mengapa parameter dari addLast pada tester di atas adalah new Integer(…).
Salah satu pertanyaan yang sering muncul pada tahap ini adalah “kalau begitu, kenapa kalau saya ganti jadi myLL.addLast(1) dia tetap jalan dengan baik dan tidak ada compilation error?”
Alasannya adalah karena Java memiliki fitur yang disebut auto boxing (anda dapat mencari penjelasan lebih lengkap mengenai fitur ini di internet). Fitur ini akan mengubah secara otomatis tipe-tipe primitif menjadi tipe wrapper-nya bila dibutuhkan. Dalam kasus ini, berarti Java akan secara otomatis mengubah statement myLL.addLast(1) menjadi myLL.addLast(new Integer(1));
addFirst
Buatlah sebuah method dengan header :
public void addFirst(Object info)
yang akan berfungsi untuk menyisipkan sebuah node pada awal list. Setelah itu modifikasilah Tester yang telah anda gunakan sebelumnya untuk memastikan bahwa implementasi anda sudah benar. Pengujian anda perlu untuk mencoba kasus-kasus di bawah ini :
- addFirst pada saat list masih kosong
- addFirst pada saat list sudah memiliki isi
- pemanggilan addFirst dan addLast secara bergantian
removeFirst
Method removeFirst berfungsi untuk menghapus elemen pertama dari list dan mengembalikan info dari elemen yang dihapus tersebut. Bila list kosong maka method ini tidak akan melakukan apa-apa dan akan mengembalikan nilai null. Method ini memiliki header :
public Object removeFirst()
Di bawah ini adalah potongan kode yang mengimplementasikan method removeFirst :
Kita akan menguji method removeFirst dengan cara memasukkan 3 buah bilangan bulat ke dalam list. Setelah kita akan menghapus node pertamanya dan menampilkan info dari node yang dihapus tersebut. Berikut ini adalah Tester yang menguji hal tersebut :
Hal yang perlu diperhatikan pada Tester ini adalah mengenai tipe kembalian dari method removeFirst. Kembalian dari method ini bertipe Object, namun karena kita tahu bahwa objek yang kita simpan dalam List tersebut adalah objek-objek dari kelas Integer, maka kita dapat meng-cast objek dari kelas Object tersebut ke kelas Integer.
Mengapa kita perlu melakukan casting? Karena biasanya kita tidak dapat memproses info tersebut (dalam kasus ini adalah objek-objek Integer) bila dia masih dianggap sebagai kelas Object. Sebagai contoh, objek dari kelas Object tidak dapat kita operasikan dengan operasi aritmatika. Contoh di atas menunjukkan bahwa setelah kita cast infonya ke tipe aslinya, kita dapat melakukan operasi-operasi yang kita inginkan terhadap info tersebut.
removeLast
Buatlah sebuah method dengan header :
public Object removeLast()
Berfungsi untuk menghapus node terakhir dari list dan mengembalikan info dari node yang dihapus tersebut. Bila list dalam kondisi kosong maka method ini akan mengembalikan nilai null.
getNode
Tambahkanlah method dengan header :
public void MyNode getNode(int index)
Berfungsi untuk mengembalikan node pada index tersebut. Index 0 akan mengacu pada elemen pertama dari list. Method ini akan mengembalikan null bila tidak ada node pada index tersebut. Pastikan bahwa method ini sudah berjalan dengan benar sebelum anda mengerjakan nomor selanjutnya.
get
Tambahkanlah method dengan header :
public void Object get(int index)
Berfungsi untuk mengembalikan info dari node pada index tersebut. Index 0 akan mengacu pada elemen pertama dari list. Method ini akan mengembalikan null bila tidak ada node pada index tersebut.
size
Buatlah sebuah method dengan nama size yang berfungsi untuk mengeluarkan jumlah elemen yang ada dalam list pada saat ini. Header dari method size adalah :
public int size()
addAfter
Buatlah sebuah method dengan nama addAfter yang berfungsi untuk menyisipkan sebuah node baru pada posisi setelah sebuah node lain yang sudah ada dalam list (prevNode). Header dari method ini adalah sebagai berikut :
public void addAfter(MyNode prevNode,Object info)
Contoh implementasi dari method ini adalah sebagai berikut :
Kita dapat menguji method ini dengan bantuan method getNode yang telah kita buat sebelumnya. Berikut ini adalah potongan kode untuk menguji method ini.
Bila addAfter telah bekerja dengan benar, maka addAfter yang pertama akan menyisipkan sebuah node dengan info bernilai 1 setelah node pertama. Oleh karena itu printAllInfo akan mengeluarkan :
5 1 2 3
AddAfter yang kedua akan menyisipkan node dengan nilai 10 setelah node kedua, sehingga hasil akhirnya adalah:
5 1 10 2 3
removeAfter
Method removeAfter berfungsi untuk menghapus node yang terletak setelah sebuah node lainnya dalam list(prevNode). Method ini akan mengembalikan info dari node yang dihapus tersebut. Bila tidak ada node yang dapat dihapus maka method ini akan mengembalikan nilai null. Header dari method ini adalah public void removeAfter(MyNode prevNode)
Contoh Penggunaan Kelas-Kelas List Dinamis Pada Java
Kelas Vector dan ArrayList
Kelas Vector dan ArrayList memiliki cara penggunaan yang sangat mirip. Hal ini disebabkan karena kedua kelas ini merupakan subclass dari kelas abstrak yang sama yaitu kelas AbstractList. Contoh yang akan ditunjukan di bawah ini tidak menggunakan generics (penjelasan mengenai generics ada di luar lingkup dari modul ini) oleh karena itu objek yang disimpan akan berupa objek-objek dari kelas Object. Beberapa method-method yang sering digunakan di kedua kelas ini adalah :
- public int size() : mengembalikan jumlah elemen yang sudah tersimpan dalam list.
- public void add(Object obj) : memasukkan obj ke akhir list.
- public void add(int index, Object obj) : menyisipkan obj pada posisi index dari list.
- public Object remove(int index) : menghapus objek pada posisi index dari list dan mengembalikan objek yang dihapus tersebut.
- public Object get(int index) : mengembalikan objek yang disimpan pada posisi index.
- public void set(int index,Object obj) : menyimpan obj ke dalam list pada posisi index. method ini akan menimpa objek yang sebelumnya tersimpan pada posisi tersebut.
Nilai parameter “index” yang valid pada method-method di atas adalah dari 0 sampai jumlahElemen-1 (inklusif). Pada saat baru diinstansiasi, jumlah elemen yang tersimpan adalah 0. Jumlah elemen akan bertambah tiap kali kita memanggil method-method add dan akan berkurang pada saat kita memanggil method-method remove.
Untuk dapat menggunakan kelas Vector anda akan perlu untuk mengimport java.util.Vector. sedangkan untuk menggunakan kelas ArrayList anda perlu mengimport java.util.ArrayList.
Berikut ini adalah contoh penggunaan kelas Vector :
Karena cara penggunaan ArrayList persis sama seperti cara penggunaan Vector, maka anda dapat mengubah contoh di atas agar menggunakan ArrayList hanya dengan mengganti tipe data dari objList serta kelas yang diinstansiasinya (dari new Vector menjadi new ArrayList).
Kelas LinkedList
Kelas LinkedList juga merupakan subclass dari kelas AbstractList walaupun tidak secara langsung. Oleh karena itu, method-method Vector dan ArrayList yang ditulis sebelumnya juga dimiliki oleh kelas LinkedList. Perbedaannya adalah bahwa kelas LinkedList juga memiliki beberapa methodmethod tambahan yang tidak dimiliki oleh Vector maupun ArrayList. Untuk dapat menggunakan kelas LinkedList anda akan perlu untuk mengimport java.util.LinkedList.
Berikut ini adalah beberapa method-method penting pada kelas LinkedList yang tidak ada pada Vector maupun ArrayList
- addFirst
- addLast
- removeFirst
- removeLast
- peek
Bacalah javadoc dari kelas LinkedList untuk memahami fungsi dari method-method di atas. Pastikan bahwa anda mengerti perbedaan antara removeFirst dan peek.
Berikut ini adalah contoh penggunaan kelas LinkedList :
Sumber
Modul ASD : ADT List
Posting Komentar