Java ArrayList, как добавлять элементы в начале

183

Мне нужно добавить элементы в ArrayListочередь как угодно, но когда я вызываю функцию для добавления элемента, я хочу, чтобы он добавил элемент в начале массива (поэтому он имеет самый низкий индекс), и если массив имеет добавление 10 элементов новый результат удаляет самый старый элемент (тот, который имеет самый высокий индекс).

У кого-нибудь есть предложения?

ZeDonDino
источник
Вы имеете в виду как removeи add?
Питер Лори
arraylist stack queue whateverЛучше избегать того, что вы используете как добавление в начало массива, и похоже, что вы должны использовать другую коллекцию.
Питер Лори
Во-первых, вы должны сделать что-то самостоятельно. Что ты сделал до сих пор?
Егошин Максим

Ответы:

301

Listимеет метод add(int, E), так что вы можете использовать:

list.add(0, yourObject);

После этого вы можете удалить последний элемент с помощью:

if(list.size() > 10)
    list.remove(list.size() - 1);

Однако вы можете пересмотреть свои требования или использовать другую структуру данных, например Queue

РЕДАКТИРОВАТЬ

Может быть, посмотрите на Apache CircularFifoQueue:

CircularFifoQueue является очередью «первым пришел - первым вышел» с фиксированным размером, который заменяет самый старый элемент, если он заполнен.

Просто инициализируйте его с максимальным размером:

CircularFifoQueue queue = new CircularFifoQueue(10);
Baz
источник
10
Я не стал бы трогать любую библиотеку apache с полюсом в десять футов, тем более что существуют классы коллекций guava. EvavtingQueue Guava может быть хорошим выбором здесь.
DPM
26

Использование конкретных структур данных

Существуют различные структуры данных, которые оптимизированы для добавления элементов в первый индекс. Имейте в виду, что если вы преобразуете свою коллекцию в одну из них, беседе, вероятно, потребуется временная и пространственная сложностьO(n)

Deque

JDK включает в себя Dequeструктуру, которая предлагает такие методы, как addFirst(e)иofferFirst(e)

Deque<String> deque = new LinkedList<>();
deque.add("two");
deque.add("one");
deque.addFirst("three");
//prints "three", "two", "one"

Анализ

Пространственно-временная сложность вставки с помощью LinkedListконстанты ( O(1)). Смотрите Big-O шпаргалку .

Перевернуть список

Очень простой, но неэффективный метод - использовать реверс:

 Collections.reverse(list);
 list.add(elementForTop);
 Collections.reverse(list);

Если вы используете потоки Java 8, этот ответ может вас заинтересовать.

Анализ

  • Сложность времени: O(n)
  • Космическая сложность: O(1)

Глядя на реализацию JDK, это имеет O(n)временную сложность, поэтому подходит только для очень маленьких списков.

Патрик Фавр
источник
Перевернуть список дважды. Будет ли он добавить время выполнения алгоритма с большим отрывом по сравнению с принятым выше решением?
Самьяк Upadhyay
Это добавляет 2n, так что да, но если у вас есть список <50, вы не сможете микро-тестировать разницу на большинстве современных машин
Патрик Фавр
8

Вы можете взглянуть на add (int index, E element) :

Вставляет указанный элемент в указанную позицию в этом списке. Смещает элемент, находящийся в данный момент в этой позиции (если есть), и любые последующие элементы вправо (добавляет один к их индексам).

После добавления вы можете проверить размер ArrayList и удалить его в конце.

npinti
источник
4

Вы можете посмотреть на Deque. это дает вам прямой доступ к первым и последним элементам в списке.

Evvo
источник
1
Я удивлен, что вы единственный ответ, говорящий о Deque, это, очевидно, лучшее оптимальное решение.
Гийом Ф.
3

То, что вы описываете, является подходящей ситуацией для использования Queue.

Так как хочется addнового элемента и removeстарого. Вы можете добавить в конце и удалить с начала. Это не будет иметь большого значения.

Очередь имеет методы add(e)и remove()который добавляет в конце новый элемент, и удаляет с самого начала старого элемента, соответственно.

Queue<Integer> queue = new LinkedList<Integer>();
queue.add(5);
queue.add(6);
queue.remove();  // Remove 5

Таким образом, каждый раз, когда вы добавляете элемент в, queueвы можете создать его резервную копию с помощью removeвызова метода.


ОБНОВЛЕНИЕ : -

И если вы хотите исправить размерQueue , то вы можете взглянуть на: -ApacheCommons#CircularFifoBuffer

Из documentation: -

CircularFifoBuffer - это буфер «первым пришел - первым обслужен» с фиксированным размером, который заменяет его самый старый элемент, если он заполнен.

Buffer queue = new CircularFifoBuffer(2); // Max size

queue.add(5);
queue.add(6);
queue.add(7);  // Automatically removes the first element `5`

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

Рохит Джайн
источник
1

Я думаю, что реализация должна быть простой, но учитывая эффективность, вы должны использовать LinkedList, а не ArrayList в качестве контейнера. Вы можете обратиться к следующему коду:

import java.util.LinkedList;
import java.util.List;

public class DataContainer {

    private List<Integer> list;

    int length = 10;
    public void addDataToArrayList(int data){
        list.add(0, data);
        if(list.size()>10){
            list.remove(length);
        }
    }

    public static void main(String[] args) {
        DataContainer comp = new DataContainer();
        comp.list = new LinkedList<Integer>();

        int cycleCount = 100000000;

        for(int i = 0; i < cycleCount; i ++){
            comp.addDataToArrayList(i);
        }
    }
}
feikiss
источник
0

Вы можете использовать этот код

private List myList = new ArrayList();
private void addItemToList(Object obj){
    if(myList.size()<10){
      myList.add(0,obj);
    }else{
      myList.add(0,obj);
      myList.remove(10);
    }
}
MaVRoSCy
источник
0

Вы можете использовать методы списка, удалить и добавить

list.add(lowestIndex, element);
list.remove(highestIndex, element);
Меня_
источник
0

Возьмите этот пример:

List<String> element1 = new ArrayList<>();
element1.add("two");
element1.add("three");
List<String> element2 = new ArrayList<>();
element2.add("one");
element2.addAll(element1);
Ашиш Мехта
источник
-1

Ты можешь использовать

public List<E> addToListStart(List<E> list, E obj){
list.add(0,obj);
return (List<E>)list;

}

Изменить E с вашим типом данных

Если необходимо удалить самый старый элемент, вы можете добавить:

list.remove(list.size()-1); 

до возврата заявления. В противном случае список добавит ваш объект в начале, а также сохранит самый старый элемент.

Это удалит последний элемент в списке.

ученик
источник
-1
import java.util.*:
public class Logic {
  List<String> list = new ArrayList<String>();
  public static void main(String...args) {
  Scanner input = new Scanner(System.in);
    Logic obj = new Logic();
      for (int i=0;i<=20;i++) {
        String string = input.nextLine();
        obj.myLogic(string);
        obj.printList();
      }
 }
 public void myLogic(String strObj) {
   if (this.list.size()>=10) {
      this.list.remove(this.list.size()-1);
   } else {
     list.add(strObj); 
   }
 }
 public void printList() {
 System.out.print(this.list);
 }
}
Махиндра Неупане
источник
-2

У меня была похожая проблема: я пытался добавить элемент в начале существующего массива, сдвинуть существующие элементы вправо и отбросить самый старый (массив [длина-1]). Мое решение может быть не очень эффективным, но оно работает для моих целей.

 Method:

   updateArray (Element to insert)

     - for all the elements of the Array
       - start from the end and replace with the one on the left; 
     - Array [0] <- Element

Удачи

FabianUx
источник