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

Question

Мне нужна сортировка структуры связанного списка, но если бы у нее тоже был индексированный доступ, было бы здорово.

Есть ли способ сделать это?

РЕДАКТИРОВАТЬ: Я пишу на C, но это может быть для любого языка.

Answer 1

Один из способов достижения вашей цели - реализовать случайный или детерминированный список пропусков . На нижнем уровне - у вас есть связанный список с вашими предметами.

Чтобы получить элементы, использующие индексы, вам нужно добавить информацию к внутренним узлам - сколько узлов находится на самом низком уровне от этого узла до следующего узла на этом уровне. Эта информация может быть добавлена ​​и сохранена в O (logn).

Сложность этого решения: Добавить, удалить, перейти к индексу, все работают в O (logn).

Недостатком этого решения является то, что его гораздо сложнее реализовать, чем обычный связанный список. Таким образом, используя обычный связанный список, вы получаете Add, Remove in O (1) и Go to index in O (n).

Answer 2

Вы, вероятно, можете использовать дерево для того, к чему вы стремитесь. Создайте двоичное дерево, которое поддерживает вес каждого узла дерева (где вес равен числу узлов, прикрепленных к этому узлу, включая самого себя). Если у вас есть схема балансировки, доступная для дерева, тогда вставки по-прежнему равны O (log n), поскольку вам нужно только добавить одну к весам узлов-предков. Получение узла по индексу - это O (log n), поскольку вам нужно только взглянуть на индексы предков нужного вам узла и двух потомков каждого из этих предков.

Answer 3

Элементы строки сервера SQL в кластерном индексе расположены следующим образом: :

   .
 /  \   
/\  /\  
*-*-*-*

Связанный список находится в листьях (*-*-*). Связанный список упорядочен, что позволяет быстро направленное сканирование, а дерево служит «дорожной картой» в связанном списке. Таким образом, вам понадобится пара ключ-значение для ваших элементов, а затем структура данных, которая инкапсулирует дерево и связанный список.

так что ваша структура данных может выглядеть примерно так:

struct ll_node
{
     kv_pair current;
     ll_node * next;
};

struct tree_node
{
   value_type value;
   short isLeaf;        

   union
   {
      tree_node * left_child;
      kv_pair * left_leaf;
   }
   union
   {
      tree_node * right_child;
      kv_pair * right_leaf
   }
};

struct indexed_ll
{
    tree_node * tree_root;
    ll_node * linked_list_tail;
};

Answer 4

Для достижения индексации массива в таких языках, как C ++, Java, Python, необходимо перегрузить оператор индексации массива [] для класса, который реализует структуру данных связанного списка. Реализация будет O (n). В C, поскольку перегрузка оператора невозможна, следовательно, необходимо написать функцию, которая берет структуру данных связанного списка и позицию и возвращает соответствующий объект.

В случае, если требуется более быстрый доступ к порядку, нужно будет использовать другую структуру данных, такую ​​как BTree, предложенную jprete, или динамический массив (который автоматически увеличивается по мере добавления в него новых элементов). Быстрый пример будет std::vector в стандартной библиотеке C ++.