Java Academy · Pelajaran

Struktur Internal LinkedList

Pelajari struktur node dua arah pada LinkedList dan karakteristik kompleksitas waktunya.

Struktur Internal LinkedList adalah pelajaran Java Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Java Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Java Academy mencakup 4 pelajaran total.

Struktur Internal LinkedList

LinkedList dari Java adalah daftar tertaut ganda: setiap simpul menyimpan referensi ke simpul sebelumnya dan berikutnya, serta nilai elemennya. Berbeda dari ArrayList, tidak ada larik pendukung — memori dialokasikan untuk setiap simpul.

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

Profil Kompleksitas Waktu

Karakteristik kinerja LinkedList berbeda secara signifikan dari ArrayList:

addFirst / addLast: O(1)
get(indeks): O(n) — harus menelusuri dari awal atau akhir
remove(indeks): O(n) untuk mencari, kemudian O(1) untuk melepaskan tautan
Penelusuran: O(n)

Gunakan LinkedList ketika Anda memerlukan penyisipan yang sering di awal atau akhir, bukan akses acak.

Membuat dan Menelusuri LinkedList

Membuat LinkedList dan melakukan iterasi mengikuti interface List yang sudah Anda kenal. Perbedaannya terletak pada struktur internal.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst, addLast, removeFirst, removeLast

LinkedList menyediakan operasi pada awal dan akhir yang tidak ditawarkan ArrayList secara efisien:

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

Melepas Tautan Simpul: Penghapusan O(1) Setelah Ditemukan

Setelah Anda memiliki referensi ke sebuah simpul (melalui iterator), penghapusan berlangsung dalam O(1) karena hanya penunjuk berikutnya dan sebelumnya yang perlu diperbarui — tidak ada pergeseran elemen seperti pada ArrayList.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

Overhead Memori dibandingkan ArrayList

Setiap simpul LinkedList membawa dua referensi tambahan (prev, next) dan satu referensi elemen — sekitar 48 byte untuk setiap entri pada JVM 64-bit. ArrayList hanya menyimpan referensi elemen (8 byte) dalam larik yang bersebelahan.

Untuk kumpulan data besar yang banyak dibaca, ArrayList biasanya lebih ramah cache dan menggunakan lebih sedikit memori.

Operasi Antrean Dua Ujung: Tumpukan dan Antrean

LinkedList mengimplementasikan interface Deque, sehingga dapat digunakan sebagai tumpukan maupun antrean.

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Ikhtisar PriorityQueue

PriorityQueue adalah antrean berbasis heap yang selalu mengeluarkan elemen terkecil terlebih dahulu, berdasarkan urutan alami atau pembanding. Ini NOT didukung oleh daftar tertaut — struktur ini menggunakan larik heap biner.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

PriorityQueue dengan Comparator Khusus

Berikan Comparator untuk membalik urutan atau mengurutkan berdasarkan bidang khusus:

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

Memilih LinkedList atau ArrayList

Pedoman umum:

Gunakan ArrayList untuk akses acak, iterasi, dan sebagian besar skenario.
Gunakan LinkedList ketika Anda memerlukan penyisipan/penghapusan O(1) yang sering di kedua ujung dan tidak memerlukan akses berdasarkan indeks.
Gunakan PriorityQueue ketika Anda memerlukan pemrosesan terurut (penjadwalan tugas, algoritma Dijkstra).

Kesalahan Umum

Hindari memanggil get(i) dalam perulangan pada LinkedList — total waktunya adalah O(n²):

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

Pemeriksaan Singkat

Operasi LinkedList manakah yang memiliki kompleksitas O(1), terlepas dari ukuran daftar?

Ringkasan: LinkedList dan Antrean Dua Ujung

Poin-poin utama:

LinkedList adalah daftar tertaut ganda dengan operasi O(1) di awal dan akhir
Akses acak (get/set berdasarkan indeks) memiliki kompleksitas O(n)
Mengimplementasikan Deque — dapat digunakan sebagai tumpukan atau antrean
PriorityQueue menyediakan pemrosesan yang diurutkan berdasarkan heap
Utamakan ArrayList untuk sebagian besar kasus penggunaan; LinkedList unggul untuk perubahan yang sering di awal atau akhir

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Struktur Internal LinkedList” gratis?

Ya — teks lengkap “Struktur Internal LinkedList” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Java Academy, upgrade ke CoddyKit PRO. Kursus Java Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Struktur Internal LinkedList”?

Pelajari struktur node dua arah pada LinkedList dan karakteristik kompleksitas waktunya. Kamu berlatih Java Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Java Academy?

Tidak diperlukan pengalaman sebelumnya. Java Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Struktur Internal LinkedList” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy