Linked List in Java

Halo Arek Blodhil! bertemu lagi pada hari ini kita akan membahas... yap betul Linked List!

Untuk Penjelasannya aku akan mengambil langsung dari Tutorial: (Struktur Data) Implementasi Single Linked List sederhana dengan Java – UNYDeveloperNetwork dengan code yang saya modifikasi sedikit ya! 😅 maka full credit kepada unydevelopernetwork.com

Apakah itu Single Linked List?

Dalam ilmu komputer, linked list dapat didefinisikan sebagai koleksi linear dari elemen – elemen data. Penempatan elemen – elemen data ini acak di dalam memori, namun antar elemen data ini terhubung dengan node. Jadi satu node dalam suatu elemen data akan menunjuk ke node elemen data lain melalui suatu penunjuk yang umumnya disebut pointer. Jadi dapat disimpulkan, sebuah koleksi data disebut sebagai Linked List apabila antar data tersebut nodenya saling terhubung melalui pointer.

Lantas, apakah itu Single Linked List? Sesuai penjelasan pada paragraf sebelumnya, antar elemen data terhubung nodenya melalui pointer. Nah, pointer inilah yang menentukan sebuah Linked List apakah itu Single, Double, Circular, atau Double Circular. Sebuah Linked List dikatakan sebagai single apabila dua node hanya terhubung dengan satu pointer saja (entah itu pointer maju ataupun mundur). Jika, dua node terhubung dengan dua pointer (bolak balik) maka disebut Double. Apabila node first dan last nya saling terhubung dan hanya dihubungkan dengan satu pointer maka disebut single circular. Terakhir, apabila node first dan last nya terhubung dengan dua pointer (bolak balik) maka disebut double circular.

Secara sederhana berikut penjelasan melalui gambar.

Sebuah Node lengkap dengan elemen data dan pointernya

Kemudian contoh dari Single Linked List adalah sebagai berikut.

Dapat kita lihat dari gambar di atas, masing – masing node dihubungkan oleh satu pointer. Sedangkan pada pointer node terakhir tidak menunjuk ke mana – mana alias null.

Operasi – operasi pada Single Linked List

Pada single linked list secara umum dikenal dua operasi, yakni operasi push dan pop. Operasi push adalah operasi yang menambahkan data pada list, sedangkan operasi pop adalah operasi yang menghapus data dari list. Untuk operasi push secara umum dapat dilakukan secara first yang menambahkan data pada head dan secara last yang menambahkan data pada tail. Sedangkan pop juga sama, dapat dilakukan secara first yang menghapus data pada head dan secara last yang menghapus data pada tail.

Dari kedua gambar di atas dapat kita lihat bahwa letak / posisi data yang di push tidak selalu pada satu tempat (memory) yang sama. Karena prinsip pada Linked List adalah tidak memandang data itu berada, selama antar data itu masih terhubung, maka data yang saling terhubung tersebut masih dalam satu sequence. Oleh karenanya, penggambaran push node baru ke dalam list dapat diperlihatkan dengan menghubungkan data yang letak / posisinya berbeda.

Untuk operasi push yang melibatkan head dan tail itu sangat sederhana. Karena pada head nodenya belum ditunjuk pointer apapun, sedangkan pada tail, pointernya menunjuk pada NULL. Oleh karenanya operasi push pada head dan tail sangat sederhana. Berbeda sekali dengan operasi push pada index-N. Operasi push yang dilakukan pada index-N melibatkan dua aksi, yang pertama adalah memutus pointer dari node index-(N-1) ke node index-(N+1); kemudian menghubungkan pointer dari node index-(N-1) ke node index-N; dan dilanjutkan dengan menghubungkan pointer dari node index-N ke node index-(N+1). Proses ini disebut juga dengan insertion atau proses menyisipkan data ke dalam list.

Lalu bagaimanakah dengan operasi pop? Operasinya hampir sama dengan push dan bahkan hanya merupakan kebalikan dari operasi push. Berikut adalah penggambarannya.

