The ready-made version
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<String> queue = new ArrayList<String>();
queue.add("Ravi"); // at the end: fast
queue.add("Meena");
queue.add("Tom");
System.out.println(queue);
System.out.println("first: " + queue.get(0) + ", size: " + queue.size());
queue.add(0, "VIP"); // at the front: everyone shifts right
System.out.println(queue);
queue.remove("Meena"); // find her, then close the gap
System.out.println(queue);
System.out.println("has Tom? " + queue.contains("Tom"));
}
}Output
[Ravi, Meena, Tom] first: Ravi, size: 3 [VIP, Ravi, Meena, Tom] [VIP, Ravi, Tom] has Tom? true
The cost of each method
| Method | What it does | Big-O | Why |
|---|---|---|---|
get(i), set(i, x) | read / change slot i | O(1) | jump straight to the slot |
add(x) | add at the end | O(1) on average | spare room is waiting |
add(0, x) | add at the front | O(n) | every item shifts one place right |
remove(i) | remove slot i | O(n) | items after it shift left |
contains(x), indexOf(x) | search | O(n) | checks items one by one |
size() | count | O(1) | it's a stored number |
Think of it like this: A line of people: joining at the back is easy. Pushing in at the front makes everyone take a step back.
Integer, not int
Lists hold objects, so you write ArrayList<Integer>, never ArrayList<int>. Java converts between int and Integer for you.
Common mistake:
list.remove(3)on anArrayList<Integer>removes the item at index 3, not the number 3. To remove the value, writelist.remove(Integer.valueOf(3)).
Remember: Prefer adding and removing at the end of an ArrayList. If you need lots of work at the front, a different structure (a deque, Module 11) is better.