ArrayList와 LinkedList, add/remove 성능이 정반대로 갈리는 지점

문제 발생

대량의 데이터를 앞쪽에 계속 삽입하는 로직에서 ArrayList를 썼더니 데이터가 늘어날수록 삽입 속도가 눈에 띄게 느려졌습니다.

List<String> list = new ArrayList<>();
for (String item : items) {
    list.add(0, item); // 항상 맨 앞에 삽입
}

원인 분석

ArrayList는 내부적으로 배열을 씁니다. 맨 뒤에 추가(add(item))하는 건 대부분 O(1)(가끔 배열이 가득 차서 더 큰 배열로 복사할 때만 O(n))이지만, 중간이나 맨 앞에 삽입하려면 그 뒤에 있는 모든 요소를 한 칸씩 밀어야 합니다 — O(n) 연산입니다. 위 코드처럼 맨 앞에 계속 삽입하면 매번 전체를 미루는 셈이라 전체가 O(n²)이 됩니다.

LinkedList는 내부적으로 이중 연결 리스트입니다. 이미 위치를 가리키는 노드 참조가 있다면 그 자리에 삽입/삭제하는 건 O(1)입니다 — 앞뒤 노드의 포인터만 바꾸면 되고 다른 요소를 옮길 필요가 없습니다. 그래서 맨 앞/맨 뒤에서의 삽입·삭제는 LinkedList가 ArrayList보다 유리합니다.

반대로 임의 인덱스 접근(get(i))은 정반대입니다. ArrayList는 배열이라 인덱스 계산만으로 O(1)에 접근하지만, LinkedList는 그 인덱스까지 노드를 하나씩 따라가야 해서 O(n)입니다 — 이미 다룬 것처럼 LinkedList를 인덱스 for문으로 순회하면 안 되는 이유가 여기서도 이어집니다.

해결 방안

1. **읽기/임의 접근이 많다면 ArrayList**를 씁니다 — 대부분의 실무 케이스가 여기 해당합니다.
2. 맨 앞/맨 뒤에서의 삽입·삭제가 빈번하다면 LinkedList나, 양쪽 끝 삽입·삭제에 특화된 ArrayDeque를 고려합니다. 특히 큐(queue)나 스택(stack)처럼 쓸 거라면 ArrayDeque가 LinkedList보다 대체로 더 나은 성능과 메모리 효율을 보입니다 — Java 공식 문서도 스택/큐 용도로는 LinkedList보다 ArrayDeque를 우선 고려하도록 권장합니다.
3. 중간 삽입이 잦다면 어느 자료구조를 써도 결국 O(n)이 발생할 수 있다는 점을 인지하고, 삽입 패턴 자체를 재검토하거나(예: 뒤에서부터 채우기, 정렬 후 한 번에 구성하기) 다른 자료구조(예: 정렬된 삽입이 필요하면 TreeSet/TreeMap)를 검토합니다.
4. "기본은 ArrayList, 정말 필요한 근거가 있을 때만 다른 구현체"가 실무에서 무난한 원칙입니다 — LinkedList가 유리한 시나리오는 생각보다 드뭅니다.

공식 문서

• Oracle Java Docs: ArrayList
• Oracle Java Docs: LinkedList
• Oracle Java Docs: ArrayDeque — "likely to be faster than Stack... and faster than LinkedList"