ArrayList vs LinkedList

모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체이다. 하지만 인터페이스만 같을 뿐 내부적으로 동작하는 방식은 다르다.

 

ArrayList

- 내부적으로 데이터를 관리.

- 데이터 추가/ 삭제를 위해 임시 배열을 생성해 데이터를 복사

- 인덱스 기반 자료구조이기 때문에 검색에 유리

- 대량의 자료를 추가/삭제 하는 경우 그만큼 데이터의 복사-> 성능 저하

 

LinkedList

- 데이터를 저장하는 각 노드는 이전 노드와 다음 노드 상태만 알고 있다. 

- 추가/ 삭제 시 불필요한 데이터 복사가 없어 데이터 추가/ 삭제에 유리

- 검색 시, 인덱스가 없기 때문에 처음부터 노드 순회-> 성능 저하

---

데이터 검색, 삽입, 삭제 시 성능 비교

검색

- ArrayList: O(1). 인덱스 기반 자료구조

- LinkedList: 최악의 경우, O(N)

 

삽입, 삭제

- ArrayList: 최악의 경우, O(N)

- LinkedList: O(1). 이전 노드, 다음 노드를 참조하는 상태만 변경하면 됨.