Linked List
Hello, World!
I know it must be a bit boring for you guys to see me writing stuffs about programming each week. But, what can I say when writing article about programming has been the task given by my lecturer. Anyway, today's article will mostly talk about Linked List and will be written in bahasa. For those who seek the material in english, please click the links that i've included down below the article.
Linked List
Linked List adalah struktur data yang menyimpan data dalam bentuk linear, dimana tiap-tiap data direpresentasikan oleh node-node yang membentuk sekuens secara berurutan. Pada dasarnya, satu node dalam linked list terdiri dari:
- Data yang disimpan, dan
- Referensi (link) kepada node selanjutnya
Efisiensi Linked-List
Penyisipan dan penghapusan pada linked list memiliki kecepatan yang tinggi. Kedua perintah ini hanya melibatkan satu atau dua referensi, sehingga hanya membutuhkan waktu sebesar O(1).
Operasi pencarian, penghapusan, dan penyisipan sebuah elemen atau data di samping elemen tertentu secara spesifik membutuhkan pencarian menyeluruh, yang mana sekitar setengah dari seluruh data pada rata-rata kasus. Operasi ini membutuhkan waktu sebesar O(N) yang mana sebanding dengan operasi pada array. Namun, operasi pada linked list tersebut tetap lebih cepat karena tidak ada elemen atau data yang perlu dipindahkan ketika sebuah elemen dihapus atau disisipkan
Kelebihan lainnya dari penggunaan linked list adalah linked list menggunakan memori secukupnya persis sesuai dengan yang dibutuhkan dan dapat diperbesar hingga memenuhi semua memori yang tersedia. Pada sisi lainnya, ukuran dari sebuah array sudah ditetapkan ketika dibuat yang mana kemudian menimbulkan masalah karena apabila terlalu kecil maka akan menyebabkan segmentation fault sedangkan ketika terlalu besar maka program menjadi tidak efisien.
Sorted List
Sorted List adalah sebuah linked list dengan elemen atau data yang sudah tersusun sesuai dengan tingkatan nilainya. Operasi penghapusan biasanya terbatas pada penghapusan elemen terkecil (atau terbesar) dalam sebuah list, yang mana terletak pada awal list, namun terkadang metode find() dan delete(), yang mana mencari pada keseluruhan list untuk menemukan posisi tertentu, tetap digunakan.
Efisiensi Sorted List
Kelebihan dari sorted list dibanding array adalah kecepatan dalam operasi penyisipan (karena elemennya tidak perlu dipindah) dan fakta bahwa sebuah list dapat diperbesar untuk mengisi memori yang tersedia, sedangkan ukuran array terbatas pada ukuran yang sudah ditentukan sebelumnya. Meskipun begitu, sorted list lebih susah diimplementasikan dibanding dengan sorted array.
Penyisipan dan penghapusan elemen pada sorted list membutuhkan waktu sebesar O(N) yang mana lebih besar dibanding linked list biasa yang hanya membutuhkan O(N/2). Hal ini terjadi karena lokasi yang tepat harus dicari dengan melakukan iterasi pada keseluruhan list. Namun, nilai minimum dapat ditemukan dan dihapus dalam waktu O(1) karena sudah pasti terletak pada awalan list. Apabila pengaplikasian program sering kali mengakses nilai minimum dan kecepatan penyisipan bukanlah suatu hal yang penting, maka sorted linked list merupakan pilihan yang efektif.
Doubly Linked List
Kelebihan dari doubly linked list adalah pada linked list biasa, sulit untuk mengakses elemen sebelumnya. Pada linked list biasa, program harus mulai kembali dari awal kemudian melakukan operasi traversal sampai elemen sebelum data yang sedang diakses sekarang. Namun, doubly linked list memungkinkan program untuk langsung bergerak ke belakang maupun ke depan. Rahasianya terletak pada fakta bahwa list tersebut menyimpan dua referensi link. Referensi pertama mengarah ke link berikutnya, sama seperti linked list biasa. Referensi kedua mengarah ke link sebelumnya.
Kekurangan dari doubly linked list adalah pada saat melakukan operasi penghapusan atau penyisipan, sebuah program harus berurusan dengan 4 link, bukan hanya 2 seperti linked list biasa: 2 link yang terhubung pada data sebelumnya dan 2 link yang terhubung pada elemen berikutnya. Selain itu, setiap link pada doubly linked list juga membutuhkan memori yang lebih besar karena adanya tambahan referensi tersebut.
Implementasi Linked List pada Java
| import java.util.LinkedList; | |
| import java.util.Scanner; | |
| import java.util.InputMismatchException; | |
| public class JavaLinkedList | |
| { | |
| private static LinkedList<String> dataStorage = new LinkedList<String>(); | |
| private static Scanner extracted(){ | |
| return new Scanner(System.in); | |
| } | |
| private static void displayData(){ | |
| System.out.println("\nData dalam List: " + dataStorage); | |
| System.out.println("Total Data :" + dataStorage.size()); | |
| } | |
| private static void addData(){ | |
| System.out.print("Masukkan Data: "); | |
| String tempData = extracted().nextLine(); | |
| dataStorage.add(tempData); | |
| displayData(); | |
| } | |
| private static void addDataToFirst(){ | |
| System.out.print("Masukkan Data: "); | |
| String tempData = extracted().nextLine(); | |
| dataStorage.addFirst(tempData); | |
| displayData(); | |
| } | |
| private static void addDataToLast(){ | |
| System.out.print("Masukkan Data: "); | |
| String tempData = extracted().nextLine(); | |
| dataStorage.addLast(tempData); | |
| displayData(); | |
| } | |
| private static void addDataAtLocation(){ | |
| boolean status = true; | |
| int indexData = 0; | |
| displayData(); | |
| while(status){ | |
| System.out.print("Pilih Index Data yang ingin disisipi data : [0-" + (dataStorage.size()-1) + "]: "); | |
| try{ | |
| status = false; | |
| indexData = extracted().nextInt(); | |
| } | |
| catch(InputMismatchException e) { | |
| System.out.println("Data harus berupa Angka!"); | |
| status = true; | |
| } | |
| } | |
| System.out.print("Data yang ingin disisipkan pada index data ke-" + indexData + ": "); | |
| String tempData = extracted().nextLine(); | |
| dataStorage.add(indexData, tempData); | |
| displayData(); | |
| } | |
| private static boolean searchData(String data){ | |
| return dataStorage.contains(data); | |
| } | |
| private static void removeData() { | |
| boolean status = true; | |
| int indexData = 0; | |
| displayData(); | |
| while(status){ | |
| System.out.print("Pilih Index Data yang ingin dihapus: [0-" + (dataStorage.size() - 1) + "]: "); | |
| try{ | |
| status = false; | |
| indexData = extracted().nextInt(); | |
| } | |
| catch(InputMismatchException e){ | |
| System.out.println("Data harus berupa Angka!"); | |
| status = true; | |
| } | |
| } | |
| dataStorage.remove(indexData); | |
| displayData(); | |
| } | |
| private static void removeDataAtFirst() { | |
| dataStorage.removeFirst(); | |
| displayData(); | |
| } | |
| private static void removeDataAtLast() { | |
| dataStorage.removeLast(); | |
| displayData(); | |
| } | |
| private static void removeDataByContent() { | |
| displayData(); | |
| System.out.print("Masukkan Data yang ingin dihapus: "); | |
| String data = extracted().nextLine(); | |
| if(searchData(data)) { | |
| dataStorage.remove(data); | |
| } | |
| else { | |
| System.out.println("Anda memasukkan data yang tidak tersimpan di dalam list"); | |
| } | |
| displayData(); | |
| } | |
| private static void programExit() { | |
| System.exit(0); | |
| } | |
| private static void programTitle() { | |
| System.out.println("\nSimple Linked List Program" + "\nDitulis dalam bahasa pemrograman Java" | |
| + "\nOleh : Angela Oryza Prabowo"); | |
| } | |
| private static void programSwitcher() { | |
| boolean status = true; | |
| int indexMenu = 0; | |
| while(status) { | |
| try{ | |
| status = false; | |
| System.out.print("Pilih Menu [1~9]: "); | |
| indexMenu = extracted().nextInt(); | |
| } | |
| catch(InputMismatchException e) { | |
| System.out.println("Masukan harus berupa Angka!"); | |
| } | |
| } | |
| switch(indexMenu) { | |
| case 1: addData(); break; | |
| case 2: addDataToFirst(); break; | |
| case 3: addDataToLast(); break; | |
| case 4: addDataAtLocation(); break; | |
| case 5: removeData(); break; | |
| case 6: removeDataAtFirst(); break; | |
| case 7: removeDataAtLast(); break; | |
| case 8: removeDataByContent(); break; | |
| case 9: programTitle(); break; | |
| case 10: programExit(); break; | |
| } | |
| programMenu(); | |
| } | |
| private static void programMenu() { | |
| System.out.println("\n. PROGRAM MENU : ." | |
| + "\n 1. Add Data" | |
| + "\n 2. Add Data at First" | |
| + "\n 3. Add Data at Last" | |
| + "\n 4. Add Data at N Index" | |
| + "\n 5. Remove Data at N Index" | |
| + "\n 6. Remove Data at First" | |
| + "\n 7. Remove Data at Last" | |
| + "\n 8. Remove Data by Data Content" | |
| + "\n 9. About Program" | |
| + "\n 10. Program Exit"); | |
| programSwitcher(); | |
| } | |
| public static void main(String[] args){ | |
| programTitle(); | |
| programMenu(); | |
| } | |
| } |
Comments
Post a Comment