[JAVA] ArrayList vs LinkedList 완벽 정리

1. ArrayList와 LinkedList의 성능 차이

ArrayList와 LinkedList는 중간 삽입/삭제의 시간 복잡도가 모두 O(N)으로 동일합니다. 하지만 실제로는 ArrayList가 더 빠른 경우가 많습니다.

• ArrayList:
  • 내부적으로 배열을 사용하며, 연속된 메모리에 데이터를 저장합니다.
  • 특정 위치를 찾는 데 O(1)로 빠르며, 삽입/삭제 시 데이터 이동이 발생하지만, 캐시 최적화 효과로 인해 성능이 더 좋습니다.
• LinkedList:
  • 노드 기반 자료구조로, 삽입/삭제는 연결만 변경하면 되지만 특정 위치를 탐색하는 데 O(N)이 걸립니다.
  • 메모리가 비연속적이어서 캐시 효율이 떨어지고, 실제로 더 느릴 수 있습니다.

결론: 이론적으로 LinkedList가 유리할 것 같지만, 캐시 친화적인 ArrayList가 더 빠른 경우가 많습니다.

---

2. 삽입/삭제가 빈번할 때 ArrayList가 더 빠른 이유

"삽입/삭제가 많다면 LinkedList가 더 적합하다"는 말을 들어본 적 있으시죠? 이론적으로는 맞지만, 현실에서는 ArrayList가 더 나은 경우가 많습니다.

• ArrayList의 경우:
  • 삽입/삭제 시 요소를 밀거나 당기기만 하면 됩니다.
  • 연속된 메모리를 사용하므로 CPU 캐시 효율이 좋아 성능이 더 빠를 때가 많습니다.
• LinkedList의 경우:
  • 삽입/삭제 위치를 찾기 위해 순차 탐색이 필요합니다.
  • 노드 추가/삭제 시 포인터를 조작하는 작업이 필요해, 삽입/삭제만큼 비용이 더 들어갈 수 있습니다.

정리: 삽입/삭제 작업만을 보더라도, ArrayList의 캐시 효율로 인해 실제로 더 나은 성능을 보이는 경우가 많습니다.

---

3. 앞뒤 삽입/삭제도 ArrayList가 더 빠를까?

앞이나 뒤에 데이터를 삽입/삭제하는 경우, 성능 차이는 작업 위치에 따라 다릅니다.

• 뒤쪽 삽입/삭제:
  • ArrayList와 LinkedList 모두 O(1)로 수행됩니다.
  • ArrayList는 배열 끝에 포인터를 변경하면 끝이고, LinkedList도 마지막 노드에 연결하면 끝나기 때문입니다.
• 앞쪽 삽입/삭제:
  • ArrayList: 첫 번째 위치에 삽입/삭제 시 모든 요소를 한 칸씩 이동해야 하므로 O(N)입니다.
  • LinkedList: 첫 번째 노드의 포인터만 변경하면 되므로 O(1)입니다.

결론: 앞쪽 삽입/삭제는 LinkedList가 더 빠르지만, 뒤쪽 삽입/삭제는 둘 다 O(1)으로 비슷한 성능을 보입니다.

---

4. 기본 용량

• ArrayList: 초기 용량(기본 10) 설정 후, 용량 초과 시 기존 용량의 1.5배로 배열을 확장합니다.
• LinkedList: 별도의 초기 용량 개념이 없으며, 필요한 경우에 노드를 동적으로 생성합니다.

---

5. LinkedList와 ArrayList의 구조적 차이

✨ ArrayList

• 내부적으로 동적 배열로 구성됩니다.
• 메모리가 연속적으로 배치되어 있어 CPU 캐시 효율이 높습니다.
• 삽입/삭제 시 데이터 이동이 필요합니다.

✨ LinkedList

• 각각의 요소가 노드로 존재하며, 각 노드가 다음/이전 노드를 가리키는 포인터를 가집니다.
• 메모리가 비연속적으로 배치되므로 캐시 효율이 낮습니다.
• 삽입/삭제 시 노드 연결만 변경하면 되므로 비용이 낮습니다.

---

6. 왜 LinkedList가 캐시 친화적이지 않은가?

LinkedList는 각 노드가 비연속적인 메모리에 저장됩니다.
이 때문에 캐시 지역성(Cache Locality)이 떨어지게 됩니다.

ArrayList는 배열로 연속적으로 데이터를 저장하므로 캐시 친화적입니다. 하지만, LinkedList는 포인터를 따라가며 노드를 탐색해야 하므로 캐시 효율이 낮아지고 속도가 느려질 수 있습니다.

---

7. 언제 LinkedList를 선택해야 하나?

LinkedList를 선택하는 경우는 아래와 같습니다.

• 삽입/삭제가 매우 빈번하고 특정 위치 탐색이 거의 없는 경우
• 정확한 메모리 관리가 필요한 경우 (각 노드가 독립적으로 관리되므로 필요 없는 노드를 빠르게 제거할 수 있음)
• 메모리 크기 확장이 자주 일어나는 상황 (ArrayList는 배열 크기 확장이 발생할 때 성능 저하가 생길 수 있음)

하지만 대부분의 경우 ArrayList가 더 적합합니다.

---

✨ 핵심 요약

1. ArrayList는 배열 기반으로 캐시 효율이 좋아 대부분의 경우 더 빠릅니다.
2. LinkedList는 삽입/삭제가 많고 탐색이 거의 없는 경우에 적합합니다.
3. 데이터의 접근 패턴과 삽입/삭제 빈도를 고려해 적절히 선택하세요!