[Java-자료구조] ArrayList vs LinkedList

지금까지 ArrayList와 LinkedList의 특징과 장단점, 구현까지 해보았다.

 

[Java] ArrayList 사용과 구현

 

[Java] LinkedList 사용과 구현

 

Collection Framework에서의 계층구조

LinkedList를 확인하면 Abstract Sequential List를 상속하고 있는 반면, ArrayList의 경우 AbstractList를 상속하고 있다.

즉 구조적인 차이가 나타나는 것을 확인할 수 있다.

data

data

data

data

ArrayList

LinkedList

 

	ArrayList	LinkedList
저장방식	연속적인 메모리 공간	불연속적인 메모리 공간
검색	인덱스 기반의 자료구조로 빠름	모든 요소 탐색이 필요하기에 느림
삽입/삭제	느림	빠름
유리한 상황	데이터의 개수가 자주 변하지 않고 검색, 수정을 자주 할 경우	데이터의 개수의 변경이 잦고 삽입이나 삭제가 자주 일어나는 경우

 

시간 복잡도(Time Complexity)

작업	메소드	ArrayList	LinkedList
데이터 마지막에 추가	add()	O(1) copy op가 필요시 O(N)	O(1)
데이터 중간에 추가	add(int index, Object element)	O(N)	O(N)
index에 위치한 데이터 제거	remove(int index)	O(N)	O(N)
특정 데이터를 제거	remove(Object element)	O(N)	O(N)
index로 데이터 검색/ 수정	get(int index) set(int index, Object element)	O(1)	O(N)
데이터로 index  검색	indexOf(Object element)	O(N)	O(N)