Como debati uma lista duplamente vinculada de O (1)

Uma vez, vi acidentalmente meu colega resolver a tarefa júnior de expandir uma lista duplamente vinculada em C ++. E naquele momento me pareceu estranho não que ele fosse um líder e já superasse isso há muito tempo, mas a própria decisão.

Mais verdadeiramente, não é assim.

A solução era padrão: a mesma passagem linear com a substituição de ponteiros em cada nó, como centenas de milhares de pessoas escreveram antes. Nada de incomum ou complicado, mas quando olhei para ele, tive duas perguntas:

• Por que, por padrão, todos resolvem o problema dessa maneira?
• É possível fazer melhor?

Brevemente sobre o material. Se você souber o que é uma lista duplamente vinculada, poderá pular o próximo parágrafo.

Uma lista duplamente vinculada é uma das estruturas básicas de dados; o conhecimento geralmente ocorre nos estágios iniciais do treinamento em programação. Essa é uma coleção que consiste em uma sequência de nós que contêm alguns dados e são pareados entre si - ou seja, se o nó A se referir a B como o próximo, o nó B se referirá a A como o anterior. Na prática, você pode encontrar essa estrutura em contêineres como std :: list em C ++, LinkedList em C # e Java. Provavelmente, você encontrará sua implementação na biblioteca padrão de qualquer outro idioma.

Além disso, no texto, serão descritas as propriedades e operações básicas dessa lista, com a indicação da complexidade computacional.

Agora, de volta às perguntas feitas anteriormente.

Examinei a condição do problema e vi a resposta para o primeiro. Aqui está:

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

. - .