ArrayList

이 글은 Baeldung 사이트 'Guide to the Java ArrayList'를 해석, 정리한 글입니다.

 

ArrayList

ArrayList

ArrayList는 Java Collections Framework 중에 하나이다.

Java Core Library로 사용하려면 import문만 추가해주면 된다.

import java.util.ArrayList;

List Interface를 상속받아 Array를 기반으로 정의된 Class이다.

ArrayList의 Element를 추가/삭제할 때마다 동적으로 크기가 변합니다.

ArrayList 시간복잡도

• Random Access => O(1)
• 할부 시간 복잡도(amortized time complexity) 관점에서 Element 추가 => O(1)
• Element 추가/삭제 => O(n)
• Searching Element
  
  • Unsorted ArrayList => O(n)
  • Sorted ArrayList => O(log n)

ArrayList 생성

ArrayList는 Generic Class이다.

ArrayList를 생성할 때 원하는 type을 Paramter로 넣으면 된다.

// default No-Argument
List<String> list = new ArrayList<>(); 
// List Capacity(초기 용량) 지정
List<String> list = new ArrayList<>(20);
// 다른 Collection을 활용해서 ArrayList 생성
Collection<Integer> numbers = IntStream.range(0, 10).boxed().collect(toSet());
List<Integer> list = new ArrayList<>(numbers);

ArrayList Element 추가

ArrayList는 마지막에 추가할 수 도 중간에 특별한 위치에 추가할 수도 있다.

List<Long> list = new ArrayList<>();

list.add(1L);
list.add(2L);
list.add(1, 3L); // 마지막이 아닌 중간에 insert

// 한번에 여러 Element 추가
List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L));
LongStream.range(4, 10).boxed().collect(collectingAndThen(toCollection(ArrayList::new), ys -> list.addAll(o, ys)));

Iterate Over ArrayList

ArrayList는 Iterator, ListIterator 2가지 Iteraor를 사용할 수 있다.

Iterator는 한 방향으로, ListIterator는 양방향으로 찾아갈 수 있다.

List<Integer> list = new ArrayList<>(
	InStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);

ListInterator<Integer> it = list.listIterator(list.size());
List<Integer> result = new ArrayList<>(list.size());

// reverse 순서로 추가
while (it.hasPrevisous()) {
	result.add(it.previous());
}

ArrayList 검색

보통 ArrayList에서 검색할 때 indexOf, lastIndexOf 2가지 Method를 활용한다.

검색하고자 하는 Element의 Index 값을 Return한다.

Sorted LIst 검색

ArrayList가 정렬되어 있다면 이진탐색으로 좀 더 빠르게 검색할 수 있다.

List<String> copy = new ArrayList<>(stringToSearch);
// 정렬
Collections.sort(copy);
// 이진탐색
int index = Collections.binarySearch(copy, "f");

ArrayList 삭제

remove Method로 Element를 삭제할 수 있다.

Argument로 삭제할 Element Index를 넣어주거나, 삭제할 Element를 넣어준다.

(해당하는 가장 첫번째 Element 삭제)

List<Integer> list = new ArrayList<>(
	IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);
Collections.reverse(list);

// 0번 index Element 삭제
list.remove(0);

// Integer 0 Element 삭제
// Integer Type 일때는 주의!!! (index로 인식할 수 도 있다)
list.remove(Integer.valueOf(0));

[주요용어]

할부 시간 복잡도(amortized time complexity)

가장 오래 걸리는 시간을 추정하는 최악 시간 복잡도(worst-case time complexity)와는 다르게 각 입력이 같은 빈도로 발생한다는 가정 하에 입력 처리시간도 고려한다.