मैंने O (1) के लिए दोगुनी लिंक की गई सूची पर बहस कैसे की

एक बार जब मैंने गलती से अपने सहकर्मी को C ++ में दोगुनी लिंक्ड सूची के विस्तार के कनिष्ठ कार्य को हल करने के लिए देखा। और उस पल मुझे यह अजीब नहीं लगा कि वह एक सीसा था और लंबे समय से इस बात को पछाड़ता रहा, लेकिन फैसला खुद ही हुआ।

अधिक सही मायने में, ऐसा नहीं है।

समाधान मानक था: प्रत्येक नोड में संकेत के प्रतिस्थापन के साथ एक ही रैखिक मार्ग, जैसा कि सैकड़ों हजारों लोगों ने पहले लिखा था। कुछ भी असामान्य या जटिल नहीं है, लेकिन जब मैंने उसकी ओर देखा, तो मेरे दो सवाल थे:

• डिफ़ॉल्ट रूप से हर कोई इस तरह से समस्या का समाधान क्यों करता है?
• क्या बेहतर करना संभव है?

संक्षेप में मैटरियल के बारे में। यदि आप जानते हैं कि दोहरी लिंक की गई सूची क्या है, तो आप अगले पैराग्राफ को छोड़ सकते हैं।

एक डबल लिंक की गई सूची बुनियादी डेटा संरचनाओं में से एक है, इसके साथ परिचित आमतौर पर प्रोग्रामिंग प्रशिक्षण के शुरुआती चरणों में होता है। यह नोड्स के अनुक्रम से बना एक संग्रह है जिसमें कुछ डेटा होते हैं और एक दूसरे के साथ जोड़े जाते हैं - अर्थात, यदि नोड A को अगले के रूप में संदर्भित करता है, तो नोड B पिछले के रूप में A को संदर्भित करता है। व्यवहार में, आपको यह संरचना कंटेनरों में मिल सकती है जैसे कि std :: C ++ में सूची, C # में लिंक्डलिस्ट, और जावा। सबसे अधिक संभावना है, आपको इसका कार्यान्वयन किसी अन्य भाषा के मानक पुस्तकालय में मिलेगा।

पाठ में आगे, कम्प्यूटेशनल जटिलता के संकेत के साथ ऐसी सूची पर मूल गुणों और संचालन का वर्णन किया जाएगा।

अब पहले दिए गए प्रश्नों पर वापस जाएं।

मैंने समस्या की स्थिति पर ध्यान दिया और पहले का जवाब देखा। यहाँ यह है:

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: , . . – , . , .

. - .