Comment j'ai débattu d'une liste doublement liée pour O (1)

Une fois, j'ai accidentellement vu mon collègue résoudre la tâche junior d'élargir une liste doublement liée en C ++. Et à ce moment-là, il me semblait étrange non pas qu'il soit un leader et qu'il ait longtemps dépassé ce stade, mais la décision elle-même.

Plus vraiment, non.

La solution était standard: le même passage linéaire avec le remplacement des pointeurs dans chaque nœud, comme l'ont écrit des centaines de milliers de personnes avant lui. Rien d'inhabituel ni de compliqué, mais quand je l'ai regardé, j'avais deux questions:

• Pourquoi par défaut tout le monde résout-il le problème de cette façon?
• Est-il possible de faire mieux?

Brièvement sur le matériel. Si vous savez ce qu'est une liste doublement liée, vous pouvez ignorer le paragraphe suivant.

Une liste doublement couplée est l'une des structures de données de base; sa connaissance se produit généralement dans les premiers stades de la formation en programmation. Il s'agit d'une collection constituée d'une séquence de nœuds qui contiennent des données et sont associés les uns aux autres - c'est-à-dire, si le nœud A fait référence à B comme le suivant, alors le nœud B fait référence à A comme le précédent. En pratique, vous pouvez trouver cette structure dans des conteneurs tels que std :: list en C ++, LinkedList en C # et Java. Très probablement, vous trouverez son implémentation dans la bibliothèque standard de toute autre langue.

Plus loin dans le texte, les propriétés et opérations de base sur une telle liste avec l'indication de la complexité de calcul seront décrites.

Revenons maintenant aux questions posées plus tôt.

J'ai examiné l'état du problème et j'ai vu la réponse au premier. Le voici:

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

. - .