👨🏾‍🏭 🈚️ 😧 我如何辩论O的双向链表（1） 👩‍👧‍👦 😚 👘

一旦我偶然看到我的同事解决了在C ++中扩展双向链表的初级任务。在那一刻，令我感到奇怪的不是他是领导者，而且早已不合时宜，而是决定本身。

更确切地说，并非如此。

解决方案是标准的：成千上万的人在它之前写过相同的线性段落，并在每个节点中替换了指针。没什么异常或复杂的，但是当我看着他时，我有两个问题：

为什么默认情况下每个人都以这种方式解决问题？
有可能做得更好吗？

简要介绍一下装备。如果您知道双向链表是什么，则可以跳过下一段。

双向链表是基本数据结构之一；熟悉链表通常发生在编程培训的早期。这是一个由一系列节点组成的集合，这些节点包含一些数据并且彼此配对-也就是说，如果节点A将B称为下一个，则节点B将A称为上一个。实际上，您可以在诸如C ++中的std :: list，C＃中的LinkedList和Java之类的容器中找到此结构。您很可能会在其他任何语言的标准库中找到其实现。

进一步在本文中，将描述具有计算复杂性的指示的这种列表上的基本属性和操作。

现在回到前面提出的问题。

我调查了问题的状况，并看到了第一个答案。这是：

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

. - .

我如何辩论O的双向链表（1）

More articles: