Java ArrayList how to add elements at the beginning

Question

I need to add elements to an ArrayList queue whatever, but when I call the function to add an element, I want it to add the element at the beginning of the array (so it has the lowest index) and if the array has 10 elements adding a new results in deleting the oldest element (the one with the highest index).

Does anyone have any suggestions?

Answer 1

Starting from Java 21, List extends SequencedCollection interface, which has the following methods:

interface SequencedCollection<E> extends Collection<E> {
  SequencedCollection<E> reversed();
  void addFirst(E);
  void addLast(E);
  E getFirst();
  E getLast();
  E removeFirst();
  E removeLast();
}

Additional details in JEP 431: Sequenced Collections.

So, working with the first/last element becomes simpler:

list.addFirst(new Object());

...

if (list.size() > 10) {
  list.removeLast();
}

Notes:

• Keep in mind that while the time complexity of removing the last element from ArrayList is O(1), adding an element to beginning of ArrayList is O(n), as it would require shifting all the existing elements by one position. So, might be worth checking ArrayDeque as suggested by others.
• List.removeLast throws NoSuchElementException if the list is empty.

Answer 2

Bounded Circular Buffer With FIFO Discipline

It seems that you need a circular buffer with limited capacity. You prefer an array like behavior and you dislike a linked queue. Am I right? You appear to need a capacity set to '10'. This can achieved with a bounded structure. You seem also to need a FIFO discipline.

Solution with an ArrayBlockingQueue

From the docs: A bounded blocking queue backed by an array... orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue. Put, take are blocking . Offer, poll do not block.

PriorityBlockingQueue

You can have a look at docs for PriorityBlockingQueue. There is an example of a class "that applies first-in-first-out tie-breaking to comparable elements".

Example with an ArrayBlockingQueue

ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);

for (int i = 10; i < 30; i++) {
    if (queue.remainingCapacity() > 0) {
        queue.offer(i);
    } else {
        queue.poll();
        queue.offer(i);
    }
    if (queue.size() > 9) {
        System.out.println(queue);
    }
}

Answer 3

import com.google.common.collect.Lists;

import java.util.List;

/**
 * @author Ciccotta Andrea on 06/11/2020.
 */
public class CollectionUtils {

    /**
     * It models the prepend O(1), used against the common append/add O(n)
     * @param head first element of the list
     * @param body rest of the elements of the list
     * @return new list (with different memory-reference) made by [head, ...body]
     */
    public static <E> List<Object> prepend(final E head, List<E> final body){
        return Lists.asList(head, body.toArray());
    }

    /**
     * it models the typed version of prepend(E head, List<E> body)
     * @param type the array into which the elements of this list are to be stored
     */
    public static <E> List<E> prepend(final E head, List<E> body, final E[] type){
        return Lists.asList(head, body.toArray(type));
    }
}

Answer 4

Take this example :-

List<String> element1 = new ArrayList<>();
element1.add("two");
element1.add("three");
List<String> element2 = new ArrayList<>();
element2.add("one");
element2.addAll(element1);

Answer 5

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);
 }
}

Answer 6

Using Specific Datastructures

There are various data structures which are optimized for adding elements at the first index. Mind though, that if you convert your collection to one of these, the conversation will probably need a time and space complexity of O(n)

Deque

The JDK includes the Deque structure which offers methods like addFirst(e) and offerFirst(e)

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

Analysis

Space and time complexity of insertion is with LinkedList constant (O(1)). See the Big-O cheatsheet.

Reversing the List

A very easy but inefficient method is to use reverse:

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

If you use Java 8 streams, this answer might interest you.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Looking at the JDK implementation this has a O(n) time complexity so only suitable for very small lists.

Answer 7

I had a similar problem, trying to add an element at the beginning of an existing array, shift the existing elements to the right and discard the oldest one (array[length-1]). My solution might not be very performant but it works for my purposes.

 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

Good luck

Answer 8

Java LinkedList provides both the addFirst(E e) and the push(E e) method that add an element to the front of the list.

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#addFirst(E)

Answer 9

List has the method add(int, E), so you can use:

list.add(0, yourObject);

Afterwards you can delete the last element with:

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

However, you might want to rethink your requirements or use a different data structure, like a Queue

EDIT

Maybe have a look at Apache's CircularFifoQueue:

CircularFifoQueue is a first-in first-out queue with a fixed size that replaces its oldest element if full.

Just initialize it with you maximum size:

CircularFifoQueue queue = new CircularFifoQueue(10);

Answer 10

You may want to look at Deque. it gives you direct access to both the first and last items in the list.

Answer 11

You can use list methods, remove and add

list.add(lowestIndex, element);
list.remove(highestIndex, element);

Answer 12

I think the implement should be easy, but considering about the efficiency, you should use LinkedList but not ArrayList as the container. You can refer to the following code:

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);
        }
    }
}

Answer 13

What you are describing, is an appropriate situation to use Queue.

Since you want to add new element, and remove the old one. You can add at the end, and remove from the beginning. That will not make much of a difference.

Queue has methods add(e) and remove() which adds at the end the new element, and removes from the beginning the old element, respectively.

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

So, every time you add an element to the queue you can back it up with a remove method call.

---

UPDATE: -

And if you want to fix the size of the Queue, then you can take a look at: - ApacheCommons#CircularFifoBuffer

From the documentation: -

CircularFifoBuffer is a first in first out buffer with a fixed size that replaces its oldest element if full.

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

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

As you can see, when the maximum size is reached, then adding new element automatically removes the first element inserted.

Answer 14

You can use

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

}

Change E with your datatype

If deleting the oldest element is necessary then you can add:

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

before return statement. Otherwise list will add your object at beginning and also retain oldest element.

This will delete last element in list.

Answer 15

you can use this code

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);
    }
}

Answer 16

You can take a look at the add(int index, E element):

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Once you add you can then check the size of the ArrayList and remove the ones at the end.