Struktur Data & Algoritma untuk Backend

15 min readFundamental
JavaStruktur DataAlgoritmaBig-O

Struktur data adalah cara Anda mengatur data di memori; algoritma adalah langkah yang Anda jalankan di atasnya. Keduanya bukan topik "teori kuliah" yang bisa ditunda — di backend, struktur data yang salah bisa membuat sebuah endpoint yang harusnya balas dalam 50 milidetik malah menjawab dalam 50 detik. Artikel ini melengkapi bahasan Java Collections Framework: di sana kita belajar mana implementasi yang harus dipilih, di sini kita belajar mengapa — lewat Big-O notation, struktur data dasar, dan algoritma pencarian & pengurutan.

Kenapa Struktur Data & Algoritma Penting untuk Backend

Backend bekerja dengan data dalam jumlah besar: jutaan user, jutaan order, jutaan log. Di skala itu, selisih O(1) vs O(n) bukan soal milidetik lagi, melainkan soal detik vs hari.

  • Query besar. Endpoint yang mengembalikan daftar user biasanya tidak hanya membaca dari database — data sering dimanipulasi, digabung, atau di-cache di memori terlebih dahulu. Semua manipulasi itu memakai struktur data.
  • Bottleneck. Ketika sistem lambat, penyebabnya biasanya salah satu dari ini: query database yang buruk, I/O yang menunggu, atau struktur data yang salah di kode — misalnya memakai List untuk mencari data padahal seharusnya Map.
  • Skala. Di data kecil, semua struktur data terasa sama cepat. Perbedaannya baru terlihat saat data bertambah — dan saat itulah backend Anda harus sudah benar, karena menulis ulang struktur data inti setelah produksi jauh lebih mahal daripada memilihnya dengan benar sejak awal.

Mentalitas backend engineer: selalu tanyakan "berapa kompleksitas operasi ini?" setiap kali menulis loop. Satu loop O(n²) yang memproses 100.000 baris data = 10 miliar langkah. Itu bukan sekadar lambat — itu pembunuh server.

Big-O Notation: Bahasa untuk Mengukur Performa

Big-O notation adalah cara ringkas menyatakan bagaimana waktu eksekusi bertumbuh seiring bertambahnya ukuran data n. Ini notasi asimptotik: kita membuang konstanta dan faktor yang tidak penting, fokus pada bentuk pertumbuhan — bukan "butuh 42 langkah", melainkan "tumbuh sebanding dengan n".

Dua aturan praktis saat menganalisis kode:

  1. Buang konstanta. 5n + 100 dan n sama-sama O(n) — yang menentukan bentuk kurva adalah n.
  2. Dominasi: hanya suku dengan pertumbuhan tercepat yang dihitung. O(n² + n) cukup ditulis O(n²).

Kelas kompleksitas yang wajib dikenal

NotasiNamaContoh operasiGambaran mental
O(1)KonstanAkses array by index, get di HashMap"Seketika", tidak peduli ukuran data
O(log n)LogaritmikBinary search, get di TreeMapData berlipat ganda, langkah hanya bertambah 1
O(n)LinearScan satu per satu, linear searchData 2×, waktu 2×
O(n log n)LinearithmicArrays.sort, merge sort, TimsortCukup cepat untuk dataset besar
O(n²)KuadratikLoop bersarang, Bubble/Selection sortData 2×, waktu 4× — cepat meledak

Gambar mental O(log n): bayangkan mencari nama di buku telepon setebal 1 juta halaman dengan membuka buku di tengah terus-menerus. Setiap langkah membuang separuh halaman. Menemukan entri butuh sekitar 20 langkah — padahal buku punya 1 juta halaman. Itulah logaritma: membalik data berlipat ganda hanya menambah satu langkah.

Analisis contoh kode

// Skenario 1: loop bersarang -> O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);   // n * n = n² langkah
    }
}