Hampir sama dengan push, pada kedua pop di atas (head & tail) dapat kita lihat bahwa proses pop dilakukan hanya dengan memutus pointer yang menunjuk. Untuk pop pada head, pointer yang menunjuk ke node next diputus dan menjadikan node next menjadi head. Begitu pula dengan pop pada tail, node prev memutuskan pointer yang menunjuk ke node next (yang dalam hal ini adalah tail) dan membuat pointernya tidak menunjuk apa apa alias NULL. Hal ini menjadikan node prev menjadi tail.

Untuk pop pada index-N prosesnya agak sedikit berbeda. Karena pada kasus ini, seluruh node sudah terhubung dan satu node dipaksa untuk memisahkan diri. Oleh karena itu, untuk pop pada index-N, kali pertama pointer node index-(N-1) memutuskan hubungan terlebih dahulu dengan node index-N. Pointer node index-(N-1) dalam hal ini sudah tidak lagi menunjuk node index-N. Pointer node index-(N-1) kemudian melanjutkannya dengan menunjuk node index-(N+1) yang mana sudah sudah ditunjuk terlebih dahulu oleh pointer node index-N. Oleh karenanya, pointer node index-N pun melepaskan diri dari node index-(N+1) dengan tidak lagi menunjukkan. Dengan demikian node index-N sudah keluar dari list.

Demikianlah penjelasan singkat mengenai operasi – operasi pada Single Linked List. Selanjutnya, mari kita beralih ke bagian berikutnya. Implementasi Single Linked List dengan menggunakan bahasa pemrograman Java.

Implementasi Single Linked List dengan Menggunakan Java

Untuk implementasi Single Linked List dengan menggunakan Java, Saya buat agak panjang. Hal ini bertujuan supaya Anda dapat memahami proses logika dari Single Linked List dengan menggunakan bahasa pemrograman Java. Mari kita mulai.

Pertama, buatlah class dengan nama JavaLinkedList lengkap dengan main methodnya.

public class JavaLinkedList {
     public static void main(String[] args){
     }
}

Kedua, import komponen – komponen yang dibutuhkan.

import java.util.LinkedList;
import java.util.Scanner;
import java.util.InputMismatchException;

Ada 3 komponen yang dibutuhkan dalam program ini. Yang pertama adalah Linked List itu sendiri, Scanner yang berfungsi untuk menerima masukan, dan InputMismatchException yang berfungsi untuk menghandle kesalahan masukan (validasi masukan).

Ketiga, buatlah satu object dengan jenis Linked List dan tipe data String.

private static LinkedList<String> dataStorage = new LinkedList<>();

Keempat, buatlah sebuah method dengan nilai kembalian object Scanner. Saya melakukan hal ini supaya object Scanner dapat dipakai berulangkali dengan berbagai jenis tipe data.

private static Scanner extracted() {
    return new Scanner(System.in);
}

Kelima, Saya membuat method displayData() terlebih dahulu. Tujuannya adalah untuk menampilkan isi Linked List setiap selesai melakukan suatu aksi.

private static void displayData(){
    System.out.println("\nData dalam List: " + dataStorage);
    System.out.println("Total Data     : " + dataStorage.size());
}

Keenam, kita buat dua method void untuk menghandle push secara mendasar. Maksudnya secara normal di sini adalah, jika tidak menggunakan penunjuk node, maka data yang di push akan diletakkan di tail. Namun, jika menggunakan penunjuk node, maka data yang di push akan di sisipkan di node yang ditunjuk.

private static void addData() {
    System.out.print("Masukkan Data: ");
    String tempData = extracted().nextLine();
    dataStorage.add(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();
	}

Ketujuh, Saya membuat dua method void yang digunakan untuk menghandle push pada head dan tail

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();
}

Kedelapan, Saya membuat method dengan nilai kembalian boolean yang mana adalah hasil pencarian data pada list. Method ini akan Saya gunakan pada proses pop berbasis konten data.

private static boolean searchData(String data) {
    return dataStorage.contains(data);
}

Kesembilan, Saya membuat method void yang digunakan untuk menghandle pop pada index ke N.

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();
}

Kesepuluh, selanjutnya kita buat dua method void yang menghandle pop pada head dan tail.

private static void removeDataAtFirst() {
    dataStorage.removeFirst();
    displayData();
}

private static void removeDataAtLast() {
    dataStorage.removeLast();
    displayData();
}

