Array dan Linked List adalah dua struktur data dasar yang menjadi pondasi hampir semua struktur data lain. Array menawarkan akses acak O(1) tetapi insert/delete O(n). Linked List menawarkan insert/delete O(1) pada posisi yang diketahui tetapi akses acak O(n). Pada chapter ini kita akan mengimplementasikan LinkedList manual di Kotlin dan membandingkan kinerjanya dengan Array. Pembaca akan melihat kapan memilih satu di atas yang lain berdasarkan pola akses data.

Perbandingan Array vs Linked List #

OperasiArrayLinked List
Akses by indexO(1)O(n)
Insert di awalO(n) (geser)O(1)
Insert di akhirO(1) amortizedO(n) (atau O(1) dengan tail pointer)
Insert di tengahO(n) (geser)O(1) (bila node diketahui)
Hapus by indexO(n) (geser)O(n) (cari) + O(1) (unlink)
Memori per elemen4 byte (Int)16+ byte (data + reference)

Array menang di akses acak dan kepadatan memori. Linked List menang di insert/delete di posisi yang sudah diketahui (misalnya saat memegang reference ke node).

Implementasi LinkedList Manual #

kotlin 
// Demo Array dan Linked List: perbandingan operasi dan implementasi LinkedList.

// === Array: akses random O(1) ===
fun demoArray() {
    val arr = intArrayOf(10, 20, 30, 40, 50)
    println("Array: ${arr.toList()}")
    println("Akses index 0 (O(1)): ${arr[0]}")
    println("Akses index 4 (O(1)): ${arr[4]}")

    // Insert di tengah: O(n) karena elemen setelahnya harus digeser
    val mutable = arr.toMutableList()
    mutable.add(2, 25)
    println("Setelah insert 25 di index 2 (O(n)): $mutable")

    val arrLarge = IntArray(1000000) { it }
    val t0 = System.nanoTime()
    val x = arrLarge[500000]
    val t1 = System.nanoTime()
    println("Akses random elemen ke-500000 (O(1)): $x dalam ${(t1 - t0)} ns")
}

// === Implementasi LinkedList manual ===
class Node<T>(var data: T, var next: Node<T>? = null)

class LinkedList<T> {
    private var head: Node<T>? = null
    private var size = 0

    fun size(): Int = size

    // Tambah di akhir: O(n) karena harus traversing ke tail
    fun tambahAkhir(data: T) {
        val node = Node(data)
        if (head == null) {
            head = node
        } else {
            var curr = head
            while (curr?.next != null) curr = curr.next
            curr?.next = node
        }
        size++
    }

    // Tambah di awal: O(1)
    fun tambahAwal(data: T) {
        val node = Node(data, head)
        head = node
        size++
    }

    // Akses by index: O(n) karena harus traversing
    fun akses(index: Int): T? {
        if (index < 0 || index >= size) return null
        var curr = head
        repeat(index) { curr = curr?.next }
        return curr?.data
    }

    // Hapus by index: O(n) karena traversing + unlink
    fun hapus(index: Int): Boolean {
        if (index < 0 || index >= size) return false
        if (index == 0) {
            head = head?.next
        } else {
            var prev = head
            repeat(index - 1) { prev = prev?.next }
            prev?.next = prev?.next?.next
        }
        size--
        return true
    }

    fun toList(): List<T> {
        val result = mutableListOf<T>()
        var curr = head
        while (curr != null) {
            result.add(curr.data)
            curr = curr.next
        }
        return result
    }
}

fun main() {
    println("=== Demo Array dan Linked List ===")

    println("--- Array ---")
    demoArray()

    println()
    println("--- LinkedList ---")
    val list = LinkedList<Int>()
    list.tambahAkhir(10)
    list.tambahAkhir(20)
    list.tambahAkhir(30)
    println("Setelah tambah akhir 10, 20, 30: ${list.toList()}")

    list.tambahAwal(5)
    println("Setelah tambah awal 5: ${list.toList()}")

    println("Akses index 2 (O(n)): ${list.akses(2)}")
    println("Akses index 10 (out of range): ${list.akses(10)}")

    list.hapus(1)
    println("Setelah hapus index 1: ${list.toList()}")
    println("Ukuran: ${list.size()}")

    println()
    println("--- Perbandingan ukuran besar ---")
    val arrLarge = IntArray(100000) { it }
    val t0 = System.nanoTime()
    val arrEl = arrLarge[99999]
    val t1 = System.nanoTime()
    println("Array akses index 99999 (O(1)): $arrEl dalam ${(t1 - t0)} ns")

    val linkedLarge = LinkedList<Int>()
    for (i in 1..1000) list.tambahAkhir(i)
    val t2 = System.nanoTime()
    val linkedEl = list.akses(999)
    val t3 = System.nanoTime()
    println("LinkedList akses index 999 (O(n)): $linkedEl dalam ${(t3 - t2)} ns")
}

Output yang Dihasilkan:

text 
=== Demo Array dan Linked List ===
--- Array ---
Array: [10, 20, 30, 40, 50]
Akses index 0 (O(1)): 10
Akses index 4 (O(1)): 50
Setelah insert 25 di index 2 (O(n)): [10, 20, 25, 30, 40, 50]
Akses random elemen ke-500000 (O(1)): 500000 dalam 76 ns

--- LinkedList ---
Setelah tambah akhir 10, 20, 30: [10, 20, 30]
Setelah tambah awal 5: [5, 10, 20, 30]
Akses index 2 (O(n)): 20
Akses index 10 (out of range): null
Setelah hapus index 1: [5, 20, 30]
Ukuran: 3

--- Perbandingan ukuran besar ---
Array akses index 99999 (O(1)): 99999 dalam 334 ns
LinkedList akses index 999 (O(n)): 997 dalam 31951 ns

Bedah Kode Baris-per-Baris #

Mari kita amati bagian kunci:

  1. Baris 4-15 (demoArray): Akses elemen array by index adalah satu operasi O(1). Insert di tengah mutable.add(2, 25) memerlukan menggeser elemen setelahnya, sehingga O(n).
  2. Baris 18-19 (Node): Setiap node menyimpan data dan reference ke node berikutnya. Linked list tidak menyimpan index; akses harus dari head.
  3. Baris 21-37 (tambahAkhir): Untuk menambah di akhir, kita harus traverse dari head sampai node terakhir. Kompleksitas O(n). Implementasi produksi biasanya menyimpan tail pointer untuk membuat operasi ini O(1).
  4. Baris 39-43 (tambahAwal): Untuk menambah di awal, kita hanya membuat node baru dengan next menunjuk ke head lama. Kompleksitas O(1)—keunggulan utama linked list.
  5. Baris 45-51 (akses): Akses by index harus traverse dari head. Untuk index k, butuh k langkah. Kompleksitas O(n). Inilah kelemahan utama linked list dibanding array.

Kapan Memilih Apa #

Pola aksesPilih
Sering akses by indexArray
Sering insert/delete di awal/tengahLinked List
Data berukuran besar tetap (image, audio)Array (kontigu di memori)
Banyak modifikasi struktural (queue, deque)Linked List
Memori sangat terbatasArray (tidak ada overhead reference)

Penutup #

Array unggul di akses acak dan kepadatan memori; Linked List unggul di insert/delete di posisi yang diketahui. Pemilihan tergantung pola akses data yang dominan dalam aplikasi. Pada chapter berikutnya kita akan membahas Stack dan Queue: dua struktur data yang dibangun di atas array atau linked list dengan operasi yang dibatasi.

Referensi #

Referensi Lanjutan #