// Skenario 2: loop tunggal -> O(n)
for (int i = 0; i < n; i++) {
    System.out.println(i);           // n langkah
}

// Skenario 3: lookup HashMap -> O(1)
Map<Long, User> byId = new HashMap<>();
User u = byId.get(userId);           // seketika, berapa pun isinya

Untuk n = 100.000, skenario 1 menjalankan 10 miliar operasi; skenario 2 hanya 100 ribu; skenario 3 selalu 1. Ketika memilih struktur data, tujuan utama Anda di backend adalah mendorong operasi dominan ke kelas yang lebih rendah — itulah yang dibahas di bagian berikutnya. Oracle membahas praktik ini secara resmi di artikel Java Performance, termasuk mengapa pemilihan Collection yang tepat berdampak besar pada throughput aplikasi.

Struktur Data Dasar & Kompleksitas Operasi

Setiap struktur data menukar sesuatu: kecepatan akses melawan kecepatan sisip, urutan melawan kekacauan, memori melawan waktu. Bagian ini memetakan struktur data dasar beserta kompleksitas operasi intinya.

Array: Akses Cepat, Sisip Lambat

Array menyimpan elemen berjajar di memori, sehingga tiap elemen punya indeks. Mengambil elemen ke-i tinggal menghitung posisinya — tidak peduli berapa panjang array.

int[] skor = {85, 90, 78, 92};
skor[2];             // 78 — langsung, O(1)
skor[3] = 95;        // update indeks 3, O(1)

Namun menyisipkan di tengah atau menghapus berarti menggeser semua elemen setelahnya — mahal.

OperasiKompleksitas
a[i] (akses/update by index)O(1)
Insert di tengahO(n) — geser elemen sesudahnya
Delete di tengahO(n) — geser elemen sesudahnya
Cari nilai (contains)O(n) — scan satu per satu

Array berukuran tetap (new String[5] tidak bisa lebih). Saat ukurannya harus tumbuh, Anda butuh struktur dinamis — ArrayList.

ArrayList vs LinkedList (Singkat)

Artikel Collections Framework sudah membahas keduanya secara detail. Inti yang perlu diingat di sini:

  • ArrayList menyimpan data dalam array yang tumbuh otomatis: get(index) O(1), add di ujung O(1) rata-rata, add/remove di tengah O(n).
  • LinkedList menyimpan node yang saling menunjuk: addFirst/addLast O(1), tapi get(index) O(n).

Aturan praktis: default ke ArrayList. LinkedList hanya unggul bila operasi dominan Anda sisip/hapus di kedua ujung — dan untuk itu Java punya abstraksi yang lebih jelas: Deque.

Stack (LIFO) — Terakhir Masuk, Pertama Keluar

Stack bekerja seperti tumpukan piring: piring yang terakhir diletakkan adalah yang pertama diambil. Pola ini disebut LIFO (Last-In, First-Out). Java punya kelas java.util.Stack, tapi dokumentasi resmi Stack sendiri menyarankan menggunakan kelas yang lebih modern — dan dokumentasi Deque merekomendasikan ArrayDeque sebagai implementasi stack yang disarankan.

   push("C")            pop()
    +---+                +---+
    | C |  <- top        | C |  <- keluar (terakhir masuk)
    +---+                +---+
    | B |                | B |
    +---+                +---+
    | A |                | A |
    +---+                +---+

// Stack modern: Deque + ArrayDeque
Deque<String> riwayat = new ArrayDeque<>();
riwayat.push("halaman: /login");
riwayat.push("halaman: /produk");
riwayat.push("halaman: /checkout");

String kembali = riwayat.pop();   // "/checkout" — yang terakhir masuk keluar duluan
String peek = riwayat.peek();     // "/produk" — lihat tanpa mengeluarkan
OperasiKompleksitas
push(x)O(1)
pop()O(1)
peek()O(1)
Cari nilaiO(n)

