[java] ArrayList vs LinkedList

ArrayList

배열은 크기가 지정되면 고정되지만 ArrayList는 크기 고정과 상관 없이 추가 삭제를 진행할 수 있다. 하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업이 진행된다. 즉, ArrayList는 겉 보기에 리스트 같지만, 내부적으로는 배열로 존재한다.

 

기본적으로 new ArrayList<>()를 하게 되면 위와 같은 생성자가 호출되는데, 이때 기본적으로 ArrayList의 크기(capacity)는 10으로 지정되어 있다.

 

 

 

여기서 원소 10개 이상을 add했을 경우에는 다음과 같이 배열을 옮기는 과정이 발생한다.

 

cf. 위 add 메소드에서 볼 수 있듯이 ArrayList는 elementData[] 라는 배열로 관리된다.

 

ArrayList의 원소 개수가 배열의 길이와 같게 될 경우 배열 크기를 늘려줘야하는데 이 부분은 grow() 메소드에서 진행된다.

 

위 grow()를 보게되면 Arrays.copyOf를 볼 수 있는데 이 메소드에서는 배열의 모든 원소를 더 큰 공간을 갖는 배열로 복사하는 과정이 이루어진다. 따라서 copyOf() 메소드가 많이 실행될 수록 비효율적인 코드라고 말할 수 있다.

 

결론

- ArrayList를 사용할 때에는 최대로 몇 개의 원소가 들어갈 지 생각해보고 사용하자.

- 많은 원소가 들어갈 거라고 생각된다면 초기 용랴을 설정하자. (new ArrayList<>(100))

 

cf. ArrayList에서 용량 초과시 증설하는 배열 크기

- int newCapacity = oldCapacity + (oldCapacity >> 1)

- 즉, 기존ArrayList 크기가 10이였다면 10 + 5 인 15로 사이즈업 한다.

 

 

 

 

LinkedList

구조

https://javarevisited.blogspot.com/2015/02/how-to-find-first-and-last-element-of.html

- 배열 X -> Node로 관리

- first, last referdence와 노드마다 갖는 prev, next가 있음. (즉, 양방향임)

- next, prev가 있는 것으로 보아 doubly linked list임

 

 

 

ArrayList vs ArrayList 연산 별 비교

 

https://www.nextree.co.kr/p6506/

1) add() : 순차적으로 삽입

- ArrayList : 배열의 원소 이동없이 추가됨

- LinkedList : 추가하고자 하는 위치로 탐색 후 위치 결정한 뒤에 해당 위치에 원소 추가

-> 결론: 큰 차이 없음

 

2) add() : 중간위치에 삽입

- ArrayList : 원소들의 위치 이동이 필요하기 때문에 비효율적

- LinkedList : 추가하고자 하는 위치로 이동하기만 하면 바로 삽입 가능

-> 결론 : LinkedList가 효율적

 

3) remove() : 중간위치에서 삭제

- ArrayList : 원소들의 위치 이동이 필요하기 때문에 비효율적

- LinkedList : 삭제하고자 하는 위치로 이동하기만 하면 바로 삭제 가능

-> 결론 : LinkedList가 효율적

 

 

cf. 메모리 구조상 비교

- ArrayList : 랜덤엑세스. 가상화된 JVM 메로리 상 연속된 공간에 데이터들이 인접하여 존재하게 됨.

- LinkedList : 순차접근. JVM 메모리상에 연속해서 존재하지 않고 듬성듬성 존재함

 

 

Reference

- https://www.nextree.co.kr/p6506/