Pendahuluan Struktur Data

Kegiatan Belajar 1: Konsep Struktur Data

A. Definisi Struktur Data

1. Pengertian Struktur Data

• Struktur data: cara menyimpan, menyusun, dan mengurutkan data sehingga dapat digunakan secara efisien pada media komputer (Morin, 2012).
• Pentingnya struktur data: digunakan dalam kehidupan sehari-hari seperti membuka file di komputer, melihat kontak telepon, login media sosial, mesin pencari, dan layanan darurat 9-1-1.

2. Permasalahan, Algoritma, dan Pemrograman

• Permasalahan: kondisi yang harus diselesaikan atau ditemukan solusinya. Contoh: keluhan konsumen onlineshop terhadap lambatnya respon penjual.
• Algoritma: langkah-langkah sistematis untuk menyelesaikan permasalahan. Contoh: alur pembuatan kopi — siapkan bahan, masukkan kopi dan gula, tuang air, aduk, sajikan.
• Pemrograman: implementasi algoritma ke dalam bahasa pemrograman. Satu algoritma dapat diimplementasikan dengan berbagai bahasa pemrograman, tergantung kemampuan programmer.

3. Kebutuhan Efisiensi

• Efisiensi ruang dan waktu: solusi dikatakan efisien jika mampu memecahkan masalah dengan memperhatikan keterbatasan sumber daya.
• Struktur data menjadi solusi utama karena seluruh algoritma tidak terlepas dari struktur data.
• Partisi memori: memori utama dapat dipartisi menjadi beberapa disk terpisah untuk optimalisasi penyimpanan.

B. Interface Struktur Data

1. Interface Queue, Stack, dan Deque

• Queue (antrean): menggunakan konsep FIFO (First In First Out). Elemen pertama masuk = elemen pertama keluar. Analogi: antrean tiket kereta api.
  • Operasi: add(x)/enqueue(x) menambah elemen di awal, remove()/dequeue() menghapus elemen di akhir.
• Stack (tumpukan): menggunakan konsep LIFO (Last In First Out). Elemen terakhir masuk = elemen pertama keluar. Analogi: tumpukan koin dalam pipa tertutup bawah.
  • Operasi: push(x) menambah elemen, pop() menghapus elemen.
• Deque (Double-Ended Queue): dapat menambah dan menghapus elemen di depan maupun belakang. Menggunakan konsep FIFO dan LIFO.
  • Operasi: addFirst(x), removeFirst(), addLast(x), removeLast().

2. List Interface

• List: merepresentasikan urutan elemen x0 sampai xn-1.
  • Operasi: size() mengembalikan panjang list, get(i) mengembalikan nilai xi, set(i,x) mengatur nilai, add(i,x) menambah elemen pada posisi i, remove(i) menghapus elemen pada posisi i.
• Relasi dengan deque: addFirst(x) ≡ add(0,x), removeFirst() ≡ remove(0), addLast(x) ≡ add(size(),x), removeLast() ≡ remove(size()-1).

3. Interface USet dan SSet

• USet (Unordered Sets): himpunan elemen unik dan tidak terurut.
  • Operasi: size() jumlah elemen, add(x) menambah elemen, remove(x) menghapus, find(x) menemukan elemen.
• SSet (Sorted Sets): himpunan elemen yang terurut. Mendukung operasi compare(x,y).
  • Fungsi compare: menghasilkan nilai <0 jika x<y, >0 jika x>y, =0 jika x=y.
  • Perbedaan: SSet find(x) mencari x pada himpunan terurut, USet find(x) mencari pada himpunan tidak terurut.

---

Kegiatan Belajar 2: Matematika dan Struktur Data

A. Eksponensial dan Faktorial

1. Eksponensial (Perpangkatan)

• Notasi: a^n = a × a × a × ... sebanyak n kali, di mana a = basis/bilangan pokok, n = eksponen.
• Sifat penting: untuk a bilangan real dan a ≠ 0, maka a^0 = 1. Juga a^(-n) = 1/a^n.

2. Faktorial

• Notasi: n! = 1 × 2 × 3 × ... × n (untuk bilangan bulat positif n).
• Pendekatan Stirling: n! ≈ √(2πn) · (n/e)^n.
• Koefisien binomial: C(n,k) = n! / (k! · (n-k)!) untuk integer non-negatif n dan k ∈ {0, ..., n}.

B. Notasi Asimtotik (Big-Oh)

