[ ArrayList ] ArrayList란?

---

1. ArrayList?

• List 인터페이스를 상속받는 자바 Collection에 속하는 객체
• 크기를 정해 객체 생성을 하고 한 번 크기를 지정하면 수정할 수 없는 배열과는 다르게
  크기 설정 없이 객체 생성할 수 있음. 크기로부터 자유로움
• 부모 클래스(abstract) : AbstractList<E>
• 인터페이스 : List<E>, RandomAccess, Cloneable, Serializable

 

 

 

 

2. Java ArrayList 공식 문서 기반 정리

* List는 클래스 List를 칭하는 말로, '리스트'는 말 그대로 요소/값을 저장하는 리스트, 배열이란 의미로 사용하였습니다.

 

 

ArrayList는 List 인터페이스를 상속받는 리스트로, 사이즈를 재설정할 수 있는 배열이라고 할 수 있다. List 클래스의 메서드를 모두 상속받고 null 포함한 모든 요소(값)를 리스트에 담을 수 있다. 또한, List 인터페이스를 상속받았기 때문에 ArrayList 클래스는 요소를 저장하는 데 사용하는 배열의 사이즈를 조작(변경)할 수 있는 메서드를 제공한다. 동기화되지 않는다는 것만 제외하면 벡터 클래스와 동일하다고 할 수 있다.

▶ 제네릭 명시하지 않는 한 어떤 클래스든 리스트에 추가할 수 있으며 배열과는 다르게 size가 변경되지만 동기화되지 않음

 

 

 

size(), isEmpty(), get(), set(), iterator(), listIterator() 함수는 상수(constant) 시간 동안 동작한다. add() 함수는 분할 상수 시간(amortized constant time) 동안 작동합니다. 즉 add(n)은 O(n) 시간 동안 작동합니다. 그리고 다른 함수들은 대략적으로 말하자면 일련의(linear:순차적인, 연속적인) 시간 동안 작동합니다. 그러나 상수 요소는 LinkedList 객체에 비하면 낮습니다.

▶ 시간 복잡도에 대한 설명이므로 자세히 설명하진 않겠습니다.

 

 

 

ArrayList의 인스턴스(=생성된 개별 개체)는 각각 용량(capacity)을 갖고 있습니다. 이 용량은 요소를 저장하기 위해 쓰이는 배열의 사이즈를 말하며, 항상 최소 리스트의 크기만 한 용량을 갖고 있습니다. ArrayList에 요소가 추가되면 용량은 자동적으로 증가합니다. 증가 정책(growth policy)의 세부 사항은 요소 추가에 일정한 분할 상수 시간(amortized time)이 든다는 사실 외에는 지정되어있지 않습니다. ArrayList의 배열에 많은 요소를 추가하기 전 ensureCapacity() 함수를 사용하면 ArrayList 인스턴스 용량을 미리 증가시키게 되고 이는 증분 재할당(incremental reallocation)의 양을 줄일 수 있습니다.

▶ ArrayList는 내부적으로 배열(array)을 사용하는 클래스이며, 기존에 갖고 있는 배열에 요소가 꽉 차있을 때 요소를 추가하면 2배의 크기인 배열을 새로 생성하고 기존 배열에 있는 값을 새 배열에 복사한 후에 새 배열에 요소를 추가합니다. (이때 기존 배열은 사용하지 않고 새 배열을 기존 배열에 새로 assign하여 사용합니다. 기존 배열은 버림.) ensureCapacity() 함수를 사용하면 배열이 꽉 차있지 않아도 용량을 넉넉히 증가시킵니다.

 

 

 

 

