Приветствую вас!
После изучения коллекций, а именно такие реализации List, как ArrayList и LinkedList, возникла идея, а почему бы не объединить эти структуры данных в одну и посмотреть, что из этого получится.


Зачем это нужно?


  • Проблема ArrayList — у него есть начальный размер по умолчанию DEFAULT_CAPACITY или заданный размер initialCapacity, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложность O(n)
  • Проблема LinkedList — здесь наоборот, добавить новый элемент, это всего лишь добавить новую связь (создать еще одну Node и добавить ссылку на неё), но операция получения элемента по индексу очень затратна, т.к. нужно будет пройтись по всему списку от начала, что очень затратно и дает O(n)

Решение


Что если создать такую структуру данных, при которой вставка и получение любого элемента будет за константное время. Буду использовать технологию ArrayList без пересоздания массива
Для того чтобы связать их между собой, буду использовать двусвязный список:


Реализация


Перейдем непосредственно к исходному коду:


public class Node<T> {
    Node prev;
    Node next;
    T[] value;

    public Node(Node prev, Node next, T[] value) {
        this.prev = prev;
        this.next = next;
        this.value = value;
    }
}

Для начало создадим стандартную структуру двусвязного списка, где value — это массив значений.
Далее перейдем к конкретной реализации класса, объявим необходимые переменные: 


public static int INIT_CAPACITY = 100;
private Object[] arr = new Object[INIT_CAPACITY];
private int index = 0;
private int level = 0;
private Node<T> first = new Node<>(null, null, (T[]) arr);
private Node last = first;
private Node current = null;
private int size = 0;

Здесь INIT_CAPACITY — начальный размер массива, его можно переопределить в соответствующем конструкторе, arr — собственно сам массив, переменная index — понадобится для расчета индекса, level — для расчета уровня, далее подробно будет рассказано для чего это нужно, first — ссылка на первый элемент списка,
last — ссылка на последний элемент списка, current — ссылка на текущий элемент списка (последней выборки), так можно ускорить выборку подряд идущих элементов или близ — лежащих к ним, size — размер (или количество данных).
Зададим 2 коструктора — по умолчанию и для изменения начального размера:


public MyLinkedList() {
    first.next = last.next;
}
public MyLinkedList(int size) {
    INIT_CAPACITY = size;
    arr = new Object[INIT_CAPACITY];
    first.next = last.next;
}

Добавление элемента:


public void add(T i) {
    if (index == INIT_CAPACITY) {
        arr = new Object[INIT_CAPACITY];
        last.next = new Node<>(last, null, (T[]) arr);
        index = 0;
        last = last.next;
    }
    arr[index] = i;
    index++;
    size++;
}

Здесь проверяем условие, если массив заполнен, то создаем новый и запоминаем ссылку на него.
Получение элемента:


public T get(int i) {
    T value;
    int level = i / INIT_CAPACITY;
    int index = i % INIT_CAPACITY;
    if (this.current == null) {
        this.level = 0;
        this.current = first;
    }
    if(this.level > level)
        for (int j = this.level; j < level; j++) {
            this.level = level;
            current = current.prev;
        }
    else
        for (int j = this.level; j < level; j++) {
            this.level = level;
            current = current.next;
        }
    value = (T) current.value[index];
    return value;
}

Уровни это количество массивов в списке, т.е на 0-м уровне 1 массив, на 1-м уровне 2 массива и т.д.,index — это индекс текущего уровня 0..INIT_CAPACITY, также у нас есть ссылка на текущий элемент списка current, который был получен из предыдущей выборки, т.е. если новый уровень больше предыдущего, то идем вперед от текущего элемента и если наоборот, то назад. Также добавил 2 быстрые операции — получение первого и последнего элемента:


public T getFirst(){
    return first.value[0];
}
public T getLast() {
    return (T) last.value[(size-1) % INIT_CAPACITY];
}

Первый и последний элемент получить также просто и быстро, как в массиве.
Операция удаления последнего элемента — быстрее всего это затирать значение null-ом, если весь массив становится заполненным null-ми, то теряем ссылку на него и garbage collector все почистит:


public void removeLast(){
    if (last.value[0] == null) {
        last = last.prev;
        index=INIT_CAPACITY-1;
    }
    last.value[(size-1) % INIT_CAPACITY]=null;
    size--;
    index--;
}

Получение размера — очевидно. Также был добавлен итератор, т.е. этот класс имплементирует Iterable и реализует метод iterator


private Node<T> first;
private int index = -1;
public MyLinkedListIterator(Node<T> first) {
    this.first = first;
}

@Override
public boolean hasNext() {
   index++;
   return first != null;
}

@Override
public T next() {
    T value;
    int index = this.index % INIT_CAPACITY;
    value= first.value[index];
    if(index==INIT_CAPACITY-1||this.first.value[index+1]==null)
        first=first.next;
    return value;
}

Время работы


Замерял с помощью JMH benchmark, пример теста:


public class TestGetMyDeque {

    private static class SetDeque {
        MyDeque<Integer> deque = new MyDeque<>();

        SetDeque() {
            for (int i = 0; i <Constant.COUNT_ELEMENT; i++) {
                deque.add(i);
            }
        }
    }

    @State(Scope.Benchmark)
    public static class MyState{
        SetDeque deque;
        @Setup(Level.Invocation)
        public void setUp() {
            deque = new SetDeque();
        }
    }

     @Benchmark
     @BenchmarkMode(Mode.AverageTime)
     @OutputTimeUnit(TimeUnit.SECONDS)
     public void getFirst(MyState state, Blackhole blackhole) {
         for (int i = 0; i < Constant.COUNT_ELEMENT; i++) {
             blackhole.consume(state.deque.deque.getFirst());
         }
     }
}

Документацию, можно посмотреть в интернете
Брал разное количество элементов, результаты тестов в сек:


N=100000 Вставка в конец Получение первого Получение среднего Получение последнего
MyDeque 0,002 0 0,001 0
ArrayDeque 0,002 0 - 0,001
ArrayList 0,002 0,001 0 0,001
LinkedList 0,003 0 28,465 0,001

Возьмем миллион элементов:


N=1000000 Вставка в конец Получение первого Получение среднего Получение последнего
MyDeque 0,019 0,005 0,010 0,007
ArrayDeque 0,025 0,005 - 0,005
ArrayList 0,036 0,005 0,005 0,005
LinkedList 0,051 0,005 OutOfMemoryError: Java heap space 0,006

И наконец, возьмем 10 миллионов элементов:


N=10000000 Вставка в конец Получение первого Получение среднего Получение последнего
MyDeque 1,832 0,047 0,090 0,071
ArrayDeque 2,065 0,046 - 0,058
ArrayList 4,413 0,048 0,047 0,048
LinkedList OutOfMemoryError: Java heap space

Замер памяти делал по принципу https://github.com/jheusser/core-java-performance-examples/


(ось x — миллион элементов, ось y — мб памяти)


Как видно из графика пожирание памяти этой структурой не сильно отличается от схожих ей структур данных


Вывод


В сухом остатке, получили очередь LIFO, которая работает быстрее, чем обычная Deque, а в плане вставке элементов, намного быстрее чем ArrayList, также нет проблем с которыми можно столкнуться при использовании LinkedList. В дальнейшем планируется реализовать такие операции как вставка и удаление из любого места без потери производительности, уже есть кое-какие наработки по этому поводу, на данном этапе хотелось бы получить обратную связь и увидеть заинтересованность сообщества для дальнейшей работы над новой структурой данных.


Проект можно посмотреть по ссылке