C++ list ve deque ile Sıralı Veri Yapıları

C++’taki std::list ve std::deque, std::vector’a alternatif olarak belirli durumlarda daha verimli davranan sıralı veri yapılarıdır. std::list, çift bağlı liste (doubly linked list) yapısı sunarken; std::deque, iki uçlu kuyruk (double-ended queue) olarak hem başa hem sona hızlı ekleme/silme imkanı sağlar. Bu makalede hangi durumda hangisinin kullanılacağı ve performans özellikleri örneklerle anlatılmaktadır.

1) std::list Nedir?

std::list, çift yönlü bağlı liste yapısıdır:

• Her eleman ayrı bir düğümde saklanır.
• Her düğüm bir önceki ve bir sonraki elemana işaret eder.
• Orta bir yere eleman ekleme/silme O(1) maliyetle gerçekleşir.
• Rastgele erişim yoktur (v[i] kullanılamaz) → sadece iterasyonla erişilir.

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> lst = {10, 20, 30};

    lst.push_front(5);   // başa ekleme
    lst.push_back(40);   // sona ekleme

    auto it = lst.begin(); 
    advance(it, 2);      // 2 adım ileri git
    lst.insert(it, 25);  // araya ekleme

    for (int x : lst) cout << x << " ";
}

Kullanım Alanı: Liste içinde sık sık araya ekleme/silme işlemleri yapılıyorsa (özellikle ortada).

2) std::list Performans Özellikleri

• Araya ekleme/silme: O(1)
• Baştan/sondan ekleme/silme: O(1)
• Sıralama (list.sort()): O(n log n) ancak veri taşımak ucuzdur.
• Rastgele erişim (random access): Yok
• Bellek tüketimi: Vector’e göre daha yüksek (düğümler ekstra pointer içerir)

// list üzerinde sıralama
list<int> lst = {5, 2, 9, 1};
lst.sort();      // kendi sort algoritması vardır

3) std::deque Nedir?

std::deque (double-ended queue), hem başta hem sonda hızlı ekleme/silme yapabilen dinamik bir yapıdır.

• Hem başa hem sona O(1) ekleme/silme.
• Rastgele erişim O(1) (vector gibi).
• Orta ekleme/silme O(n).
• Bellek, vector gibi tamamen bitişik değildir; segmentlere bölünmüş yapıdadır.

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<int> dq = {10, 20, 30};

    dq.push_front(5);    // başa hızlı ekleme
    dq.push_back(40);    // sona hızlı ekleme

    dq.pop_front();
    dq.pop_back();

    cout << dq[0] << endl;   // rastgele erişim mümkün
}

Kullanım Alanı: Hem başa hem sona sık ekleme/silme ihtiyacı varsa.

4) std::deque Performans Özellikleri

• Başa ekleme/silme: O(1)
• Sona ekleme/silme: O(1)
• Orta ekleme/silme: O(n)
• Rastgele erişim: O(1)
• Bellek düzeni: parçalı (chunked), vector kadar cache-dostu değildir

5) list ve deque Karşılaştırması

6) Uygulamalı Örnek: Kuyruk ve İş Listesi

a) deque ile görev kuyruğu (task queue)

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<string> tasks;

    tasks.push_back("Download");
    tasks.push_back("Parse");
    tasks.push_front("Init"); // öncelikli görev

    while (!tasks.empty()) {
        cout << "Görev: " << tasks.front() << endl;
        tasks.pop_front();
    }
}

b) list ile oyun sahnesi nesne yönetimi

Oyun motorlarında sahnedeki nesneler sık sık eklenip çıkarıldığı için list tercih edilir.

#include <list>
#include <iostream>
using namespace std;

struct Entity {
    string name;
    Entity(string n) : name(n) {}
};

int main() {
    list<Entity> entities;

    entities.emplace_back("Player");
    entities.emplace_back("Enemy");
    entities.emplace_back("Tree");

    // Düşman yok edildi
    for (auto it = entities.begin(); it != entities.end(); ) {
        if (it->name == "Enemy")
            it = entities.erase(it); // O(1)
        else
            ++it;
    }

    for (auto& e : entities)
        cout << e.name << endl;
}

7) Hangi Durumda Hangisi?

• list → Araya sık ekleme/silme yapılacaksa.
• deque → Başa ve sona hızlı erişim gerekiyorsa.
• vector → Rastgele erişim ve yüksek cache performansı önemliyse.

Yani genel öneri: Önce vector düşünün; sonra ihtiyaç varsa deque veya list’e geçin.

8) TL;DR

İlişkili Makaleler