하지만, ArrayList는 동기화되지 않는다(unsyncronized)는 것을 명심하세요. 만약 여러 개의 스레드(Thread)가 어떤 ArrayList 인스턴스에 동시에 접근한다면, 최소 한 개의 스레드에서 리스트 구조를 변경할 테고, 이는 곧 외부적으로 동기화되어야 합니다. 그래야 다른 스레드에서 변경된 값이 반영된 ArrayList를 사용하기 때문입니다. 여기서 구조적 수정이란 요소를 더하거나 빼기. 혹은 배열 되돌리기나 사이즈 재조정하는 것을 말합니다. 참고로 요소의 값을 설정하는 것은 구조적 변경이 아닙니다. 동기화는 일반적으로 자연스럽게 캡슐화(encapsulate)해주는 일부 객체를 통해 ArrayList 인스턴스를 동기화하여 실행됩니다. 만약 동기화를 도와주는 객체가 존재하지 않는다면 ArrayList 인스턴스를 syncronizedList() 메서드를 통해 한 번 감싸줘야 동기화가 이루어집니다. 이 방법이 객체 생성 시 우발적인 비동기화를 막기 위한 최선입니다.

List list = Collections.synchronizedList(new ArrayList(...)); // ArrayList를 메소드가 감싸고 있는 모습

▶ wrap이란 단어 의미처럼 한 번 감싸주는 것을 의미하며 JAVA에서 wrap이란 어떤 값을 내부에 두고 외부를 포장하는 행위를 가리킬 때 사용합니다. 예를 들면 Integer.parseInt(String str)처럼 말이죠. List는 기본적으로 동기화되는 클래스가 아니어서 동기화되도록 도와주는 객체를 사용하여 여러 개의 스레드가 하나의 인스턴스에 접근해도 값 변동으로 인한 오류가 나지 않게 해 주거나, 위의 코드처럼 syncronizedList 메서드로 한 번 감싸 동기화를 시켜줘야 합니다.

 

 

 

※fail-fast 방식 : 컬렉션 클래스들은 저장된 요소/객체들에 대한 순차적 접근을 제공하는 반면 fail-fast 방식은 순차적 접근 시 컬렉션 객체의 변경이 생길 경우 순차적 접근이 실패하면서 예외를 날리면 접근을 끝내버리는 방식

ArrayList 클래스로부터 반환된 이터레이터(Iterator)와 listIterator 메서드는 fail-fast 방식을 사용합니다. 만약 이터레이터가 생성된 후 어느 때라도 ArrayList에 구조적으로 변경이 발생한다면 예외를 날리면 수행이 종료됩니다. 이터레이터 메서드 중 remove(), add() 메서드를 쓴 것이 아니라면 말이죠.

 

이터레이터는 동시 다발적 수정이 발생하는 상황에서 ConcurrentModificationException이라는 예외를 던져 수행을 종료하는 것이 최선입니다. 구조적 변경에 이미 영향받은 시점에 모호하거나 확실하게 끝맺음할 수 없는 것에 위험을 걸기 보단 말이죠.

▶ ArrayList 구조가 변경되면 이터레이터 수행 자동 종료

 

 

 

일반적으로 말해 동시에 일어나는 비동기적인 수정은 확실하게 보장하는 것이 불가능한 일이기 때문에 이터레이터의 fail-fast 방식 또한 이를 보장할 수 없다는 것을 명심하세요.  fail-fast 이터레이터는 ConcurrentModificationException이 최선입니다. 따라서, 이 예외에 의존하는 프로그램을 작성하면 안 됩니다. fail-fase 수행 방식은 오직 버그를 잡을 때에만 활용해야 합니다.

 

 

 

⊙ ArrayList 글 더보기

2022.12.05 - [JAVA] - [ ArrayList ] size(), isEmpty(), add(), addAll() 구현 01

[ ArrayList ] size(), isEmpty(), add(), addAll() 구현 01

2022.12.07 - [JAVA] - [ ArrayList ] get(), remove(), clear(), removeAll(), retainAll() 구현 02

[ ArrayList ] get(), remove(), clear(), removeAll(), retainAll() 구현 02

2022.12.07 - [JAVA] - [ ArrayList ] indexOf(), lastIndexOf(), contains(), set(), toArray(), subList(), containsAll() 구현 03

[ ArrayList ] indexOf(), lastIndexOf(), contains(), set(), toArray(), subList(), containsAll() 구현 03