Можем ли мы реализовать двусвязный список, используя один указатель?

Я хочу использовать указанную выше структуру для создания дважды связанного списка. Возможно ли это, и если да, то как я могу это достичь?

Ответы

Ответ 1

Да, возможно, но это грязный хак.

Он называется связанным списком XOR. (https://en.wikipedia.org/wiki/XOR_linked_list)

Каждый node хранит XOR next и prev как uintptr_t.

Вот пример:

#include <cstddef>
#include <iostream>

struct Node
{
    int num;
    uintptr_t ptr;
};

int main()
{
    Node *arr[4];
    // Here we create a new list.
    int num = 0;
    for (auto &it : arr)
    {
        it = new Node;
        it->num = ++num;
    }
    arr[0]->ptr =                     (uintptr_t)arr[1];
    arr[1]->ptr = (uintptr_t)arr[0] ^ (uintptr_t)arr[2];
    arr[2]->ptr = (uintptr_t)arr[1] ^ (uintptr_t)arr[3];
    arr[3]->ptr = (uintptr_t)arr[2];

    // And here we iterate over it
    Node *cur = arr[0], *prev = 0;
    do
    {
        std::cout << cur->num << ' ';
        prev = (Node *)(cur->ptr ^ (uintptr_t)prev);
        std::swap(cur, prev);
    }
    while (cur);
    return 0;
}

Он печатает 1 2 3 4, как ожидалось.

Ответ 2

Я хотел бы предложить альтернативный ответ, который сводится к "да и нет".

Во-первых, это "нечто вроде невозможного", если вы хотите получить все преимущества двусвязного списка только с одним указателем на node.

Список XOR

Однако приведенный здесь список также был связан с XOR. Он сохраняет одно основное преимущество за счет сжатия с потерями двух указателей, которые укладываются в одно, которое вы теряете с помощью односвязного списка: способность пересекать его в обратном направлении. Он не может делать такие вещи, как удаление элементов из середины списка в постоянное время, учитывая только адрес node, и возможность вернуться к предыдущему элементу в прямой итерации и удалить произвольный элемент в линейном времени еще проще без списка XOR (вы также сохраняете два указателя node: previous и current).

Производительность

Тем не менее, в комментариях было указано стремление к производительности. Учитывая это, я думаю, что есть некоторые практические альтернативы.

Во-первых, указатель next/prev в двусвязном списке не обязательно должен быть, скажем, 64-разрядным указателем на 64-битных системах. Он может быть двумя индексами в 32-битное смежное адресное пространство. Теперь у вас есть два индекса для цены памяти одного указателя. Тем не менее, попытка эмулировать 32-разрядную адресацию на 64-битном уровне довольно востребована, возможно, не совсем то, что вы хотите.

Однако, чтобы воспользоваться всеми преимуществами производительности связанной структуры (включая деревья), часто требуется, чтобы вы вернули контроль над распределением и распределением узлов в памяти. Связанные структуры, как правило, являются узкими, потому что, если вы просто используете malloc или plain operator new для каждого node, например, вы теряете контроль над макетом памяти. Часто (не всегда - вам может повезти в зависимости от распределителя памяти, и независимо от того, вы ли вы распределяете все свои узлы сразу или нет), это означает потерю смежности, что означает потерю пространственной локальности.

Это почему ориентированные на данные проекты подчеркивают массивы больше всего на свете: связанные структуры обычно не очень дружелюбны к производительности. Процесс перемещения кусков из более крупной памяти в меньшую, более быструю память ему нравится, если вы собираетесь получать доступ к соседним данным внутри одного и того же фрагмента (кэш-строка/страница, например) до выселения.

Непродуманный список, не содержащий часто цитируемых

Итак, существует гибридное решение, которое не так часто обсуждается, это разворачиваемый список. Пример:

struct Element
{
    ...
};

struct UnrolledNode
{
    struct Element elements[32];
    struct UnrolledNode* prev;
    struct UnrolledNode* next;
};

Развернутый список объединяет характеристики массивов и двусвязных списков в одном. Это даст вам много пространственной локальности, не обращаясь к распределителю памяти.

Он может перемещаться вперед и назад, он может удалить произвольные элементы из середины в любой момент времени для дешевых.

И это уменьшает накладные расходы связанного списка до абсолютного минимума: в этом случае я жестко запрограммировал размер развернутого массива из 32 элементов на node. Это означает, что стоимость хранения указателей списка сократилась до 1/32 ее нормального размера. Это еще более дешево с точки зрения указателя списка, чем односвязный список, с часто более быстрым обходом (из-за локальности кэша).

Это не идеальная замена для двусвязного списка. Для начала, если вас беспокоит недействительность существующих указателей на элементы в списке при удалении, вы должны начать беспокоиться о том, чтобы оставить свободные пробелы (дыры/надгробные камни) позади, которые будут исправлены (возможно, связывая свободные биты в каждом развернутом node). В этот момент вы сталкиваетесь со многими аналогичными проблемами в реализации распределителя памяти, включая некоторые незначительные формы фрагментации (например: наличие развернутого node с 31 свободным пространством и только один занятый элемент - node все еще должен оставайтесь в памяти, чтобы избежать аннулирования, пока он не станет полностью пустым).

"Итератор" к нему, который позволяет вставлять/удалять в/из середины, обычно должен быть больше, чем указатель (если, как отмечено в комментариях, вы сохраняете дополнительные метаданные с каждым элементом). Он может тратить память (как правило, спорный, если у вас нет очень маленьких списков), требуя, скажем, памяти для 32 элементов, даже если у вас есть список из 1 элемента. Это, как правило, немного сложнее для реализации, чем любое из этих вышеперечисленных решений. Но это очень полезное решение в критическом для производительности сценарии, и часто это, вероятно, заслуживает большего внимания. Это тот, который не так много вырос в информатике, так как он не улучшает алгоритмическую перспективу, чем обычный связанный список, но локальность ссылок оказывает значительное влияние на производительность, а также в реальных сценариях.

Ответ 3

Это не совсем возможно. Для двусвязного списка требуются два указателя, один для ссылки в каждом направлении.

В зависимости от того, что вам нужно, связанный с XOR список может делать то, что вам нужно (см. ответ HolyBlackCat).

Еще один вариант - немного обойти это ограничение, выполняя такие действия, как запоминание последнего node, которое вы обработали, когда вы перебираете список. Это позволит вам вернуться на один шаг во время обработки, но это не делает список дважды связанным.

Ответ 4

Вы можете объявить и поддерживать два начальных указателя на узлы head и tail. В этом случае вы сможете добавлять узлы в оба конца списка.

Такой список иногда называют двухсторонним списком.

Однако сам список будет пересылать список.