Самый простой способ добавить элемент в начало и удалить в конце в Java

#java

Привет!
Подскажите, как Java создать динамический массив (карту) и обработать его, такого вида:
Создаем:
[20,30,40,50,60]
Добавляем  элемент в начало и убираем в конце:
[10,20,30,40,50]
Т.е. мне необходимо оставить тело  20,30,40,50, не трогать, а  к нему добавить голову
10, и убрать хвост 60.
Как реализовать это самым быстрым и дешевым методом это в Java?    

Ответы

Ответ 1

@Andrew F


  создать динамический массив (карту) 


для начала определись чего ты хочешь. карту или динамический массив.
Я вижу что ты используешь список, так что твой выход - интерфейс Deque и его встроенная
 реализация LinkedList.

насколько дорого? что значит дорого ?  В хвосты/голову вствляет быстро. тут подробнее


Ответ 2

Подскажите, как Java создать динамический массив (карту)

Вы, наверное, имеете в виду map (обычно ее начинающие ошибочно называют картой)?
Слово "map" имеет несколько переводов, в зависимости от контекста употребления, и здесь
верный перевод - это "отображение" (этот термин пришел из дискретной математики).
Отображение в Java можно создать на базе дерева или hash таблицы, не думаю, что что-то
из этого вам подойдет.

Как реализовать это самым быстрым и дешевым методом это в Java?

Вам нужен двусвязный список:
 Deque deque = new LinkedList();
 deque.addAll(Arrays.asList(20, 30, 40, 50, 60));
 deque.addFirst(10);        // O(1)
 deque.removeLast();        // O(1)


Подскажите, пожалуйста, в данном
случае на организацию списка, вставку
и удаление  будет затрачено меньше
памяти и процессорного времени чем для
"сдвига" всего массива

Есть эмпирическое правило выбора структуры данных в вашем случае:

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


Ответ 3

Если максимальное количество элементов известно, а добавляются и удаляются они только
с головы и хвоста, то самой эффективной структурой (независимо от Java или Си или ...)
будет использование массива фиксированного размера.
Только у него должна быть "плавающая" точка отсчета (так сказать, виртуальный нулевой
индекс). Т.е. храните индекс "нуля" (ihead) и текущий размер (length). Индекс последнего
(точнее первого свободного в хвосте = (ihead + lenght) % size).
Т.е. вставка новой головы это в ihead - 1 и length++, а удаление хвоста -- тривиально
length--
Ну, думаю, далее сами разберетесь.
--
Кстати (@Xmaster, спасибо за подсказку), подобная структура данных называется кольцевой
(или циклический) буфер (cyclic buffer или ring buffer).


Ответ 4

Добавлю свои пять копеек:
Если размер массива фиксированный, то наилучшим образом конструкция описывается лимитированным
стеком (LimitedStack). Вставка в дно стека приводит к выталкиванию с вершины стека
элемента (аналогия с вертикальной трубой где, элементы добавляются/берутся только снизу).
В Guava есть такая коллекция EvictingQueue