ArrayList, LinkedList and Vector

Site Admin · 11 Sep 2026 · 11 views

Three List Families

All three implement the List interface with the same behaviour, but they store data in very different ways, which changes performance.

ArrayList

Backed by a growable array. Reading by index is instant because an index maps directly to a memory position. Inserting into the middle requires shifting following elements.

List<String> list = new ArrayList<>();
list.add("A");
list.add("C");
list.add(1, "B");       // insert in the middle
System.out.println(list); // [A, B, C]
System.out.println(list.get(2)); // C - instant access

Random access: O(1)
Insert/delete at the middle: O(n) (shift needed)

LinkedList

Backed by nodes that point to their neighbours. There is no cheap "index", but adding or removing at either end is constant time.

LinkedList<String> queue = new LinkedList<>();
queue.add("first");
queue.add("second");
System.out.println(queue.removeFirst()); // first
System.out.println(queue.removeFirst()); // second

Random access: O(n) (must walk the chain)
Insert/delete at ends: O(1)

LinkedList also doubles as a queue or deque via its addFirst/addLast/removeFirst methods.

Vector

An older, synchronized relative of ArrayList. Its methods are thread safe but slower; for new single-threaded code prefer ArrayList. In a multithreaded setting prefer the collections in java.util.concurrent.

Sorting and Reversing

List<Integer> nums = new ArrayList<>(List.of(5, 2, 8, 1));
Collections.sort(nums);           // [1, 2, 5, 8]
Collections.reverse(nums);        // [8, 5, 2, 1]