🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

1. Mengimplementasikan Double Linked List beserta operasinya
2. Mengimplementasikan Single Circular Linked List
3. Mengimplementasikan Double Circular Linked List
4. Memahami konsep Sentinel Node dan Iterator
5. Memilih jenis linked list yang tepat untuk kasus tertentu

📋 Agenda

📖 Apa itu Double Linked List?

🖼️ Struktur Double Linked List

🔗

p04-01-double-linked-list-structure.png

Double Linked List dengan pointer HEAD, TAIL, dan koneksi bidirectional

💡 Aplikasi Double Linked List

💻 Struktur Node DLL

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

💻 Class Double Linked List

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;
    int size;
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    void insertFront(int value);
    void insertBack(int value);
    void deleteFront();
    void deleteBack();
    void displayForward();
    void displayBackward();
    
    int getSize() const { return size; }
    bool isEmpty() const { return size == 0; }
};
                

➕ Insert di Depan (insertFront)

void DoublyLinkedList::insertFront(int value) {
    Node* newNode = new Node(value);
    
    if (head == nullptr) {
        head = tail = newNode;  // List kosong
    }
    else {
        newNode->next = head;   // Node baru → head lama
        head->prev = newNode;   // Head lama ← node baru
        head = newNode;         // Update head
    }
    size++;
}
                

➕ Insert di Belakang (insertBack)

void DoublyLinkedList::insertBack(int value) {
    Node* newNode = new Node(value);
    
    if (tail == nullptr) {
        head = tail = newNode;  // List kosong
    }
    else {
        newNode->prev = tail;   // Node baru ← tail lama
        tail->next = newNode;   // Tail lama → node baru
        tail = newNode;         // Update tail
    }
    size++;
}
                

🖼️ Insert di Tengah DLL

➕

p04-02-dll-insert-middle.png

Proses insert node di tengah dengan 4 langkah pointer manipulation

➕ Insert pada Posisi Tertentu

void DoublyLinkedList::insertAt(int value, int position) {
    if (position < 0 || position > size) return;
    if (position == 0) { insertFront(value); return; }
    if (position == size) { insertBack(value); return; }
    
    Node* newNode = new Node(value);
    Node* current;
    
    // Traversal optimal: dari depan atau belakang
    if (position <= size / 2) {
        current = head;
        for (int i = 0; i < position; i++) current = current->next;
    } else {
        current = tail;
        for (int i = size - 1; i > position; i--) current = current->prev;
    }
    
    // Insert sebelum current
    newNode->next = current;
    newNode->prev = current->prev;
    current->prev->next = newNode;
    current->prev = newNode;
    size++;
}
                

➖ Delete di Depan dan Belakang

void deleteFront() {
  if (head == nullptr) return;
  Node* temp = head;
  
  if (head == tail) {
    head = tail = nullptr;
  } else {
    head = head->next;
    head->prev = nullptr;
  }
  delete temp;
  size--;
}
                        

void deleteBack() {
  if (tail == nullptr) return;
  Node* temp = tail;
  
  if (head == tail) {
    head = tail = nullptr;
  } else {
    tail = tail->prev;
    tail->next = nullptr;
  }
  delete temp;
  size--;
}
                        

O(1) Keduanya konstan — deleteBack() DLL lebih cepat dari SLL!

📊 Perbandingan SLL vs DLL

📖 Circular Linked List

🖼️ Visualisasi Circular Linked List

🔄

p04-03-circular-linked-list.png

Single Circular LL (atas) dan Double Circular LL (bawah)

💡 Aplikasi Circular Linked List

💻 Single Circular Linked List

class CircularLinkedList {
private:
    Node* tail;   // Menggunakan TAIL untuk efisiensi
    int size;
    
public:
    CircularLinkedList() : tail(nullptr), size(0) {}
    
    // HEAD dapat diakses via tail->next
    Node* getHead() const {
        return (tail == nullptr) ? nullptr : tail->next;
    }
    
    void insertFront(int value);
    void insertBack(int value);
    void display();
};
                

➕ Insert pada Single Circular LL

void CircularLinkedList::insertFront(int value) {
    Node* newNode = new Node(value);
    
    if (tail == nullptr) {
        tail = newNode;
        newNode->next = newNode;  // Menunjuk ke diri sendiri
    } else {
        newNode->next = tail->next;  // Node baru → head lama
        tail->next = newNode;         // Tail → node baru (head baru)
    }
    size++;
}

void CircularLinkedList::insertBack(int value) {
    insertFront(value);   // Insert di depan
    tail = tail->next;    // Geser tail ke node baru
}
                

O(1) Keduanya konstan berkat penggunaan tail

🔄 Traversal Circular Linked List

