ArrayList

https://www.baeldung.com/java-arraylist

 

1. 개요

ArrayList는 Java Core Libraries로 다른 라이브러리를 추가할 필요는 없다.

import java.util.ArrayList;

List는 값의 순서있는 시퀀스를 나타내며 해당 값은 중복될 수 있다.

ArrayList는 배열 위에 구축된 List의 구현체 중 하나며 요소를 추가/삭제할 때 동적으로 확장 및 축소할 수 있다.

요소들은 인덱스 0부터 쉽게 접근할 수 있다.

해당 구현은 다음과 같은 속성이 있다.

• 임의의 값 접근시 시간복잡도 O(1)
• 요소 추가 시간복잡도 O(1)
• 삽입/삭제 시간복잡도 O(n)
• 검색 시간복잡도 정렬되지 않은 배열의 경우 O(n), 정렬된 배열의 경우 O(log n)

2. ArrayList 생성

ArrayList는 제너릭 클래스로 type을 명시해야하며 컴파일러가 type을 보장한다.

 

2.1 기본 인수가 없는 생성자

List<String> list = new ArrayList<>();
assertTrue(list.isEmpty());

 

2.2 배열 크기 수용 생성자

List<String> list = new ArrayList<>(20);

 

2.3 Collection 수용 생성자

Collection<Integer> numbers = IntStream.range(0,10).boxed.collect(toSet());

List<Integer> list = new ArrayList<>(numbers);
assertEquals(10, list.size());
assertTrue(numbers.containsAll(list));

 

3. ArrayList에 요소 추가

리스트의 끝이나 특정 위치에 요소를 추가할 수 있다.

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

list.add(1L);
list.add(2L);
list.add(1, 3L);

assertThat(Arrays.asList(1L, 3L, 2L), equalTo(list));

또한 collection이나 다수의 요소를 한 번에 추가할 수도 있다.

List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L));

LongStream.range(4, 10).boxed()
	.collect(collectingAndThen(toCollection(ArrayList::new), ls -> list.addAll(0, ls)));
assertThat(Arrays.asList(4L, 5L, 6L, 7L, 8L, 9L, 1L, 2L, 3L), equalTo(list));

 

4. ArrayList의 반복 Iterate

두 종류의 반복자가 있다: Iterator과 ListIterator

전자(former)는 단방향 탐색을 지원하고 후자(latter)는 양방향 탐색을 지원한다.

# listIterator
List<Integer> list = new ArrayList<>(
  IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);
ListIterator<Integer> it = list.listIterator(list.size());
List<Integer> result = new ArrayList<>(list.size());
while (it.hasPrevious()) {
    result.add(it.previous());
}

Collections.reverse(list);
assertThat(result, equalTo(list));

hasPrevious: 역방향 순회

hasNext: 순방향 순회

 

5. ArrayList 탐색

Collection을 사용해 검색 동작 확인하기

List<String> list = LongStream.range(0, 16)
  .boxed()
  .map(Long::toHexString)
  .collect(toCollection(ArrayList::new)); // 0 1 2 3 4 5 6 7 8 9 a b c d e f
List<String> stringsToSearch = new ArrayList<>(list);
stringsToSearch.addAll(list); // 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f

 

5.1. 정렬되지 않은 리스트 탐색

요소를 찾기위해서는 indexOf() 또는 lastIndexOf() 메서드를 사용한다.

둘다 객체를 받고 int를 반환한다.

assertEquals(10, stringsToSearch.indexOf("a"));
assertEquals(26, stringsToSearch.lastIndexOf("a"));

만족하는 요소를 모두 찾으려면 Java 8 Stream API의 filter를 사용해 찾을 수 있다.

Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));

List<String> result = stringsToSearch
  .stream()
  .filter(matchingStrings::contains)
  .collect(toCollection(ArrayList::new));

assertEquals(6, result.size());

loop나 iterator를 사용할 수도 있다.

Iterator<String> it = stringsToSearch.iterator();
Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));

List<String> result = new ArrayList<>();
while (it.hasNext()) {
    String s = it.next();
    if (matchingStrings.contains(s)) {
        result.add(s);
    }
}

 

5.2. 정렬된 리스트 탐색

선형 탐색보다는 바이너리 탐색 알고리즘을 사용하는게 빠르다.

List<String> copy = new ArrayList<>(stringsToSearch);
Collections.sort(copy);
int index = Collections.binarySearch(copy, "f");
assertThat(index, not(equalTo(-1)));

 

6. ArrayList 요소 삭제

먼저 요소의 인덱스를 찾고 remove() 메서드를 사용해야 한다.

객체를 받아 탐색하고 첫 번째 요소를 지우는 예시

List<Integer> list = new ArrayList<>(
  IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
); // 0 1 2 3 4 5 6 7 8 9
Collections.reverse(list); // 9 8 7 6 5 4 3 2 1 0

list.remove(0); // 8 7 6 5 4 3 2 1 0
assertThat(list.get(0), equalTo(8));

list.remove(Integer.valueOf(0)); // 8 7 6 5 4 3 2 1
assertFalse(list.contains(0));

하지만 Integer과 같이 boxed type을 사용할때 조심해야 한다.

특정 요소를 삭제하기 위해서 먼저 int 값으로 box 해야한다. 그렇지 않으면 인덱스 값으로 인식해 요소가 제거될 수 있다.

여러 항목을 제거할 수도 있다.

Set<String> matchingStrings
 = HashSet<>(Arrays.asList("a", "b", "c", "d", "e", "f"));

Iterator<String> it = stringsToSearch.iterator();
while (it.hasNext()) {
    if (matchingStrings.contains(it.next())) {
        it.remove();
    }
}