1. Konsep dan Perhitungan Big-Oh

• Big-Oh O(f(n)): notasi untuk menghitung kompleksitas waktu algoritma berdasarkan banyak iterasi n.
• Contoh coding:

void cBigOh() {
    for (int i = 0; i < n; i++)
        a[i] = i;
}

• Analisis: 1 perintah inisialisasi + (n+1) perbandingan + n perulangan + n array + n perintah = T(n) = a + b(n+1) + cn + dn + en → O(n).
• a, b, c, d, e adalah konstan yang bergantung pada machine running.

C. Nilai Acak dan Probabilitas

1. Random dan Probabilitas

• Expected value: E[X] = Σ x · Pr{X = x}, di mana x ∈ U (semesta pembicaraan).
• Contoh lempar koin: melempar koin k kali, peluang muncul kepala = E[X] = Σ (k choose i) · (1/2)^k = k/2.

D. Komputasi Struktur Data

1. Model Komputasi (word-RAM)

• word-RAM (w-bit): model komputasi Random Access Machine untuk menganalisis running time.
• Tiga operasi utama:
  • Aritmatika: +, -, ×, /, %
  • Perbandingan: <, >, =, ≤, ≥
  • Bitwise boolean: AND, OR, exclusive-OR (XOR)

2. Kompleksitas Komputasi — Tiga Pilar

• Correctness: interface struktur data harus diimplementasikan sesuai fungsinya.
• Time complexity: running time operasi sekecil mungkin.
• Space complexity: penggunaan memori sekecil mungkin.

3. Jenis Running Time

• Worst-case: operasi tidak sesuai target, melebihi f(n) yang diharapkan.
• Amortized: running time hampir mendekati target f(n), tidak terlalu melenceng.
• Expected: running time sesuai target f(n) yang diharapkan.

---

Kegiatan Belajar 3: Bahasa Pemrograman Java

A. Compiler

1. Pengertian Compiler

• Compiler: software untuk mengimplementasikan bahasa pemrograman tertentu menjadi program yang dapat dijalankan komputer.
• Bahasa Java merupakan bahasa pemrograman tingkat tinggi yang digunakan dalam mata kuliah struktur data.
• Contoh compiler Java: Netbeans, Eclipse, JCreator, BlueJ, Borland JBuilder. Modul ini menggunakan Netbeans + JDK.

B. Tipe Data dalam Java

1. Tipe Data Primitif

• Null: dapat dimiliki oleh setiap variabel, bernilai kosong.
• Boolean: bernilai true atau false.
• Integer: bilangan bulat. int = 32-bit (contoh: 176, -52). long = 64-bit diakhiri "L" (contoh: 176L, -52L).
• Floating point: bilangan desimal. double = default (contoh: 3.1415). float = diakhiri "F" (contoh: 3.14F). Notasi saintifik: 3.14E2, 19e10.
• Character: simbol individual. Contoh: 'a', '?'. Karakter khusus: \n (newline), \t (tab), \b (backspace), \r (return), \f (form feed), \\ (backslash), \' (single quote), \" (double quote).
• String: rangkaian karakter dalam kutip dua. Contoh: "dog cannot climb trees".

2. Tipe Data Abstrak (ADT)

• ADT: mendefinisikan bentuk logis tipe data; struktur data mengimplementasikan bentuk fisik.
• Relasi: Data Type → Data Items + Operations → Logical Form → Data Structure → Storage Space + Subroutines → Physical Form.
• Class: tempat menampung anak class, object, dan method.
  • Contoh: class "Jenis Kendaraan Bermotor" memiliki anak class:
    • Kendaraan Ringan: objek Mobil, method menampung 2-7 penumpang.
    • Kendaraan Berat: objek Truk (method: 2 penumpang + muat barang), objek Bus (method: 25-45 penumpang).
    • Sepeda Motor: objek Motor, method menampung 1 penumpang.

3. Tipe Data Koleksi

• Array: variabel bertipe data sejenis berderet dengan alamat memori bersebelahan. Memiliki elemen (e0, e1, e2) dan indeks (0, 1, 2). Contoh: array 1 baris × 3 kolom.
• List: untaian/rangkaian data yang dibaca komputer. Implementasi Java berupa linked list.
  • Komponen: node (head, next, tail), elemen (data), pointer (penunjuk arah ke node berikutnya).
  • Struktur: head → elemen|next → elemen|next → ... → tail.