코테준비를 하다가 정렬문제를 풀다가 LinkedList 와 ArrayList 중 어느 것을 사용하냐에 따라 시간복잡도가 달라져 따로 정리한다

이 둘은 인터페이스만 같을 뿐 내부적으로 동작하는 방식은 다르다. 두 자료 구조의 차이를 알아보고 LinkedList와 ArrayList를 적절하게 사용하기 위해 본 포스팅을 작성한다.

List 인터페이스를 구현하는 LinkedList 또는 ArrayList는 어떻게 적재적소에 활용할까?

LinkedList vs ArrayList

LinkedList와 ArrayList는 모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체

LinkedList

ArrayList와 같이 데이터의 추가, 삭제시 불필요한 데이터의 복사가 없어서
데이터의 추가, 삭제시에 유리한
반면
데이터의 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다

데이터 삽입과 삭제에 노드를 아는 경우 O(1) 모르는 경우 O(N), 검색에 O(N)

ArrayList

ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사 하는 방법을 사용

데이터의 삽입과 삭제에 O(N), 검색에 O(1)

결론

참조

[Java] 배열(Array) vs. 배열리스트(ArrayList) vs. 연결리스트(LinkedList)
https://www.holaxprogramming.com/2014/02/12/java-list-interface/