1. Pendahuluan

Keterbatasan Array

⚠️ Keterbatasan Array

💡 Solusi: Linked List

2. Konsep Linked List

Komponen Penyusun

📦 Struktur Node

🖼️ Visualisasi Node

Node terdiri dari data (nilai) dan next (pointer ke node berikutnya)

🔑 Komponen Penting

🔗 Single Linked List

Traversal hanya dapat dilakukan satu arah: head → tail

3. Array vs Linked List

Perbandingan Karakteristik

💾 Penyimpanan di Memori

📊 Perbandingan Kompleksitas

* jika ada ruang   ** dengan tail pointer

⚖️ Kapan Menggunakan?

🎖️ Studi Kasus Pertahanan

4. Implementasi Node

Kode C++

💻 Struct Node

struct Node {
    int data;       // Data yang disimpan
    Node* next;     // Pointer ke node berikutnya
    
    // Constructor
    Node(int value) : data(value), next(nullptr) {}
};
                    

🔨 Membuat Node Baru

// Menggunakan constructor
Node* newNode = new Node(10);

// Atau secara manual
Node* anotherNode = new Node;
anotherNode->data = 20;
anotherNode->next = nullptr;
                    

🧪 Contoh: Membuat Linked List

// Buat tiga node
Node* node1 = new Node(5);
Node* node2 = new Node(10);
Node* node3 = new Node(15);

// Hubungkan node-node
node1->next = node2;  // node1 -> node2
node2->next = node3;  // node2 -> node3
// node3->next sudah nullptr

// Set head
Node* head = node1;
                    

5. Operasi Linked List

Traversal & Display

🚶 Traversal

void display(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL" << endl;
}
                    

Kompleksitas: O(n)

5. Operasi Linked List

Insert Operations

➕ Insert di Awal

void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}
                    

O(1)

🖼️ Visualisasi Insert di Awal

✏️ Contoh Insert di Awal

Sebelum:

insertAtBeginning(5)

➕ Insert di Akhir

void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node(value);
    
    // Kasus list kosong
    if (head == nullptr) {
        head = newNode;
        return;
    }
    
    // Traversal ke node terakhir
    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    
    // Hubungkan
    current->next = newNode;
}
                    

O(n) tanpa tail pointer

🖼️ Visualisasi Insert di Akhir

➕ Insert di Posisi Tertentu

void insertAtPosition(Node*& head, int value, int pos) {
    if (pos == 0) { insertAtBeginning(head, value); return; }
    
    // Traversal ke posisi (pos - 1)
    Node* prev = head;
    for (int i = 0; i < pos - 1; i++) {
        prev = prev->next;
    }
    
    // Sisipkan node baru
    Node* newNode = new Node(value);
    newNode->next = prev->next;
    prev->next = newNode;
}
                    

O(n)

🖼️ Visualisasi Insert di Tengah

5. Operasi Linked List

Delete Operations

➖ Delete di Awal

void deleteAtBeginning(Node*& head) {
    if (head == nullptr) 
        throw runtime_error("List kosong!");
    
    Node* temp = head;      // Simpan node
    head = head->next;      // Update head
    delete temp;            // Hapus node
}
                    

O(1)

⚠️ Kesalahan Umum Delete

delete head;
head = head->next;  // ❌ UNDEFINED BEHAVIOR!
                        

Node* temp = head;
head = head->next;  // ✅ Update dulu
delete temp;        // ✅ Baru hapus
                        

🖼️ Visualisasi Delete di Awal

➖ Delete di Akhir

void deleteAtEnd(Node*& head) {
    if (head == nullptr) throw runtime_error("List kosong!");
    
    // Kasus hanya satu node
    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }
    
    // Traversal ke node kedua terakhir
    Node* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    
    delete current->next;
    current->next = nullptr;
}
                    

O(n)

🧠 Quiz: Kondisi Loop

5. Operasi Linked List

Search & Find

🔍 Search

bool search(Node* head, int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;  // Ditemukan
        }
        current = current->next;
    }
    return false;  // Tidak ditemukan
}
                    

O(n) - worst case semua node

🎯 Two Pointer Technique

Mencari elemen ke-k dari belakang dengan satu kali traversal:

int findKthFromEnd(Node* head, int k) {
    Node* fast = head;
    Node* slow = head;
    
    // Majukan fast k langkah
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }
    
    // Majukan bersamaan sampai fast = NULL
    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow->data;
}
                    

🖼️ Two Pointer Visualization

6. Ringkasan Kompleksitas

Big-O Analysis

📊 Kompleksitas Waktu

⚖️ Keunggulan vs Kelemahan

🎖️ 7. Aplikasi Pertahanan

Studi Kasus Militer

📡 Radar Log Buffer

Sistem log aktivitas radar dengan circular buffer:

struct RadarLog {
    time_t timestamp;
    string activity;
    RadarLog* next;
};

class RadarLogBuffer {
private:
    RadarLog* head;
    RadarLog* tail;
    int maxSize, currentSize;
public:
    void addLog(string activity); // O(1)
    void displayLogs();           // O(n)
};
                    

Ketika penuh, data lama otomatis tertimpa!

🛡️ Aplikasi Lainnya

• Manajemen Antrian Pesan
  Pesan komunikasi militer (FIFO)
• Tracking Target
  Daftar pesawat/kapal yang terdeteksi radar
• Undo History
  Sistem command & control (LIFO)
• Sensor Network
  Linked list sensor di perimeter pertahanan