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

Question

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

Можно ли это сделать?

EDIT: Я пишу на C, но это может быть для любого языка.

Answer 1

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

Answer 2

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

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

Answer 3

элементы строки сервера SQL в clustered index are arranged like so:

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

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

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

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

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

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

Эта сложность в решении проблемы: Добавить, Удалить, Идти в индекс, все работают в O (logn).

Недостатком этого решения является то, что его гораздо сложнее реализовать, чем обычный связанный список. Поэтому, используя регулярный связанный список, вы получаете «Добавить», «Удалить» в O (1) и «Перейдите к индексу в O (n)».