ArrayList

자바의 정석[기초편]으로 공부한 내용을 정리한 글입니다.

 

ArrayList란 무엇인가?

핵심 요약:

• ArrayList는 List 인터페이스를 구현한 클래스이며, 데이터의 저장 순서를 유지하고, 중복을 허용합니다.
• 가장 많이 사용되는 컬렉션 클래스 중 하나입니다.
• 과거의 Vector보다 더 효율적이고 빠르게 작동합니다.

저장 구조:

• 내부적으로 데이터를 배열(Object[]) 에 저장합니다.
• 요소들은 배열의 순서대로 저장됩니다. 즉, 인덱스가 0, 1, 2, ... 이런 식으로 정해진 순서에 맞춰 저장됩니다.
• 배열의 크기를 초과하면 새로운 배열을 만들어 기존 데이터를 복사합니다.

소스 코드의 일부:

public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    transient Object[] elementData; // 실제 데이터가 저장되는 배열
}

• elementData는 Object 타입 배열로 선언되어 모든 종류의 객체를 저장할 수 있습니다.
• transient는 직렬화 대상에서 제외된다는 의미로, 직렬화(serialization)와 관련 있습니다.

 

ArrayList의 요소 추가와 삭제

삭제 동작 원리:

• 삭제할 데이터 바로 아래에 있는 데이터들을 한 칸씩 위로 이동시켜서 빈자리를 메웁니다.
• 마지막 데이터는 null로 변경합니다.
• 그 결과, 데이터의 개수(size)가 1 감소하게 됩니다.

1. data[2] = 3을 삭제한다고 가정.
2. 아래 요소들(data[3] = 4, data[4] = 4)을 한 칸씩 위로 이동합니다.
3. 그 결과 data[2] = 4, data[3] = 4, data[4] = null
4. 전체 size가 하나 줄어듭니다.

시간 복잡도 측면:

• 마지막 요소를 삭제하는 경우: 그냥 null로만 만들면 되기 때문에 빠름 (작업시간 짧음)
• 중간 요소 삭제: 이후 요소들을 전부 한 칸씩 옮겨야 하므로 시간이 오래 걸림.

❗ 중간에 데이터를 추가하는 경우도 마찬가지입니다. 이후 요소를 모두 뒤로 한 칸씩 밀어야 하기 때문입니다.