Kasus pakai di backend: undo (riwayat aksi pengguna), backtracking (menelusuri jalur dan mundur saat buntu), dan parsing (misal memvalidasi pasangan kurung dalam ekspresi).

// Validasi kurung: ekspresi seimbang?
Deque<Character> stack = new ArrayDeque<>();
for (char c : "(a + (b * c))".toCharArray()) {
    if (c == '(') stack.push(c);
    else if (c == ')') {
        if (stack.isEmpty()) return false;   // kurung tutup tanpa pasangan
        stack.pop();                          // cocokkan kurung buka
    }
}
return stack.isEmpty();                        // O(n) total

Queue (FIFO) — Pertama Masuk, Pertama Keluar

Kebalikan stack: Queue bekerja seperti antrian loket — yang pertama datang dilayani pertama. Pola ini disebut FIFO (First-In, First-Out). Antarmuka Queue dijelaskan lengkap di Queue tutorial Oracle; implementasinya bisa ArrayDeque (lebih cepat) atau LinkedList.

   offer("A") offer("B") offer("C")   poll()
   +---+---+---+                       +---+---+---+
   | A | B | C |  ->                   | B | C |   |  -> A keluar duluan
   +---+---+---+                       +---+---+---+

// Antrian job email yang harus dikirim
Queue<EmailJob> antrianEmail = new ArrayDeque<>();
antrianEmail.offer(new EmailJob("hendro@mail.com", "Invoice #123"));
antrianEmail.offer(new EmailJob("endos@mail.com",  "Invoice #124"));

while (!antrianEmail.isEmpty()) {
    EmailJob job = antrianEmail.poll();   // proses yang paling awal masuk duluan
    mailSender.send(job);
}
OperasiKompleksitas
offer(x) (tambah di belakang)O(1)
poll() (ambil di depan)O(1)
peek()O(1)

Kasus pakai di backend: antrian tugas yang diproses sesuai urutan datang — antrian email, antrian notifikasi, message queue sederhana di memori, dan rate-limiting permintaan. Untuk antrian lintas-proses yang tersimpan di disk, gunakan tools khusus (misal RabbitMQ / Redis) — tapi konsep FIFO-nya sama persis.

PriorityQueue (Heap) — Antrian dengan Prioritas

PriorityQueue adalah antrian yang tidak mengeluarkan elemen "paling lama masuk", melainkan elemen berprioritas tertinggi. Di belakang layar ia adalah struktur heap: dokumentasi resmi PriorityQueue menjanjikan offer, poll, remove dalam O(log n).

// Task dengan prioritas (lebih kecil = lebih penting)
PriorityQueue<Task> pqueue = new PriorityQueue<>(
        Comparator.comparingInt(Task::getPriority));

pqueue.offer(new Task("update-lib", 5));
pqueue.offer(new Task("hotfix-kritis", 1));
pqueue.offer(new Task("tune-db", 3));

Task selanjutnya = pqueue.poll();   // "hotfix-kritis" (1) — bukan yang paling lama masuk
OperasiKompleksitas
offer(x)O(log n)
poll()O(log n)
peek()O(1)

PriorityQueue bukan antrian FIFO biasa. poll() mengembalikan elemen terkecil menurut urutan elemennya (natural order / Comparator yang Anda berikan), bukan elemen yang pertama dimasukkan. Jangan memakainya bila urutan kedatangan adalah aturannya.

Kasus pakai di backend: penjadwalan task dengan tingkat urgensi, reminder/notification yang paling mendesak diproses duluan, dan pengambilan k-top cepat (misal "10 order terbesar hari ini").

Hash Table / HashMap — Lookup dalam O(1)

HashMap menyimpan pasangan key-value. Key diproses oleh fungsi hashCode() menjadi "slot" dalam tabel, sehingga pencarian tidak perlu membandingkan satu per satu — langsung menuju slotnya. Rata-rata put, get, remove semuanya O(1).

