Is it possible to add a string to beginning of String array without iterating the entire array.
10 Answers
The only way to do this is to maintain a ring buffer. i.e. you have a counter which remembers where the start is and you move that instead of moving all the entries in the array. This only works because you re-define what the "start" means.
See the source for ArrayDeque which has three fields
86 /**
87 * The array in which the elements of the deque are stored.
88 * The capacity of the deque is the length of this array, which is
89 * always a power of two. The array is never allowed to become
90 * full, except transiently within an addX method where it is
91 * resized (see doubleCapacity) immediately upon becoming full,
92 * thus avoiding head and tail wrapping around to equal each
93 * other. We also guarantee that all array cells not holding
94 * deque elements are always null.
95 */
96 private transient E[] elements;
97
98 /**
99 * The index of the element at the head of the deque (which is the
100 * element that would be removed by remove() or pop()); or an
101 * arbitrary number equal to tail if the deque is empty.
102 */
103 private transient int head;
104
105 /**
106 * The index at which the next element would be added to the tail
107 * of the deque (via addLast(E), add(E), or push(E)).
108 */
109 private transient int tail;
So adding to the start works like this
224 public void addFirst(E e) {
225 if (e == null)
226 throw new NullPointerException();
227 elements[head = (head - 1) & (elements.length - 1)] = e;
228 if (head == tail)
229 doubleCapacity();
230 }
312 /**
313 * @throws NoSuchElementException {@inheritDoc}
314 */
315 public E getFirst() {
316 E x = elements[head];
317 if (x == null)
318 throw new NoSuchElementException();
319 return x;
320 }
Note: it moves the head rather than shifting all the elements down the array.
3 Comments
Jerome
I'm curious. Can you do that with unfixed ring length ? Do you have some example pseudocode ?
Peter Lawrey
@Jerome Added code from ArrayDeque which is not fixed. It doubles the size of the array when required to do so.
gaoagong
Looking back at the original question... if you start out with a string array, creating an ArrayDequeue also iterates the entire array. Inside ArrayDeque
private void copyElements(Collection<? extends E> c) { c.forEach(this::addLast); }try
String[] a = {"1", "2"};
String[] a2 = new String[a.length + 1];
a2[0] = "0";
System.arraycopy(a, 0, a2, 1, a.length);
answered Jan 10, 2013 at 10:49
Evgeniy Dorofeev
137k31 gold badges209 silver badges288 bronze badges
5 Comments
Peter Lawrey
-1 This will of course iterate over all the elements in the array.
Serid
@PeterLawrey you can't prepend a value to array without copying all following elements, therefore answer is optimal and does not deserve a -1.
Peter Lawrey
@Serid the ArrayDeque doesn't do this.
algrid
@PeterLawrey ArrayDeque isn't an array.
Peter Lawrey
@algrid It's implemented on top of an array and allows you to insert or remove from the start efficiently.
If you're already using Guava you can use ObjectArrays::concat to do this:
String[] args = ...;
ObjectArrays.concat("prepended", args);
Comments
This is corrected version of solution proposed by @matteosilv:
String[] myArray= {"hi","hi2"};
List<String> list = new LinkedList<String>(Arrays.asList(myArray));
list.add(0, "h3");
myArray = list.toArray(new String[list.size()]);
Comments
You cant...You have to move all the strings coming after it forward to accommodate the new string. If you are directly adding it to 0th index, you will lose the previous element there
Comments
String[] myArray= {"hi","hi2"};
List<String> temp = new ArrayList<String>(Arrays.asList(prova));
temp.add(0, "h3");
myArray = temp.toArray(new String[temp.size()]);
1 Comment
Daniil Shevelev
Actually your solution does not work asis. Here is why: stackoverflow.com/a/2965808/1515058 This will work: String[] myArray= {"hi","hi2"}; List<String> list = new LinkedList<String>(Arrays.asList(myArray)); list.add(0, "h3"); myArray = list.toArray(new String[temp.size()]);
You can use streams
private Object[] prepend(String prefix, String[] row) {
Stream<String> stream = Stream.concat(Arrays.asList(prefix).stream(), Arrays.asList(row).stream());
return stream.toArray();
}
calling
prepend("one",new String[]{"two","three","four"})
result
$1 ==> Object[4] { "one", "two", "three", "four" }
Comments
To do that, you should use List.
And if you want to particularly use the arrays internal, go for an ArrayList
2 Comments
sr01853
You cannot do a getFirst(...), getLast(...), addFirst(...), addLast(...), removeFirst(...), or removeLast(...) with an ArrayList. It doesn’t provide extra methods for easy operation on the list’s ends, as LinkedList does
xagyg
@Sibi I think you'll find you can with add(int index, E e) ... see here docs.oracle.com/javase/6/docs/api/java/util/…
Best I can manage ...
public static void main(String[] args) {
String[] s = new String[] { "a", "b", "c" };
System.out.println(Arrays.toString(prepend(s,"d")));
}
public static String[] prepend(String[] a, String el) {
String[] c = new String[a.length+1];
c[0] = el;
System.arraycopy(a, 0, c, 1, a.length);
return c;
}
1 Comment
xagyg
@EvgeniyDorofeev Nice answer. Beat me to it.
You can do some thing like below
public class Test {
public static String[] addFirst(String s[], String e) {
String[] temp = new String[s.length + 1];
temp[0] = e;
System.arraycopy(s, 0, temp, 1, s.length);
return temp;
}
public static void main(String[] args) {
String[] s = { "b", "c" };
s = addFirst(s, "a");
System.out.println(Arrays.toString(s));
}
}
ArrayList) would be better.