📖 1. Pengantar Struktur Data

Aspek Penting Struktur Data

🎖️ Contoh: Sistem C6ISR

Sistem yang mengelola ribuan data posisi unit militer secara real-time:

📊 Klasifikasi Struktur Data

Gambar 1.4: Klasifikasi struktur data — Linear vs Non-Linear

Linear vs Non-Linear

📖 2. Abstract Data Type (ADT)

ADT vs Struktur Data Konkret

Komponen ADT

Contoh: ADT Stack

ADT Stack:
  Data:
    - Kumpulan elemen dengan tipe T
    
  Operasi:
    - push(item): Menambah item ke puncak stack
    - pop(): Menghapus dan mengembalikan item dari puncak
    - peek()/top(): Melihat item di puncak tanpa menghapus
    - isEmpty(): Mengecek apakah stack kosong
    
  Aturan:
    - LIFO (Last In First Out)
    - push lalu pop mengembalikan item yang sama
    - pop pada stack kosong menghasilkan error
                    

Manfaat ADT

1. Abstraksi — Pengguna tidak perlu tahu detail implementasi
2. Enkapsulasi — Detail internal tersembunyi dan terlindungi
3. Modularitas — Komponen dapat dikembangkan secara independen
4. Reusabilitas — ADT yang sama dapat diimplementasikan dengan berbagai cara
5. Maintainability — Perubahan implementasi tidak mempengaruhi kode pengguna

🧠 Quiz: ADT Queue

📖 3. Review Pointer dalam C++

💻 Contoh Dasar Pointer

int main() {
    int nilai = 42;        // Variabel biasa
    int* ptr = &nilai;     // Pointer menyimpan alamat 'nilai'
    
    cout << "Nilai variabel: " << nilai << endl;      // 42
    cout << "Alamat variabel: " << &nilai << endl;    // 0x7ffd...
    cout << "Nilai pointer: " << ptr << endl;         // 0x7ffd...
    cout << "Nilai yang ditunjuk: " << *ptr << endl;  // 42
    return 0;
}
                    

Operator Pointer

Pointer Arithmetic

Gambar 1.1: Ilustrasi pointer arithmetic pada array integer

int arr[5] = {10, 20, 30, 40, 50};
int* ptr = arr;

ptr++;      // Pindah ke elemen berikutnya (+sizeof(int))
ptr += 2;   // Pindah 2 elemen ke depan
                    

🧠 Quiz: Output Pointer

int x = 10;
int* p = &x;
*p = 20;
cout << x << endl;
                        

💻 Fungsi Tukar dengan Pointer

void tukar(int* a, int* b) {
    int temp = *a;  // Simpan nilai di alamat a
    *a = *b;        // Copy nilai di alamat b ke alamat a
    *b = temp;      // Copy temp ke alamat b
}

int main() {
    int x = 5, y = 10;
    tukar(&x, &y);  // Kirim alamat x dan y
    // Hasil: x = 10, y = 5
}
                    

📖 4. Referensi dalam C++

int nilai = 42;
int& ref = nilai;   // ref adalah alias untuk nilai

ref = 100;          // Sama dengan nilai = 100
cout << nilai;      // Output: 100
                    

Pointer vs Referensi

💻 Pass by Reference

// Pass by value - tidak mengubah variabel asli
void tambahSatu_nilai(int x) {
    x = x + 1;
}

// Pass by reference - mengubah variabel asli
void tambahSatu_ref(int& x) {
    x = x + 1;
}

int main() {
    int a = 5, b = 5;
    tambahSatu_nilai(a);  // a tetap 5
    tambahSatu_ref(b);    // b jadi 6
}
                    

📖 5. Dynamic Memory Allocation

Stack vs Heap Memory

Gambar 1.2: Perbandingan Stack dan Heap Memory

Karakteristik Stack vs Heap

Operator new dan delete

int main() {
    // Alokasi single variable
    int* ptr = new int;      // Alokasi memori untuk satu integer
    *ptr = 42;
    delete ptr;              // Dealokasi memori
    
    // Alokasi dengan inisialisasi
    int* ptr2 = new int(100);
    delete ptr2;
    return 0;
}
                    

💻 Alokasi Array Dinamis

