std::deque dan std::list

std::vector kita kuasai, tetapi ia punya dua titik lemah yang kini bisa kita rumuskan dengan tepat: menambah elemen di depan berarti menggeser seluruh isi, dan menyisip atau menghapus di tengah sama mahalnya. Dua container dirancang untuk menjawab kelemahan itu. std::deque (double-ended queue, dibaca “deck”) membuat kedua ujung sama cepatnya dengan ujung belakang vector, sedangkan std::list (doubly-linked list) membuat penyisipan dan penghapusan di posisi mana pun menjadi langkah konstan. Pada Chapter ini kita mencoba keduanya, membandingkannya dengan vector dalam satu tabel, dan merumuskan kapan masing-masing layak dipilih.

deque: Cepat di Kedua Ujung #

Di balik layar, std::deque menyimpan elemennya dalam beberapa blok memori yang diatur oleh satu peta kecil. Karena itu ia bisa menumbuhkan kapasitas di sisi depan maupun belakang tanpa menggeser elemen lama. Kita memperagakannya bersama fitur yang jarang disadari: deque juga mendukung akses acak dengan operator[] seperti vector.

#include <deque>     // std::deque: antrean dua ujung
#include <iostream>  // std::cout
#include <iterator>  // std::next: majukan iterator sejauh n langkah
#include <list>      // std::list: doubly-linked list
#include <string>    // std::string

void cetakDeque(const std::deque<int>& d, const std::string& label) {
    std::cout << label << ":";
    for (int x : d) std::cout << ' ' << x;
    std::cout << "\n";
}

void cetakList(const std::list<std::string>& l, const std::string& label) {
    std::cout << label << ":";
    for (const std::string& s : l) std::cout << ' ' << s;
    std::cout << "\n";
}

int main() {
    // --- deque: cepat di KEDUA ujung ---
    std::deque<int> antrean = {40, 50, 60};
    antrean.push_front(30);   // masuk di depan: murah pada deque
    antrean.push_back(70);    // masuk di belakang: juga murah
    cetakDeque(antrean, "deque        ");

    antrean.pop_front();      // buang 30 dari depan
    antrean.pop_back();       // buang 70 dari belakang
    cetakDeque(antrean, "dua ujung    ");

    // deque juga mendukung akses acak seperti vector
    std::cout << "d[1]         :" << ' ' << antrean[1] << "\n";

    // --- list: sisip/hapus di tengah lewat iterator ---
    std::list<std::string> playlist = {"Intro", "Outro"};
    auto posisi = std::next(playlist.begin());   // iterator ke elemen kedua
    playlist.insert(posisi, "Verse 1");          // sisip sebelum "Outro"
    playlist.insert(std::next(playlist.begin(), 2), "Chorus");
    cetakList(playlist, "playlist     ");

    auto target = std::next(playlist.begin());   // iterator ke "Verse 1"
    playlist.erase(target);                      // hapus di tengah: O(1)
    cetakList(playlist, "erase tengah ");

    return 0;
}

Output yang Dihasilkan:

deque        : 30 40 50 60 70
dua ujung    : 40 50 60
d[1]         : 50
playlist     : Intro Verse 1 Chorus Outro
erase tengah : Intro Chorus Outro

Mari kita bedah:

1. Baris 22-23 (push_front / push_back): deque menerima elemen baru di kedua ujung dengan biaya konstan. Setelah kedua operasi, urutannya 30 40 50 60 70 — elemen depan masuk lebih dulu dari yang belakang.
2. Baris 26-27 (pop_front / pop_back): membuang elemen dari kedua ujung juga konstan; hasilnya kembali {40, 50, 60}.
3. Baris 31 (antrean[1]): akses acak tetap tersedia dan cepat. Inilah pembeda utama deque dari list: elemen deque tersegel berurutan di memori sehingga posisi ke-n bisa dihitung langsung.
4. Baris 34-37 (menyisipkan di tengah list): std::next(playlist.begin()) menggeser iterator dua langkah ke elemen kedua — kita bahas std::next dan saudaranya lebih dalam pada Section Iterators dan Algorithms. insert menyisipkan sebelum posisi iterator, dan karena list berupa rantai simpul, penyisipan hanya menyambung ulang dua penunjuk.
5. Baris 40-41 (erase di tengah): penghapusan lewat iterator juga hanya melepas satu simpul dan menyambung rantainya. Tidak ada elemen yang digeser — berbeda total dari vector.

list: Tanpa Akses Acak #

Kekuatan std::list membawa konsekuensi yang pasti: ia tidak punya operator[]. Elemen list tersebar sebagai simpul-simpul terpisah di heap, saling terhubung lewat pointer prev dan next, sehingga mencapai elemen ke-n harus berjalan simpul demi simpul. Percobaan memakai angka[1] pada list ditolak compiler:

#include <iostream>
#include <list>

int main() {
    std::list<int> angka = {10, 20, 30};
    std::cout << angka[1] << "\n";   // TIDAK KOMPILASI: list tanpa akses acak
    return 0;
}

Kompilasi potongan di atas menghasilkan pesan kesalahan berikut:

error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int')

Kesalahan ini justru berkah: compiler mencegah kita menulis kode berbiaya tersembunyi. Jika program Anda sering menulis daftar[i], itu sinyal kuat bahwa yang dibutuhkan adalah std::vector atau std::deque, bukan list. Keunggulan list yang tersisa adalah stabilitas iterator: penyisipan dan penghapusan di mana pun tidak memindahkan simpul lain, sehingga iterator dan referensi ke elemen tetap sah setelah operasi tersebut.

Perbandingan vector, deque, dan list #

Sekarang ketiga container sekuensial bisa kita adu dalam satu tabel. Kompleksitas ditulis dengan notasi Big-O yang akan kita dalami pada Section Struktur Data dan Algoritma.

Tanda * pada list memiliki catatan penting: O(1) hanya berlaku setelah kita memegang iterator ke posisi tersebut. Mencari posisinya sendiri tetap O(n) karena list harus berjalan dari ujung. Jadi pola kerja yang pas untuk list adalah: pegang iteratornya, lalu sering sisip-hapus di sekitar posisi itu.

Dengan tiga container sekuensial ini, kita sudah bisa menampung data dalam banyak bentuk. Akan tetapi, ada pola pemakaian yang begitu umum — tumpukan dan antrean — sehingga standard library menyediakan pembungkus khusus untuknya; itulah topik Chapter berikutnya.

Rujukan resmi: cppreference — std::deque , cppreference — std::list .