Map<Long, User> usersById = new HashMap<>();
usersById.put(42L, new User(42L, "hendro@mail.com"));

User u = usersById.get(42L);       // O(1) rata-rata — langsung ke slot hash 42
boolean ada = usersById.containsKey(42L);   // O(1)

Hash collision terjadi saat dua key berbeda jatuh ke slot yang sama. Java menanganinya dengan menyimpan beberapa entri dalam satu slot (menjadi LinkedList, lalu tree bila slotnya penuh) — jadi tetap benar, hanya sedikit melambat. Kualitas hashCode() yang baik menjaga collision tetap jarang.

Kasus pakai di backend: in-memory cache, lookup user by id, pemetaan payload JSON, dan denormalisasi data agar tidak bolak-balik query database.

Tree — Data Terurut dengan O(log n)

Binary search tree menyimpan node dengan aturan: nilai di kiri selalu lebih kecil, nilai di kanan selalu lebih besar. Pencarian tinggal memilih kiri/kanan setiap langkah — membuang separuh data tiap langkah, sehingga O(log n). Java mengimplementasikannya sebagai red-black tree (pohon yang senantiasa seimbang) di balik TreeMap dan TreeSet.

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80
   cari 60: 50 -> 70 -> 60 (3 langkah untuk 8 node)

// TreeMap: key terurut + range query
TreeMap<Long, String> logByTimestamp = new TreeMap<>();
logByTimestamp.put(1000L, "login");
logByTimestamp.put(2000L, "update profil");
logByTimestamp.put(3000L, "checkout");

SortedMap<Long, String> satuJamPertama = logByTimestamp.subMap(1000L, 2000L);
Long palingAwal = logByTimestamp.firstKey();   // 1000L, O(log n)
Strukturput/getIterasiFitur unggulan
HashMapO(1)AcakKecepatan lookup
TreeMapO(log n)TerurutRange query, firstKey/lastKey

Kasus pakai di backend: data yang harus selalu terurut — session timeout terdekat, log berdasarkan timestamp, atau "ambil 5 order termahal" lewat descendingMap().

Graph — Relasi antar Entitas

Graph adalah kumpulan node (simpul) dan edge (hubungan antar simpul). Tidak seperti tree, graph bisa bercabang ke mana saja. Dua cara umum menyimpannya:

AspekAdjacency ListAdjacency Matrix
BentukMap<node, Set<node>>boolean[n][n]
Cek ada edgeO(degree) / O(1) dengan setO(1)
MemoriHemat (hanya edge nyata)Boros — n² slot
Cocok untukRelasi jarang (sparse)Relasi padat (dense)

Di backend, adjacency list jauh lebih umum. Contoh: relasi follower di aplikasi sosial.

Map<String, Set<String>> followers = new HashMap<>();
followers.computeIfAbsent("hendro", k -> new HashSet<>()).add("endos");
followers.computeIfAbsent("hendro", k -> new HashSet<>()).add("budi");

boolean endosMengikutiHendro = followers.get("hendro").contains("endos");

Untuk shortest path (jalur terpendek antara dua node), algoritma yang sering dipakai: BFS untuk graph tanpa bobot (misal "tingkat pertemanan"), dan Dijkstra untuk graph berbobot (misal biaya pengiriman). Keduanya memakai queue / priority queue — abstraksi yang tadi kita bahas.

Jembatan ke database: indeks B-tree di PostgreSQL/MySQL pada dasarnya adalah tree. Ketika Anda belajar TreeMap O(log n), Anda sedang memahami mengapa indeks database membuat query WHERE email = ? cepat — karena konsepnya sama persis.

Algoritma Pencarian

Mencari satu elemen dalam kumpulan data adalah operasi paling sering di backend. Dua pendekatan dasar:

Linear Search — O(n)

