Wie ich über eine doppelt verknüpfte Liste für O (1) debattierte

Einmal sah ich versehentlich, wie mein Kollege die Junior-Aufgabe löste, eine doppelt verknüpfte Liste in C ++ zu erweitern. Und in diesem Moment kam es mir nicht seltsam vor, dass er eine Führungspersönlichkeit war und aus dieser längst herausgewachsen war, sondern die Entscheidung selbst.

Eher nicht.

Die Lösung war Standard: die gleiche lineare Passage mit dem Ersetzen von Zeigern in jedem Knoten, wie Hunderttausende von Menschen davor geschrieben haben. Nichts Ungewöhnliches oder Kompliziertes, aber als ich ihn ansah, hatte ich zwei Fragen:

• Warum löst standardmäßig jeder das Problem auf diese Weise?
• Ist es möglich, es besser zu machen?

Kurz über das Material. Wenn Sie wissen, was eine doppelt verknüpfte Liste ist, können Sie den nächsten Absatz überspringen.

Eine doppelt verknüpfte Liste ist eine der grundlegenden Datenstrukturen, deren Kenntnis in der Regel in der Frühphase des Programmiertrainings erfolgt. Dies ist eine Sammlung, die aus einer Folge von Knoten besteht, die einige Daten enthalten und miteinander gepaart sind. Wenn also Knoten A als Nächstes auf B verweist, verweist Knoten B als Vorheriges auf A. In der Praxis finden Sie diese Struktur möglicherweise in Containern wie std :: list in C ++, LinkedList in C # und Java. Höchstwahrscheinlich finden Sie die Implementierung in der Standardbibliothek einer anderen Sprache.

Weiter im Text werden die grundlegenden Eigenschaften und Operationen auf einer solchen Liste mit der Angabe der Rechenkomplexität beschrieben.

Nun zurück zu den zuvor gestellten Fragen.

Ich habe den Zustand des Problems untersucht und die Antwort auf die erste Frage gefunden. Da ist er:

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

. - .