Tutorial: (Struktur Data) Implementasi Single Linked List sederhana dengan Java

Reading Time: 9 minutes

Selamat datang di blogs UNYDeveloperNetwork. Sebagai anak informatika atau anak computer science atau ilkom, yang masih beginner ataupun yang sudah expert pasti mengenal istilah Single Linked List (atau umumnya hanya disebut Linked List saja). Biasanya topik ini disampaikan pada mata perkuliahan struktur yang nanti diikuti oleh Double Linked List dan Circular Linked List. Kedua topik tersebut juga dibahas pada blogs ini. Namun, khusus pada artikel ini, Saya akan secara khusus membahas apa itu Linked List dan implementasi secara sederhana dengan menggunakan Bahasa pemrograman Java.

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.

Penggambaran push secara sederhana pada head
Penggambaran push secara sederhana 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.

Penggambaran push pada index-N list secara sederhana

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.

Penggambaran pop secara sederhana pada head
Penggambaran pop secara sederhana pada tail

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.

Penggambaran pop secara sederhana pada index-N

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

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 programTitle() {
    System.out.println("\nSimple Linked List Program"
                     + "\nDitulis dalam bahasa pemrograman Java"
                     + "\nOleh: Muhammad Irfan Luthfi"
                     + "\ngithub.com/milstrike\n");
}

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(); 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"
                     + "\n10. Program Exit");
    programSwitcher();
}

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

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

Program selengkapnya adalah sebagai berikut:

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

/*
 * Example of Simple Java Linked List
 * Author: Muhammad Irfan Luthfi
 * https://github.com/milstrike
 * 
 */

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: Muhammad Irfan Luthfi"
				         + "\ngithub.com/milstrike\n");
	}
	
	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(); 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"
				         + "\n10. Program Exit");
		programSwitcher();
	}
	
	public static void main(String[] args) {
		programTitle();
		programMenu();
	}
}

Setelah kita compile selanjutnya kita RUN:

Baik, bagaimana? sudah paham mengenai Single Linked List? Apabila Anda belum paham, silakan tinggalkan pertanyaan pada kolom komentar. Ingat!, hanya pertanyaan yang berhubungan dengan artikel ini (Single Linked List) yang akan Saya jawab.

Demikianlah artikel Tutorial: (Struktur Data) Implementasi Single Linked List sederhana dengan Java ini. Semoga apa yang Saya tulis di sini bermanfaat bagi kita semua. Apabila Anda ingin mencuplik artikel ini, jangan lupa untuk mencantumkan URLnya. Terima kasih banyak ^_^

UNDUH PROJECT

Please follow and like us:
Advertisements

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *