Insert at front of array

Question

Is there a way to insert an element at the front of an array? I was told there is a method other than using a circular array. We need operations like retrieval and adding to be O(1) time so things like ArrayUtil is out of the question. ie. a primitive array is needed.

edit: the thread "Java Arrays how to add elements at the beginning" does not have any methods tht follow a primitive array, the solutions are all using lists or other things like ArrayUtil.

[`LinkedList`](https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/LinkedList.html) may work — Andrew Tobilko, Sep 26 '19 at 07:58
Not in an array, but in another structure, like a linked list. Adding an element to the start of an array is O(N) because you have to adjust the position of all the other elements, or copy the contents to a new array. — khelwood, Sep 26 '19 at 07:59
StackOverflow isn't a code-writing service. The purpose of this site is to help with specific code issues. So what code have you written, and what issues are you having with that code? — SSP, Sep 26 '19 at 07:59
Use array list. List has the method add(index, E), so you can use: list.add(0, yourObject); — SSP, Sep 26 '19 at 08:00
[What is the simplest way to add an item to the beginning of a Java array](https://stackoverflow.com/questions/36807712/what-is-the-simplest-way-to-add-an-item-to-the-beginning-of-a-java-array) — khelwood, Sep 26 '19 at 08:03
There are *things* that are not possible... O(1), insert at beginning, only using array, no circular array! Only *solution* I can think of is a pre-allocated array, starting to fill from the middle (or end) - but that is very similar to a circular array or adding elements to the end (and eventually you will need to resize the array). — user85421, Sep 26 '19 at 08:28

score 2 · Answer 1 · answered Sep 26 '19 at 08:01

Java arrays have a "fixed" size. There is no "adding" out of the box. Adding always means: increasing the length of the array, thus: creating a new array and copying over the existing data.

The only solution to get to O(1) would be to look at some "linked list" like implementations of arrays, where adding/inserting elements is solely about adjusting "pointers".

score 2 · Answer 2 · answered Sep 26 '19 at 08:01

Inserting at the beginning of an array requires shifting all of the other elements to the right and dropping the last element. That means it's consistent time-wise for a given size of array (it takes longer the longer the array is). If you're maintaining a count of used entries in the array, then it takes longer depending on how many used entries there are (since you don't have to shift the unused ones). (Which I think means it wouldn't fit your O(1) requirement, but I've never really gotten into Big-O notation...)

It sounds like you might want a linked list, or a ring buffer.

score 0 · Answer 3 · answered Sep 26 '19 at 08:13

As a java array is fixed size, you would need an index anyway (to indicate the length).

The your rejection of a "circular" array could be a mistake.

final int N = 64;
String[] data = new String[N];
int start = 0;
int end = 0; // Exclusive.

int size() {
    return (end - start + N) % N;
}

String get(int i) {
    checkIndex(i);
    int j = (start + i) % N;
    return data[j];
}

void prepend(String s) {
    checkNotFull();
    start = (start - 1 + N) % N;
    data[start] = s;
}

In general data structures like Deque, ArrayDeque, LinkedList and such are normally used.

Insert at front of array

3 Answers3