Cómo debatí una lista doblemente vinculada para O (1)

Una vez, accidentalmente vi a mi colega resolver la tarea junior de expandir una lista doblemente vinculada en C ++. Y en ese momento me pareció extraño, no que él fuera un líder y lo hubiera superado durante mucho tiempo, sino la decisión en sí.

Más sinceramente, no es así.

La solución era estándar: el mismo pasaje lineal con el reemplazo de punteros en cada nodo, como lo escribieron cientos de miles de personas antes. Nada inusual o complicado, pero cuando lo miré, tuve dos preguntas:

• ¿Por qué por defecto todos resuelven el problema de esta manera?
• ¿Es posible hacerlo mejor?

Brevemente sobre el material. Si sabe qué es una lista doblemente enlazada, puede omitir el siguiente párrafo.

Una lista doblemente vinculada es una de las estructuras básicas de datos; su conocimiento generalmente ocurre en las primeras etapas de la capacitación en programación. Esta es una colección que consiste en una secuencia de nodos que contienen algunos datos y están emparejados entre sí, es decir, si el nodo A se refiere a B como el siguiente, entonces el nodo B se refiere a A como el anterior. En la práctica, puede encontrar esta estructura en contenedores como std :: list en C ++, LinkedList en C # y Java. Lo más probable es que encuentre su implementación en la biblioteca estándar de cualquier otro idioma.

Más adelante en el texto, se describirán las propiedades y operaciones básicas en dicha lista con la indicación de complejidad computacional.

Ahora volvamos a las preguntas expresadas anteriormente.

Investigué la condición del problema y vi la respuesta a la primera. Aquí esta:

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

. - .