¿Qué es una estructura de datos que tiene O (1) para anexar, anteponer y recuperar elementos en cualquier ubicación?

Question

Estoy buscando una solución Java, pero cualquier respuesta general también está bien.

Vector/ArrayList es O (1) para anexar y recuperar, pero O (n) para anteponer.

LinkedList (en Java implementado como double-linked-list) es O (1) para agregar y anteponer, pero O (n) para la recuperación.

Deque (ArrayDeque) es O (1) para todo lo anterior, pero no puede recuperar el elemento en el índice arbitrario.

En mi opinión, una estructura de datos que satisfaga el requisito anterior tiene 2 listas creíbles en el interior (una para anteponer y otra para anexar) y también almacena un desplazamiento para determinar dónde obtener el elemento durante la recuperación.

Answer 1

Está buscando una cola de doble final. Esto se implementa de la manera que desee en C++ STL, que es lo que puede indexar, pero no en Java, como notó. Es posible que desarrolles tus propios componentes estándar usando dos matrices y almacenando donde está "cero". Esto puede ser un desperdicio de memoria si terminas moviéndote lejos de cero, pero si llegas demasiado lejos puedes volver a establecer la base y permitir que el deque se arrastre a una nueva matriz.

Una solución más elegante que no requiere mucha imaginación para administrar dos matrices es imponer una matriz circular en una matriz preasignada. Esto requeriría implementar push_front, push_back, y el redimensionamiento de la matriz detrás de él, pero las condiciones para el cambio de tamaño y tal sería mucho más limpio.

Answer 2

Su idea podría funcionar. Si esas son las únicas operaciones que necesita apoyar, entonces dos vectores son todo lo que necesita (llámelos Head y Tail). Para anteponer, añádelo a la cabeza, y para anexar, añádelo a la cola. Para acceder a un elemento, si el índice es menor que head.Length, luego return head [head.Length-1-index], de lo contrario devolver tail [index-head.Length]. Todas estas operaciones son claramente O (1).

Answer 3

Si usted trata a anexar a un vector/ArrayList como O (1) - que en realidad no lo es, pero podría ser lo suficientemente cerca como en la práctica -
(EDITAR - para aclarar - append puede ser amortizados constante de tiempo , es decir, en promedio, la adición sería O (1), pero podría ser un poco peor en los picos. Dependiendo del contexto y las constantes exactas involucradas, este comportamiento puede ser mortal).

(Esto no es Java, pero sí algo de lenguaje inventado ...).

Un vector que se denominará "Adelante". Un segundo vector que se llamará "Al revés".

Cuando se le solicite anexar - Forward.Append().

Cuando se le solicite preceder - .

Cuando se le preguntó a consultar -

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

(y también para comprobar el índice de estar fuera de los límites).

Answer 4

Lo que quiere es una cola de doble final (deque) como la STL tiene, ya que ArrayDeque de Java carece de get() por algún motivo.Hubo algunas buenas sugerencias y enlaces a las implementaciones aquí:

• Java equivalent of std::deque?

Answer 5

Un deque (cola de doble extremo) puede ser implementado para proporcionar todas estas operaciones en O (1) tiempo, aunque no todas las implementaciones lo hacen. Nunca utilicé ArrayDeque de Java, así que pensé que estabas bromeando porque no admite el acceso aleatorio, pero tienes toda la razón: como deque "puro", solo permite un fácil acceso en los extremos. Puedo ver por qué, pero eso es molesto ...

Para mí, la forma ideal de implementar una deque extremadamente rápida es utilizar un circular buffer, especialmente porque solo está interesado en agregar la eliminación en la parte delantera y posterior. No estoy al tanto de uno en Java, pero he escrito uno en Objective-C como parte de un marco de código abierto. Le invitamos a usar el código, tal como está o como un patrón para implementar el suyo.

Aquí está un WebSVN portal to the code y el related documentation. La verdadera carne está en el archivo CHAbstractCircularBufferCollection.m - busque los métodos appendObject: y prependObject:. Incluso hay un enumerador personalizado ("iterador" en Java) definido también. La lógica esencial buffer circular es bastante trivial, y es capturado en estas 3 centralizados #define macros:

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

Como se puede ver en el método objectAtIndex:, todo lo que hacen para tener acceso al elemento número n de un deque es array[transformIndex(N)]. Tenga en cuenta que hago que tailIndex siempre apunte a una ranura más allá del último elemento almacenado, por lo que si headIndex == tailIndex, la matriz está llena o vacía si el tamaño es 0.

Espero que ayude. Mis disculpas por publicar código que no es de Java, pero el autor de la pregunta hizo dice que las respuestas generales fueron aceptables.

Answer 6

Aquí hay una estructura de datos que admite O (1) append, prepend, first, last y size. Podemos agregar fácilmente otros métodos de AbstractList<A> como delete y 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()); 
    }