ArrayList vs LinkedList 정리

1.1 ArrayList란?

• 동적 배열(dynamic array) 기반 자료구조
• 인덱스를 이용한 빠른 조회(O(1))

특징:

• 초기 용량(capacity)을 넘어가면 크기를 두 배로 확장한다.
• 삽입/삭제 시 인덱스를 밀어야 하므로 느리다.

---

1.2 LinkedList란?

• 이중 연결 리스트(doubly linked list) 기반 자료구조
• 각 노드가 이전 노드, 다음 노드를 참조한다.

특징:

• 삽입/삭제는 빠르다 (포인터 조작만으로 가능)
• 조회는 느리다 (앞에서부터 하나씩 탐색)

---

1.3 성능 비교

연산	ArrayList	LinkedList
get(index)	O(1)	O(n)
add(맨 뒤)	O(1) (가끔 O(n))	O(1)
add(중간 삽입)	O(n)	O(n)
remove(중간 삭제)	O(n)	O(n)

---

1.4 예제 코드

List<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
System.out.println(arrayList.get(1)); // B

List<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
System.out.println(linkedList.get(1)); // B (하지만 내부 탐색 필요)

---

1.5 언제 ArrayList? 언제 LinkedList?

• 조회가 많고, 삽입/삭제가 적은 경우 ➔ ArrayList
• 삽입/삭제가 많고, 인덱스 기반 접근이 적은 경우 ➔ LinkedList

실무 팁:

• 대부분의 경우 ArrayList를 사용한다. (LinkedList는 특별한 경우에만)

---

1.6 총정리

• ArrayList는 조회 성능이 강점이다.
• LinkedList는 삽입/삭제 성능이 강점이다.
• 메모리 구조(연속/비연속)를 이해하고, 상황에 따라 선택해야 한다.

---