int main() {
    int ukuran;
    cin >> ukuran;
    int* arr = new int[ukuran];  // Alokasi array dinamis
    
    // Mengisi dan menggunakan array
    for (int i = 0; i < ukuran; i++) {
        arr[i] = i * 10;
    }
    
    // PENTING: gunakan delete[] untuk array!
    delete[] arr;
    return 0;
}
                    

delete vs delete[]

// Single object
int* single = new int(42);
delete single;  // ✅ BENAR

// Array
int* arr = new int[10];
delete[] arr;   // ✅ BENAR
                    

📖 6. Memory Problems

Memory Leak & Dangling Pointer

Gambar 1.3: Ilustrasi Memory Leak dan Dangling Pointer

Memory Leak

void fungsiMasalah() {
    int* data = new int[1000];
    // ... melakukan operasi ...
    // ❌ MASALAH: fungsi berakhir tanpa delete[]
    // Memori 1000 integer hilang!
}

int main() {
    for (int i = 0; i < 100000; i++) {
        fungsiMasalah();  // Setiap panggilan = memory leak
    }
    // Program mungkin kehabisan memori!
}
                    

Penyebab Memory Leak

1. Lupa memanggil delete atau delete[]
2. Exception terjadi sebelum dealokasi
3. Pointer di-reassign tanpa dealokasi terlebih dahulu
4. Return dari fungsi sebelum dealokasi

Dangling Pointer

int* buatDangling() {
    int lokal = 42;
    return &lokal;  // ❌ BAHAYA! mengembalikan alamat variabel lokal
}  // lokal dihancurkan saat fungsi berakhir

int main() {
    int* ptr = new int(100);
    delete ptr;     // Memori didealokasi
    cout << *ptr;   // ❌ UNDEFINED BEHAVIOR - dangling pointer!
}
                    

✅ Praktik Terbaik

int main() {
    int* ptr = nullptr;  // 1. Selalu inisialisasi pointer
    
    if (ptr != nullptr) {  // 2. Periksa sebelum menggunakan
        cout << *ptr << endl;
    }
    
    ptr = new int(42);
    delete ptr;
    ptr = nullptr;  // 3. Set ke nullptr setelah delete
    return 0;
}
                    

📖 7. Pengenalan Smart Pointer

Raw pointer memiliki beberapa masalah:

• Tidak jelas siapa yang "memiliki" memori
• Mudah lupa dealokasi
• Exception safety sulit dicapai

Smart Pointer di C++11

💻 Contoh unique_ptr

#include <memory>

int main() {
    unique_ptr<int> ptr1(new int(42));
    cout << "Nilai: " << *ptr1 << endl;
    
    // unique_ptr tidak bisa di-copy
    // unique_ptr<int> ptr2 = ptr1;  // ❌ ERROR!
    
    // Tapi bisa di-move
    unique_ptr<int> ptr2 = move(ptr1);
    // ptr1 sekarang nullptr
    
    // Otomatis dealokasi saat keluar scope!
    return 0;
}
                    

Keuntungan Smart Pointer

// Smart pointer - aman
void fungsiSmart() {
    unique_ptr<int> ptr(new int(42));
    // Jika exception, ptr tetap 
    // dealokasi otomatis!
    riskyOperation();
    // Tidak perlu delete
}
                            

📖 8. Array Dinamis

Keterbatasan Array Statis

• Ukuran harus diketahui saat compile time
• Tidak dapat berubah setelah deklarasi
• Membuang memori jika tidak digunakan penuh

int arrStatis[100];  // Selalu menggunakan memori untuk 100 int
                     // Tidak bisa diperbesar
                    

Konsep Array Dinamis

Strategi lipat dua memberikan amortized O(1) untuk operasi tambah.

Proses Penghapusan Elemen

Gambar 1.5: Ilustrasi proses penghapusan elemen pada array dinamis

Kompleksitas waktu: O(n) karena perlu menggeser elemen

💻 Struktur Class ArrayDinamis

class ArrayDinamis {
private:
    int* data;
    int ukuran;     // Jumlah elemen saat ini
    int kapasitas;  // Total kapasitas array

public:
    ArrayDinamis(int kapasitasAwal = 10) {
        kapasitas = kapasitasAwal;
        ukuran = 0;
        data = new int[kapasitas];
    }
    
    ~ArrayDinamis() {
        delete[] data;  // Destructor - dealokasi
    }
    
    void tambah(int nilai);  // Tambah elemen
    int ambil(int index);    // Akses elemen
    void hapus(int index);   // Hapus elemen
};