void CircularLinkedList::display() {
    if (tail == nullptr) { cout << "List kosong!"; return; }
    
    Node* current = tail->next;  // Mulai dari head
    do {
        cout << current->data;
        current = current->next;
        if (current != tail->next) cout << " -> ";
    } while (current != tail->next);  // Berhenti di head
    
    cout << " -> (kembali ke " << tail->next->data << ")" << endl;
}
                

💻 Double Circular Linked List

Menggabungkan keuntungan DLL dan Circular LL:

• ✅ Traversal dua arah
• ✅ Tidak ada NULL pointer
• ✅ Insert/Delete di kedua ujung O(1)

p04-04-dcll-operations.png

➕ Insert pada Double Circular LL

void DoublyCircularLinkedList::insertFront(int value) {
    Node* newNode = new Node(value);
    
    if (head == nullptr) {
        head = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;  // Circular: menunjuk diri sendiri
    } else {
        Node* tail = head->prev;
        
        newNode->next = head;
        newNode->prev = tail;
        head->prev = newNode;
        tail->next = newNode;
        
        head = newNode;  // Update head
    }
    size++;
}
                

➖ Delete Node pada Double Circular LL

void DoublyCircularLinkedList::deleteNode(Node* node) {
    if (node == nullptr || head == nullptr) return;
    
    // Kasus hanya ada satu node
    if (node->next == node) {
        head = nullptr;
        delete node;
        size--;
        return;
    }
    
    // Hubungkan tetangga
    node->prev->next = node->next;
    node->next->prev = node->prev;
    
    if (node == head) head = node->next;
    
    delete node;
    size--;
}
                

O(1) Jika sudah punya pointer ke node target!

🛡️ Sentinel Node

🖼️ DLL dengan Sentinel Node

🛡️

p04-05-sentinel-node.png

Sentinel HEAD dan TAIL mengapit data nodes

💻 Implementasi dengan Sentinel

class DoublyLinkedListWithSentinel {
private:
    Node* sentinelHead;
    Node* sentinelTail;
    
public:
    DoublyLinkedListWithSentinel() {
        sentinelHead = new Node(0);
        sentinelTail = new Node(0);
        sentinelHead->next = sentinelTail;
        sentinelTail->prev = sentinelHead;
    }
    
    void insertAfter(Node* node, int value) {
        Node* newNode = new Node(value);
        newNode->next = node->next;
        newNode->prev = node;
        node->next->prev = newNode;
        node->next = newNode;
    }
    
    void insertFront(int value) { insertAfter(sentinelHead, value); }
    void insertBack(int value) { insertAfter(sentinelTail->prev, value); }
};
                

🔄 Iterator pada Linked List

💻 Penggunaan Iterator

// Forward traversal
cout << "Forward: ";
for (auto it = dll.begin(); it != dll.end(); ++it) {
    cout << *it << " ";
}

// Backward traversal
cout << "Backward: ";
for (auto it = dll.rbegin(); it != dll.rend(); --it) {
    cout << *it << " ";
}

// Modifikasi dengan iterator
for (auto it = dll.begin(); it != dll.end(); ++it) {
    *it *= 2;  // Gandakan setiap nilai
}
                

🎵 Studi Kasus: Music Playlist

Implementasi playlist dengan Double Circular Linked List:

struct Song {
    string title;
    string artist;
    Song* prev;
    Song* next;
};

class MusicPlaylist {
    Song* current;  // Lagu yang sedang diputar
    
    void next() { current = current->next; }
    void previous() { current = current->prev; }
    void addSong(string title, string artist);
    void removeCurrent();
};
                

✅ Loop otomatis | ✅ Prev/Next O(1) | ✅ Ins/Rmv O(1)

🐢🐇 Floyd's Cycle Detection

Mendeteksi cycle dalam linked list dengan O(n) waktu dan O(1) ruang:

bool hasCycle(Node* head) {
    if (head == nullptr) return false;
    
    Node* slow = head;        // Tortoise: 1 langkah
    Node* fast = head->next;  // Hare: 2 langkah
    
    while (fast != nullptr && fast->next != nullptr) {
        if (slow == fast) return true;  // Bertemu = ada cycle
        
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;  // Tidak ada cycle
}
                

🖼️ Floyd's Algorithm Visualized

🐢🐇

p04-07-floyd-cycle-detection.png

Slow (1 langkah) dan Fast (2 langkah) bertemu dalam cycle

📝 Ringkasan

🤔 Kapan Menggunakan?

🧠 Quiz

⭐ Poin Penting

1. DLL menggunakan lebih banyak memori (3 field vs 2)
2. Pada circular list, gunakan do-while untuk traversal
3. Sentinel node menghilangkan edge case checking
4. Floyd's algorithm: O(n) waktu, O(1) ruang

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.10.2 | Weiss Ch.3 | Hubbard Ch.7

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 04: Double dan Circular Linked List

© 2026 - CC BY 4.0