[Java] ArrayList VS LinkedList

정리

구분	ArrayList	LinkedList
add(끝)	1	1
add(시작)	n	1
add(일반적으로)	n	n
get/set	1	n
indexOf/lastIndexOf	n	n
isEmpty/size	1	1
remove(끝)	1	1
remove(시작)	n	1
remove(일반적으로)	n	n
구현	가변 크기 배열	이중 연결 리스트
초기 용량	10	0
메모리 부담	적음	많음

자료구조 선택하기

• 시작이나 끝 근처에 요소를 추가/제거하는 연산은 LinkedList
• ArrayList 클래스의 유일한 이점은 get/set 메서드
• 이러한 연산이 응용 프로그램의 실행시간에 뚜렷한 영향을 미치지 않는다면, 즉 응용 프로그램이 다른 일을 하느라 대부분 시간을 소모하면 List 구현에 대한 선택은 큰 의미가 없습니다.
• 작업하는 리스트가 매우 크지 않으면 기대하는 성능을 얻기 어려울지도 모릅니다. 
• ArrayList에서 요소들은 한 덩어리의 메로리 안에 나란히 저장되어 거의 낭비되는 공간이 없고, 컴퓨터 하드웨어도 연속된 덩어리에서 종종 속도가 더 빠릅니다. 연결 리스트에서 각 요소는 하나 또는 두 개의 참조가 있는 노드가 필요합니다. 참조는 공간을 차지합니다(때로는 데이터보다 클 수도 있음). 메모리 여기저기에 노드가 흩어져 있으면 하드웨어의 효율이 떨어질 수 있습니다.