자바 List 쓸 때 보통 그냥 습관적으로 ArrayList 썼는데, 얼마 전에 어떤 글에서 "삽입 삭제 많으면 LinkedList가 빠르다"는 걸 보고 헷갈리기 시작했어요.
둘 다 List 인터페이스 구현이라 겉으로 쓰는 방법은 똑같잖아요. 근데 내부가 다르다고 하니까, 그럼 언제 뭘 골라야 하는지 궁금합니다.
List<Integer> a = new ArrayList<>();
List<Integer> b = new LinkedList<>();
제가 알아본 바로는 ArrayList는 내부가 배열이라 인덱스로 접근하는 get(i)가 빠르고, LinkedList는 노드가 줄줄이 연결된 구조라 중간에 끼워넣는 게 빠르다는데요. 근데 여기서 막히는 게, LinkedList도 중간에 넣으려면 그 위치까지 노드를 하나씩 따라가야 되는 거 아닌가요? 그럼 그 탐색 시간 때문에 결국 느린 거 아닌가 싶어서요.
실제로 제가 백만 개 정도 넣고 리스트 맨 앞에 계속 add(0, x) 하는 테스트를 해봤는데, 확실히 ArrayList가 훨씬 느리긴 했어요. 근데 반대로 for문 돌면서 get(i)로 다 읽는 건 ArrayList가 압도적으로 빨랐고요.
for (int i = 0; i < list.size(); i++) {
sum += list.get(i); // LinkedList에서 이게 왜 이렇게 느리죠?
}
이 get 반복이 LinkedList에서 유독 느린 이유가 뭔가요? 그리고 실무에서 진짜로 LinkedList를 골라야 하는 상황이 있긴 한가요? 주변에서는 그냥 웬만하면 ArrayList 쓰라는데, 그러면 LinkedList는 대체 언제 쓰라고 만들어둔 건지 궁금합니다.