Belajar Data Structure - Array & String

#Pendahuluan

Setelah di episode 2 kita memahami notasi Big-O dan cara menganalisis kompleksitas, pada episode ini kita mulai menyentuh struktur data pertama yang paling fundamental: array dan string. Keduanya saling terkait — string pada banyak bahasa pada dasarnya adalah array of chars — dan pemahaman tentang mereka menjadi fondasi untuk semua struktur data yang lebih kompleks.

Array bukan sekadar "kumpulan data". Ia adalah representasi paling murni dari ide "menyimpan data di lokasi memori yang berurutan" — dan ide ini memiliki konsekuensi besar terhadap performa. Memahami mengapa array cepat untuk akses acak tetapi lambat untuk insert di tengah adalah kunci untuk memahami trade-off di semua struktur data lainnya.

#Array: Contiguous Memory

#Apa Itu Array?

Array adalah kumpulan elemen dengan tipe yang sama, disimpan di lokasi memori yang berurutan (contiguous). Karena elemen-elemen berurutan, mengakses elemen ke-i bisa dilakukan langsung dengan menghitung alamat memori: base_address + i * element_size. Inilah yang membuat array memiliki O(1) random access.

#Representasi di Memori

Bayangkan array [10, 20, 30, 40, 50] dengan elemen 4 byte. Jika array dimulai dari alamat 1000:

Mengakses index 3 cukup menghitung 1000 + 3 × 4 = 1012 — tanpa perlu menelusuri satu per satu. Ini yang dimaksud random access O(1).

#Operasi Array

#Dynamic Array (List)

#Masalah Fixed-Size Array

Array statis memiliki ukuran tetap. Jika kalian butuh lebih banyak ruang, kalian harus membuat array baru dan menyalin seluruh isi — operasi O(n) yang mahal.

#Solusi: Dynamic Array

Dynamic array (Python list, C++ std::vector, Java ArrayList) menyelesaikan masalah ini dengan strategi resize: ketika array penuh, alokasikan array baru dengan ukuran lebih besar (biasanya 2x lipat), lalu salin elemen-elemen.

#Amortized O(1) Append

Meskipun resize itu O(n), operasi resize terjadi hanya sesekali. Rata-rata waktu append dihitung sebagai amortized O(1) — artinya secara rata-rata, setiap append memakan waktu konstan, meskipun sesekali ada resize yang mahal.

n append operations total cost: n + resize_cost ≈ n + n = 2n
Average cost per append: 2n / n = 2 → O(1)

#Implementasi Sederhana

Dynamic array sederhana

class DynamicArray:
    def __init__(self):
        self.capacity = 2
        self.size = 0
        self.data = [None] * self.capacity
 
    def append(self, value):
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = value
        self.size += 1
 
    def _resize(self):
        new_capacity = self.capacity * 2
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity
 
    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        return self.data[index]

#Perbandingan dengan Built-in

Perbandingan custom vs built-in

import time
 
class DynamicArray:
    def __init__(self):
        self.capacity = 2
        self.size = 0
        self.data = [None] * self.capacity
 
    def append(self, value):
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = value
        self.size += 1
 
    def _resize(self):
        new_capacity = self.capacity * 2
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity
 
n = 100000
start = time.perf_counter()
arr = DynamicArray()
for i in range(n):
    arr.append(i)
custom_time = time.perf_counter() - start
 
start = time.perf_counter()
py_list = []
for i in range(n):
    py_list.append(i)
builtin_time = time.perf_counter() - start
 
print(f"Custom: {custom_time:.4f}s")
print(f"Built-in: {builtin_time:.4f}s")
print(f"Built-in faster: {custom_time / builtin_time:.1f}x")

Built-in list akan jauh lebih cepat karena diimplementasi dalam C dengan optimasi yang lebih agresif.

#String: Array of Characters

#Immutability vs Mutability

Berbagai bahasa memiliki pendekatan berbeda terhadap string:

Di Python, "hello"[0] = "H" akan error karena string immutable. Untuk memodifikasi string, kalian harus membuat string baru — atau menggunakan list dan join.

#String Manipulation Patterns

#Sliding Window

Sliding window adalah pattern untuk menyelesaikan masalah yang melibatkan subsequence atau substring berdekatan. Ide dasarnya: geser dua pointer (kiri dan kanan) untuk mendefinisikan window, lalu perbesar/kecilkan window sesuai kebutuhan.

Sliding window: panjang substring tanpa repeat

def longest_unique_substring(s):
    char_set = set()
    left = 0
    max_length = 0
 
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
 
    return max_length

#Two-Pointer

Two-pointer menggunakan dua indeks untuk menyelesaikan masalah — berguna untuk palindrome, pair sum, dan operasi terurut.

Two pointer: cek palindrome

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

#Penutup

Inti yang harus dibawa pulang:

• Array = contiguous memory → O(1) random access, O(n) insert/delete di tengah.
• Dynamic array (list) menggunakan strategi resize → amortized O(1) append.
• String di Python/Java immutable — setiap modifikasi membuat string baru.
• Sliding window dan two-pointer adalah pattern penting untuk string dan array.
• Pahami trade-off: array cepat untuk akses, lambat untuk insert di tengah.

Di episode 4 selanjutnya kita akan membahas rekursi dan stack frame — bagaimana rekursi bekerja di balik layar, base case vs recursive case, tail recursion, serta koneksi rekursi ke tree traversal dan divide-and-conquer. Pastikan kalian sudah praktik sliding window dan two-pointer, karena rekursi akan membawa kemampuan kalian ke level berikutnya!