[Java] List 인터페이스 - ArrayList 클래스

리스트는 자바에서 제공하는 자료형 중 하나로, 가장 대표적인 클래스로는 ArrayList가 속해있다.
리스트는 배열과 동일하지만 배열은 크기가 고정되어있어 상당히 불편하다. 하지만 리스트는 동적으로 크기가 변하는 큰 장점이 있다.
리스트에 대해 자세히 알아보려고 한다.

 

List를 상속받는 하위 클래스 구성

위의 그림을 보면 List 인터페이스를 상속받는 여러 클래스들이 있다. List 인터페이스와 각 클래스들에 대해 알아보자.

---

List

List는 값들을 순차적으로 나열한 자료구조이다. 인덱스가 존재하고, 값의 중복이 허용된다.

 

주요 메서드

메서드	반환타입	설명
add(E e)	boolean	요소를 맨 끝에 추가
add(int index, E element)	void	요소를 지정된 위치에 추가
clear()	void	모든 요소를 제거
get(int index)	E	지정된 위치의 요소를 반환
indexOf(Object o)	int	요소의 위치를 반환 (없으면 -1)
isEmpty()	boolean	저장된 요소가 없으면 true, 있으면 false
remove(int index)	E	지정된 위치의 요소를 제거
remove(Object o)	boolean	해당 요소를 제거
set(int index, E element)	E	지정된 위치의 요소를 해당 요소로 수정
size()	int	저장된 요소의 수를 반환

---

ArrayList

가장 많이 접하는 클래스가 아닐까 싶다. ArrayList 클래스는 배열을 이용한 자료구조다. 기존 배열의 단점을 보완했는데 아래와 같은 장점이 있다.

• 배열 크기가 부족해지면 내부적으로 알아서 늘려준다.
• 중간 요소 추가 또는 삭제가 일어날 경우 내부적으로 앞으로 당기거나 뒤로 밀어주는 작업을 통해 빈 공간이 없다.

위의 장점들이 실제로 어떻게 동작하는지 알아보자.

ArrayList는 add() 메서드를 수행할 때, 항상 크기 비교를 한다. 만약 할당된 크기만큼 요소가 저장됐다면 add() 메서드 안에서 grow() 메서드가 수행됨으로써 크기를 동적으로 늘린다. 맨 처음 add()가 수행될 때 크기 10인 배열을 생성한다.

DEFAULT_CAPACITY가 10으로 셋팅되어 있는 것을 볼 수 있음.

 

위에서 설명한 것처럼 add() 메서드가 수행될 때, 크기 비교를 하여 grow() 함수가 실행된다.

add() → grow() 메서드 호출

 

그럼 어떻게 값을 유지한채 크기만 늘릴 수 있을까? 그것은 grow() 메서드를 열어보면 바로 알 수 있다.

Arrays.copyOf 메서드를 통해 크기를 늘리는 것을 알 수 있다.

이렇게 ArrayList의 내부 배열 크기를 할당하는 과정을 살펴보았다. 이제 요소를 중간에 추가 또는 삭제를 하는 과정을 살펴보자.

 

ArrayList.add(int index, E element)

중간에 요소를 추가할때 실행되는 메서드이다.  위의 그림을 보면 System.arraycopy 메서드를 통해 index ~ size 만큼의 값을 한칸씩 옆으로 밀고, index에 요소를 저장하는 것을 볼 수 있다.

만약 ArrayList에 1 ~ 5라는 값이 저장되어 있고, add(2, 9) 메서드를 실행하면 아래와 같은 그림 순으로 동작한다.

 

다음으로는 remove() 메서드가 내부적으로 어떻게 동작하는지 알아보자.

---

remove(int index)

해당 메서드도 동일하게 System.arraycopy 메서드를 통해 요소들을 한칸씩 앞으로 당기는 작업을 하는 것을 볼 수 있다.

위의 예제와 동일하게 1~5 값이 저장되어 있고, remove(1) 메서드를 실행하면 아래의 그림과 같은 순서로 동작한다.

 

add, remove 메서드 내부를 확인해봄으로써 우리는 ArrayList가 요소 추가, 삭제 시 값을 앞으로 당기거나 뒤로 미는 shift 작업을 하는 것을 알 수 있었다. shift 작업을 함으로써 ArrayList의 추가, 삭제 시 O(n)의 시간 복잡도를 가진다는 것을 이해할 수 있을 것이다.

따라서 아래와 같이 ArrayList의 장/단점을 정리할 수 있다.

---

장점

• 배열을 사용함으로써 연속적으로 주소가 할당되어 있으므로 검색 성능이 좋다 (O(1)의 시간복잡도)
• 개발자가 크기를 신경 쓸 필요가 없다. (알아서 grow를 해주니까)
• 정적배열보다 중간에 요소를 추가하거나 삭제하는 것이 자유롭다.

단점

• 추가/삭제 시 앞으로 당기거나 뒤로 미는 작업이 필요하므로 검색보다는 성능이 떨어진다. (O(n)의 시간복잡도)