Bagaimana saya memperdebatkan daftar tertaut ganda untuk O (1)

Suatu kali saya tidak sengaja melihat kolega saya menyelesaikan tugas junior untuk memperluas daftar yang tertaut ganda di C ++. Dan pada saat itu bagiku terasa aneh bukan karena dia seorang yang memimpin dan sudah terlalu besar dalam hal ini, tetapi keputusan itu sendiri.

Lebih tepatnya, tidak begitu.

Solusinya standar: jalur linier yang sama dengan penggantian pointer di setiap node, seperti yang ditulis oleh ratusan ribu orang sebelumnya. Tidak ada yang aneh atau rumit, tetapi ketika saya memandangnya, saya memiliki dua pertanyaan:

• Mengapa secara default semua orang memecahkan masalah dengan cara ini?
• Apakah mungkin melakukan lebih baik?

Secara singkat tentang materiel. Jika Anda tahu apa daftar yang ditautkan dua kali lipat, Anda dapat melewati paragraf berikutnya.

Daftar tertaut ganda adalah salah satu struktur data dasar, kenalannya biasanya terjadi pada tahap awal pelatihan pemrograman. Ini adalah kumpulan yang terdiri dari urutan node yang berisi beberapa data dan dipasangkan satu sama lain - yaitu, jika simpul A merujuk ke B sebagai yang berikutnya, maka simpul B merujuk ke A sebagai yang sebelumnya. Dalam praktiknya, Anda mungkin menemukan struktur ini dalam wadah seperti std :: list di C ++, LinkedList di C #, dan Java. Kemungkinan besar, Anda akan menemukan implementasinya di perpustakaan standar bahasa lain.

Lebih lanjut dalam teks, sifat dasar dan operasi pada daftar tersebut dengan indikasi kompleksitas komputasi akan dijelaskan.

Sekarang kembali ke pertanyaan yang disuarakan sebelumnya.

Saya melihat ke dalam kondisi masalah dan melihat jawaban untuk yang pertama. Ini dia:

struct node
{
    int data;
    node* next;
    node* prev;
};

. ? :



. ― , . , , .

EBDCA. ― , . .

, , , , O(1), . , . , .

. , , :

• , .
• . , .
• . , .
• .
• (/ //) .
• / , .
• – . , .

― . ― / . , - . , . , - , , , - .

«? -?» ― : « !»

, , - - . , : , . Data-Oriented Design: , , , . DOD. . , , .

, , . . .

, -, . , «» . :

• / , .
• - , . -.

, . , . , - O(1), .

― (SoA) (AoS), . :



? :

― . data, prev/next.
/ -.

, ― , prev next . - . .

, ?

ACDBE. EBDCA, :



! , , , , .

, prev next , first last , , :

prev <-> next
last <-> first

, . . . - , - .

, , :

template <class T, size_t Cap>
struct doubly_linked_list
{
    struct node { size_t index; };

    // API      

    T& get(node n) { return data_[n.index]; }
    const T& get(node n) const { return data_[n.index]; }

    node first() const { return { first_ }; }
    node last() const { return { last_ }; }

    node next(node n) const { return { next_[n.index] }; }
    node prev(node n) const { return { prev_[n.index] }; }

    bool is_valid(node n) const { return n.index < length_; }

    //          

    node add(T v)
    {
        auto index = length_;
        if (length_ == 0) first_ = 0;
        data_[index] = v;
        next_[index] = INVALID_INDEX;
        prev_[index] = last_;
        next_[last_] = index;
        last_ = index;
        length_++;
        return { index };
    }

    node insert_before(T v, node n)
    {
        auto index = length_;
        data_[index] = v;
        next_[index] = n.index;
        auto prev = prev_[index] = prev_[n.index];
        prev_[n.index] = index;
        next_[prev] = index;
        length_++;
        if (n.index == first_) first_ = index;
        return { index };
    }

    // …    ,          ,
    //      «»   .     add/insert_before -
    //   length_     «».

    //    – ,      :

    void reverse()
    {
            std::swap(first_, last_);
            std::swap(next_, prev_);
    }

private:
    static constexpr size_t INVALID_INDEX = SIZE_T_MAX;

    T data_[Cap];
    size_t indirection_[Cap * 2];
    size_t *next_ = indirection_;
    size_t *prev_ = indirection_ + Cap;
    size_t first_ = INVALID_INDEX;
    size_t last_ = INVALID_INDEX;
    size_t length_ = 0;
};

:

auto list = doubly_linked_list<int, 10>();
auto pos = list.add(0);
for (int i = 0; i < 5; ++i) pos = list.insert_before(i + 1, pos);

std::cout << "list";
for (auto n = list.first(); list.is_valid(n); n = list.next(n))
    std::cout << list.get(n) << " ";

// > list 5 4 3 2 1 0

list.reverse();
std::cout << std::endl << "reversed";
for (auto n = list.first(); list.is_valid(n); n = list.next(n))
    std::cout << list.get(n) << " ";

// > reversed 0 1 2 3 4 5

, , AoS . , : - , .

, . , - - ― , cache-friendly DCEL, . , .

:

. . . ― , . , , , – , .

Data-Oriented Design: , . . – , . , .

. - .