Periksa satu per satu dari awal sampai ketemu. Bekerja di data apa pun (tidak perlu terurut), tapi lambat untuk data besar.

// Setara dengan List.contains() — scan satu per satu
for (User u : users) {
    if (u.getEmail().equals("hendro@mail.com")) {
        return u;   // bisa langsung di elemen pertama, atau butuh semua n elemen
    }
}

Binary Search — O(log n)

Syarat wajib: data sudah terurut. Mulai dari tengah, lalu buang separuh yang tidak mungkin memuat target — berulang sampai ketemu. Java sudah menyediakannya lewat Arrays.binarySearch dan Collections.binarySearch.

// Data HARUS sudah terurut naik
List<Integer> harga = new ArrayList<>(List.of(10, 20, 30, 40, 50));
int posisi = Collections.binarySearch(harga, 30);   // 2
if (posisi >= 0) {
    System.out.println("Ditemukan di indeks " + posisi);
}

int[] arr = {10, 20, 30, 40, 50};
int posisiArr = Arrays.binarySearch(arr, 40);       // 3
MetodeSyaratKompleksitasKapan dipakai
Linear searchTidak adaO(n)Data kecil / tidak terurut
Binary searchData terurutO(log n)Data besar, pencarian berulang

Bahaya diam-diam: Collections.binarySearch pada data yang belum terurut tidak melempar exception — ia hanya mengembalikan hasil yang salah secara diam-diam. Selalu pastikan data terurut sebelum memanggilnya.

Algoritma Pengurutan

Urutan yang benar adalah prasyarat binary search dan range query. Java memberi dua jalur:

  1. Arrays.sort — untuk array. Untuk tipe primitif memakai Dual-Pivot Quicksort (O(n log n)); untuk objek memakai Timsort.
  2. Collections.sort / List.sort — untuk List, memakai Timsort (gabungan merge sort + insertion sort), stabil, dan sangat cepat pada data yang hampir terurut.

Bubble sort dan Selection sort adalah materi kuliah yang O(n²) — bagus untuk memahami prinsip, tapi jangan pernah dipakai di produksi. Pada 100 ribu elemen, Timsort selesai dalam hitungan milidetik; bubble sort butuh miliaran perbandingan.

List<String> nama = new ArrayList<>(List.of("Budi", "Andi", "Citra"));
Collections.sort(nama);                      // [Andi, Budi, Citra] — natural order
Arrays.sort(skor);                           // array primitif, O(n log n)

Comparable vs Comparator

  • Comparable: urutan "alami" suatu kelas — kelasnya sendiri yang tahu bagaimana membandingkan dirinya. Satu kelas hanya boleh punya satu.
  • Comparator: urutan "eksternal" — bisa banyak, untuk banyak kebutuhan berbeda, tanpa mengubah kelas.
// Comparable: urutan alami Task berdasarkan priority
class Task implements Comparable<Task> {
    private final int priority;
    private final String nama;