Kesebelas, ini adalah tambahan fungsi yang Saya buat yakni menghapus node berdasarkan konten datanya. Jadi, sebelum melakukan pop, terlebih dahulu konten data akan di bandingkan dengan kata kunci pencarian. Proses pembandingan ini dilakukan dengan memanfaatkan method searchData yang telah dibuat sebelumnya. Apabila hasil kembalian dari method searchData adalah TRUE, maka node yang memiliki data yang dicari tadi akan di-pop.

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();
}

Kedua belas, Saya buat method untuk menghandle proses exit program

private static void programExit() {
    System.exit(0);
}

Ketiga belas, Kita buat 4 method yang berfungsi untuk menghandle User Experience dari program ini.

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!");
            status = true;
        }
    }

    switch (indexMenu) {
        case 1 -> addData();
        case 2 -> addDataToFirst();
        case 3 -> addDataToLast();
        case 4 -> addDataAtLocation();
        case 5 -> removeData();
        case 6 -> removeDataAtFirst();
        case 7 -> removeDataAtLast();
        case 8 -> removeDataByContent();
        case 9 -> programExit();
     }
     programMenu();
}

 private static void programMenu() {
    System.out.println("""

          .: PROGRAM MENU :.
           1. Add Data
           2. Add Data at First
           3. Add Data at Last
           4. Add Data at N Index
           5. Remove Data at N Index
           6. Remove Data at First
           7. Remove Data at Last
           8. Remove Data by Data Content
                 9. Program Exit""");
    programSwitcher();
}

Keempat belas, Panggil method programTitle dan programMenu di dalam method main.

public static void main(String[] args) {
    programMenu();
}

Program selengkapnya adalah sebagai berikut:

import java.util.LinkedList;
import java.util.Scanner;
import java.util.InputMismatchException;

public class LinkedListImp {
    private static final LinkedList<String> dataStorage = new LinkedList<>();

    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 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!");
                status = true;
            }
        }

        switch (indexMenu) {
            case 1 -> addData();
            case 2 -> addDataToFirst();
            case 3 -> addDataToLast();
            case 4 -> addDataAtLocation();
            case 5 -> removeData();
            case 6 -> removeDataAtFirst();
            case 7 -> removeDataAtLast();
            case 8 -> removeDataByContent();
            case 9 -> programExit();
        }
        programMenu();
    }

    private static void programMenu() {
        System.out.println("""

                .: PROGRAM MENU :.
                 1. Add Data
                 2. Add Data at First
                 3. Add Data at Last
                 4. Add Data at N Index
                 5. Remove Data at N Index
                 6. Remove Data at First
                 7. Remove Data at Last
                 8. Remove Data by Data Content
                 9. Program Exit""");
        programSwitcher();
    }

    public static void main(String[] args) {
        programMenu();
    }
}

Setelah kita compile selanjutnya kita RUN dan berikut adalah output dari program di atas :D

berikut merupakan program menu yang kita tulis tadi dan output saat kita memanggil program Add Data dengan menginput 1 dan memasukkan angka 1 ke dalam node.

ini yang terjadi saat command Add Data at First dipanggil dan kita memasukkan angka 4 ke head.

ini yang terjadi saat command Add Data at Last dipanggil dan kita memasukkan angka 3 ke tail.

bisa kita liat dari sini command Add Data memiliki kemiripan fungsi dengan Add Data at Last.

ini yang terjadi saat kita memanggil command Add Data at N Index. kita menyisipkan angka 7 di Index ke-N yang kita masukkan 2.

ini output dari command Remove Data at N Index. kita menghapus data pada index ke-3 yaitu nomor 3.

ini yang terjadi saat kita memanggil command Remove Data at First untuk menghapus data di Head yaitu dari input kita 4.

ini yang terjadi saat kita memanggil command Remove Data at Last untuk menghapus data di Tail yaitu dari input kita 5.

ini yang terjadi saat kita memanggil command Remove Data by Data Content yang berarti kita menghapus data menurut isi dari index node yang ada. bisa kita lihat bahwa kita menghapus angka 1 dan angka 1 itu hilang dari node.

dan yang terakhir adalah ini yang terjadi saat kita memanggil command Program Exit. program akan berhenti.

Search This Blog

Blodhil (Blog Fadhil)