Какова структура данных, которая имеет O (1) для добавления, добавления и извлечения элемента в любом месте?

Question

Я ищу решение Java, но любой общий ответ тоже в порядке.

Vector / ArrayList - O (1) для добавления и извлечения, но O (n) для предварительного добавления.

LinkedList (в Java реализован как двунаправленный список) равен O (1) для добавления и добавления, но O (n) для извлечения.

Deque (ArrayDeque) равен O (1) для всего вышеперечисленного, но не может извлечь элемент по произвольному индексу.

На мой взгляд, структура данных, которая удовлетворяет вышеуказанному требованию, имеет 2 расширяемых списка (один для prepend и один для append), а также хранит смещение, чтобы определить, где получить элемент во время поиска.

Answer 1

Вы ищете двустороннюю очередь. Это реализовано так, как вы хотите в C ++ STL, то есть вы можете индексировать в него, но не в Java, как вы заметили. Вы можете предположительно свернуть свои собственные из стандартных компонентов, используя два массива и сохраняя, где находится «ноль». Это может привести к бесполезной трате памяти, если вы в конечном итоге переместитесь на долгий путь от нуля, но если вы зайдете слишком далеко, вы можете перебазировать и разрешить деку сканировать в новый массив.

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

Answer 2

A deque (двусторонняя очередь) может быть реализовано, чтобы обеспечить все эти операции за O (1) время, хотя не все реализации делают. Я никогда не использовал Java ArrayDeque, поэтому я подумал, что вы шутите по поводу того, что он не поддерживает произвольный доступ, но вы абсолютно правы - как «чистый» deque, он обеспечивает только легкий доступ на концах. Я понимаю почему, но это точно раздражает ...

Для меня идеальный способ реализовать очень быструю деку - это использовать кольцевой буфер , тем более что вас интересует только добавление удаления спереди и сзади. Я не сразу знаю об этом на Java, но я написал один на Objective-C как часть инфраструктуры с открытым исходным кодом. Вы можете использовать код, как есть, или как шаблон для реализации своего собственного.

Вот портал WebSVN с кодом и соответствующей документацией . Настоящее мясо находится в файле CHAbstractCircularBufferCollection.m - ищите методы appendObject: и prependObject:. Также существует даже собственный перечислитель («итератор» в Java). Необходимая логика циклического буфера довольно тривиальна и представлена ​​в этих 3 централизованных макросах #define:

#define transformIndex(index) ((headIndex + index) % arrayCapacity)
#define incrementIndex(index) (index = (index + 1) % arrayCapacity)
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1)

Как вы можете видеть в методе objectAtIndex:, все, что вы делаете для доступа к N-му элементу в deque, это array[transformIndex(N)]. Обратите внимание, что я заставляю tailIndex всегда указывать на один слот после последнего сохраненного элемента, поэтому, если headIndex == tailIndex, массив заполнен или пуст, если размер равен 0.

Надеюсь, это поможет. Приношу свои извинения за публикацию не Java-кода, но автор вопроса сказал , что общие ответы были приемлемы.

Answer 3

Если вы рассматриваете добавление к Vector / ArrayList как O (1) - что на самом деле это не так, но на практике может быть достаточно близко -
(РЕДАКТИРОВАТЬ - чтобы уточнить - добавление может быть амортизированное постоянное время , то есть - в среднем, добавление будет O (1), но может быть немного хуже для шипов. В зависимости от контекста и точного константы, это поведение может быть смертельным).

(Это не Java, а какой-то выдуманный язык ...).

Один вектор, который будет называться «Вперед». Второй вектор, который будет называться «Назад».

Когда попросили добавить - Forward.Append().

Когда его просят подготовить - Backwards.Append().

При запросе на запрос -

if ( Index < Backwards.Size() )
{
    return Backwards[ Backwards.Size() - Index - 1 ]
}
else
{
    return Forward[ Index - Backwards.Size() ]
}

(а также проверить, находится ли индекс вне границ).

Answer 4

Ваша идея может сработать. Если это единственные операции, которые вам нужно поддерживать, то вам нужны два вектора (назовите их Head и Tail). Чтобы подготовиться, вы присоединяетесь к голове, а для добавления - к хвосту. Чтобы получить доступ к элементу, если индекс меньше, чем head.Length, верните head [head.Length-1-index], иначе верните tail [index-head.Length]. Все эти операции явно O (1).

Answer 5

Вот структура данных, которая поддерживает O (1) добавление, предварительное добавление, первое, последнее и размер. Мы можем легко добавить другие методы из AbstractList<A>, такие как delete и update

import java.util.ArrayList;

public class FastAppendArrayList<A> {
    private ArrayList<A> appends = new ArrayList<A>();
    private ArrayList<A> prepends = new ArrayList<A>();

    public void append(A element) {
        appends.add(element);
    }

    public void prepend(A element) {
        prepends.add(element);
    }

    public A get(int index) {
        int i = prepends.size() - index;
        return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size());
    }

    public int size() {
        return prepends.size() + appends.size();
    }

    public A first() {
        return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size());
    }

    public A last() {
        return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size());
    }

Answer 6

То, что вам нужно, - это двусторонняя очередь (deque), как у STL, поскольку в ArrayDeque Java по некоторым причинам не хватает get(). Здесь было несколько хороших предложений и ссылок на реализации:

• Java-эквивалент std :: deque?