ArrayList

List collection을 구현하는 대표적인 클래스. AbstractList 추상 클래스를 상속하고, List를 비롯한 다른 세 interface를 구현한다. 나머지 interface에 대해서는 차차 다루도록 한다.

public class ArrayList 
	extends AbstractList
	implements List, Cloneable, Serialization, RandomAccess

특징

동적 array

List의 기능을 모두 구현하며, 마찬가지로 null과 객체를 상관 없이 저장할 수 있다. 또한 List 를 구현하는 다른 클래스를 ArrayList에 추가할 수도 있다. 동적 array로써 크기를 자유롭게 변경할 수 있다.

ArrayList도 List와 같이 zero-indexed array이며, index를 지정하지 않고 객체를 추가하면 순차적으로 index가 증가한다. 반면 특정 index에서 제거 또는 저장을 수행하면 바로 뒤 index부터 마지막 index까지 모두 앞으로 한 칸 움직여서 다시 정렬한다.

데이터 저장과 삭제 시에 모든 index를 재정렬하므로 이런 작업이 빈번한 곳에서는 ArrayList를 쓰기보다 LinkedList나 HashMap 등을 사용하는 것이 성능 면에서 좋을 수 있다. 하지만 index를 통해 객체에 접근하거나, 마지막 index에 순차적으로 삽입하는 단순 작업이라면 ArrayList를 쓰는 것이 무난할 것이다. 이는 뒤에 설명할 time complexity를 보면 좀 더 자세히 알 수있다.

capacity와 doubling, time complexity

ArrayList의 기본 capacity는 10으로, 항상 실제 list size보다 크게 설정되어 있다. index가 늘어남에 따라 자동으로 capacity가 doubling, 두 배로 늘어난다. 그리고 doubling 할 때 배열의 크기를 두 배 늘리고, list 내에 있는 값들을 모두 복사하여 옮긴다.

따라서 Capacity가 여유 있을 때 add()를 수행할 경우 time complexity는 O(1)이지만, capacity에 도달하여 doubling 될 때는 값들을 모두 복사하여야 하여야 하므로 값의 개수만큼(n)의 time complexity를 가지게 되어 O(n) worst case가 된다. 하지만 doubling 되는 경우가 단순 저장보다 빈번하지 않기 때문에 O(1)의 성능을 O(n)으로 평가해버리면 불합리할 수 있다. 이럴 때 amortized O(1)이라는 표현을 써서 doubling이 되지 않을 조건일 때 O(1)의 time complexity를 가진다는 것을 표현한다. (이 부분은 내가 알고리즘을 자세히 공부하지 않아서 디테일하게는 모르지만, 정리하여 얻은 부분이다. 기회가 된다면 time complexity와 space complexity에 대해서 공부해봐야겠다.).

get()의 경우 하나의 index에서만 값을 얻어오므로 항상 O(1)의 time complexity를 가진다.

메서드들의 time complexity를 정리해보면 다음과 같다.

• add : amortized O(1). O(n) worst case.
• add(idx, obj): O(n). 지정한 index 뒤로 한 칸씩 밀려나야 하므로 그렇다.
• get: O(1)
• remove, contain, indexOf: linear search 이므로, O(n) (앞 index부터 순차적 으로 iteration)

iteration

Iterable interface를 구현하므로 이를 통해 iteration할 수 있지만, List collection에서는 ListIterator를 제공한다. ListIterator는 bidirectional search를 수행하게 해주며, 이를 통해 List를 구현하는 클래스가 특정 index에서 객체를 저장하거나 삭제할 수 있도록 한다.

List<Integer> list = new ArrayList<Integer>();
	for(int i = 0 ; i<10;i++) {
		list.add(i);
		
	}
	ListIterator<Integer> it = list.listIterator(list.size());
	List<Integer> result = new ArrayList<Integer>(list.size());
		
	while(it.hasPrevious()) { // last index부터 검색가능
		result.add(it.previous());
	}
		
	Collections.reverse(result); // order reverse
	System.out.println(list.equals(result)); // true

또 하나 알 수 있는 점은 List의 경우 index와 저장된 값이 일치하는 두 List의 경우 equals() 수행 시 true를 반환한다는 것이다.

TL;DR

• ArrayList는 List collection의 대표적인 구현 클래스.
• Dynamic array로 크기를 바꿀 수 있음
• get(), add()의 경우 O(1)의 time complexity. 따라서 단순 검색, 마지막 index에 순차적 저장의 경우 성능이 괜찮음.
• 특정 index에 값을 저장, 삭제할 경우 요소를 재배열하게 되어 비효율적일 수 있음(LinkedList가 대안)
• linear search 이므로 remove(), contain(), indexOf()의 경우 O(n).

references :
https://docs.oracle.com/javase/8/docs/api/java/util/List.html
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
https://www.baeldung.com/java-arraylist

time complexity
https://medium.com/@satorusasozaki/amortized-time-in-the-time-complexity-of-an-algorithm-6dd9a5d38045
https://zeddios.tistory.com/60