    Task(String nama, int priority) {
        this.nama = nama;
        this.priority = priority;
    }

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

// Comparator: urutan eksternal, bisa bermacam-macam
List<Task> tasks = ...;
tasks.sort(Comparator.comparing(Task::getPriority));              // prioritas naik
tasks.sort(Comparator.comparing(Task::getPriority).reversed());   // prioritas turun
tasks.sort(Comparator.comparing(Task::getNama));                  // urut abjad nama

Sortir descending cukup dengan membalik pembandingnya:

List<Integer> angka = new ArrayList<>(List.of(3, 1, 4, 1, 5));
angka.sort(Comparator.reverseOrder());         // [5, 4, 3, 1, 1]

List<User> byEmailDesc = users.stream()
        .sorted(Comparator.comparing(User::getEmail).reversed())
        .toList();

Studi Kasus Singkat: Memilih Struktur Data untuk Backend

Tiga kebutuhan nyata, tiga pilihan struktur data:

KebutuhanStruktur dataAlasannya
"Cari user berdasarkan email" (sering, 1M+ user)HashMap<String, User>Lookup O(1) vs scan list O(n). Jangan pernah memakai List.contains() untuk ini.
"Riwayat aksi terakhir pengguna" (undo/backtracking)Deque (stack)Aksi terakhir harus keluar pertama — LIFO. push/pop O(1).
"Antrian email yang harus dikirim sesuai urutan"Queue (FIFO)Harus first-in-first-out. offer/poll O(1).
// 1. Lookup user by email — HashMap, jangan scan list
Map<String, User> userByEmail = new HashMap<>();
User u = userByEmail.get("hendro@mail.com");    // O(1)

// 2. Riwayat aksi terakhir — stack
Deque<String> aksiTerakhir = new ArrayDeque<>();
aksiTerakhir.push("CREATE order #12");
aksiTerakhir.push("UPDATE qty order #12");
String undo = aksiTerakhir.pop();               // "UPDATE qty order #12"

// 3. Antrian email — queue
Queue<String> emailQueue = new ArrayDeque<>();
emailQueue.offer("invoice@hendro.com");
emailQueue.offer("invoice@endos.com");
String kirimDulu = emailQueue.poll();           // "invoice@hendro.com"

Kuncinya: pilih struktur data berdasarkan operasi dominan, bukan berdasarkan kenyamanan menulis. Satu perubahan dari List ke Map sering kali cukup untuk menghapus bottleneck endpoint.

Kompleksitas Ruang (Space Complexity)

Big-O tidak hanya berlaku untuk waktu, tapi juga untuk memori: berapa banyak ruang tambahan yang dipakai algoritma seiring pertumbuhan n. Notasinya sama — O(1), O(n), dst.

// In-place sort: menyortir list yang sama, tanpa salinan — O(1) ruang ekstra
angka.sort(null);

// Merge sort (versi naif): butuh array bantuan sebesar data aslinya — O(n) ruang ekstra
// (inilah alasan Timsort dipakai Java: cepat TAPI juga hemat memori)
AlgoritmaRuang ekstraCatatan
In-place sort (in-place Timsort/Quicksort)O(1)Menyortir data yang sama
Merge sortO(n)Butuh area bantuan seukuran data
Rekursi sederhana (misal Fibonacci naif)O(n)Stack frame bertumpuk
HashMap dengan n entriO(n)Slot tabel sebanding jumlah key

Trade-off klasik waktu vs ruang: HashMap menghabiskan lebih banyak memori daripada List karena slot tabelnya harus longgar agar collision jarang — tetapi ia "membayar" memori itu dengan lookup O(1). Di backend, menukar sedikit memori untuk menyelamatkan waktu adalah keputusan yang hampir selalu benar.

Ringkasan

Struktur data dan algoritma adalah bahasa performa backend. Big-O notation memberi Anda cara cepat menilai sebuah operasi: O(1) seketika, O(log n) sangat cepat di data besar, O(n) wajar untuk satu scan, O(n²) sinyal bahaya. Pilih struktur data berdasarkan operasi dominan: HashMap untuk lookup, Deque (stack) untuk undo/backtracking, Queue untuk antrian FIFO, PriorityQueue untuk penjadwalan prioritas, TreeMap untuk data terurut dan range query, Graph untuk relasi antar entitas. Untuk pencarian, ingat bahwa binary search O(log n) mensyaratkan data terurut — dan untuk pengurutan, serahkan ke Arrays.sort/Collections.sort (Timsort) serta bedakan Comparable (urutan alami) dari Comparator (urutan eksternal). Semua itu bermuara pada satu pertanyaan yang sama: apakah struktur data ini tetap cepat saat data tumbuh? Jika jawabannya ya, Anda sudah menyelamatkan server Anda jauh sebelum beban tiba.

Lanjut membaca

← Back to technical articles