ArrayList는 원소의 중복을 허용하면서, 저장 순서를 유지할 수 있는 선형 자료구조이다.
ArrayList의 특징
ArrayList의 특징을 살펴보면서 ArrayList를 이해해보자.
- ArrayList는 크기가 고정적이고, 데이터의 추가/제거가 번거롭다는 배열의 단점을 보완한 선형 자료구조이다.
- ArrayList는 내부에 갖고 있는 Object[]을 이용해 데이터를 저장한다.
- ArrayList는 크기가 가변적이다.
- 사실 Object[]에 데이터를 저장하기 때문에 크기는 정해져있다.
- 다만 기존 크기를 초과하여 데이터를 추가할 경우, 더 큰 Object[]를 생성하고 기존 배열의 데이터를 복사하여 사용한다.
- ArrayList.size()는 Object[]의 크기가 아닌, 마지막 데이터의 인덱스를 반환하는 것이다.
- ArrayList는 데이터 추가/삭제가 비교적 자유롭다.
- 시작 또는 중간에 새로운 데이터를 추가할 경우, 기존의 데이터는 삭제되지 않고 한 인덱스씩 뒤로 이동한다.
- 시작 또는 중간의 데이터를 삭제할 경우, 해당 인덱스는 빈 공간으로 남아있지 않으며, 그 뒤의 데이터들이 한 인덱스씩 앞으로 이동한다.
ArrayList의 데이터 조작
ArrayList의 데이터 추가
마지막에 데이터 추가
- 단순히 마지막에 데이터를 추가해주면 된다.
시작 또는 중간에 데이터 추가
- 목표 인덱스 이후의 데이터들을 복사하고, 기존 인덱스 + 1에 붙여넣는다.
- 목표 인덱스에 새로운 데이터를 추가한다.
ArrayList의 데이터 삭제
마지막 데이터 삭제
- 단순히 마지막 데이터를 삭제한다.
시작 또는 중간 데이터 삭제
- 목표 데이터 다음의 데이터들을 복사하고, 기존 인덱스 - 1에 붙여넣는다.
ArrayList의 장단점
장점
데이터들이 Object[]에 저장된다. 배열에 저장된 데이터들은 메모리상에 연속적으로 위치하기 때문에 데이터에 대한 접근 속도가 빠르다. 즉 저장된 데이터들의 주소를 바로 알 수 있다.
단점
ArrayList의 데이터 추가/삭제 과정에서 알 수 있듯이, 시작 또는 중간에 위치한 데이터를 추가/삭제할 때 단점이 발현된다.
추가/삭제될 인덱스 이후 또는 다음의 데이터들이 앞 또는 뒤로 이동해야하므로 데이터가 많을 수록 더 많은 시간이 소요된다.
ArrayList 구현
아래는 ArrayList를 실제로 구현한 코드이다.
주석을 참고하여 ArrayList의 동작 방식을 이해해보자.
ArrayList 구현부
// ArrayList 객체를 생성할 때, Object[]의 타입을 지정하기 위해 제네릭을 사용한다.
public class ArrayList<T> {
private final static int DEFAULT_CAPACITY = 10;
private int size; // 실제 저장된 데이터의 개수
private T[] array; // 저장 공간
// 기본 생성자
// array의 크기는 0으로 초기화한다.
@SuppressWarnings("unchecked")
public ArrayList() {
this.size = 0;
this.array = (T[]) new Object[0];
}
// capacity 인자를 갖는 생성자
// array의 크기를 capacity로 초기화한다.
@SuppressWarnings("unchecked")
public ArrayList(int capacity) {
this.size = 0;
this.array = (T[]) new Object[capacity];
}
// 저장 공간(array)의 가변성을 위한 메소드
@SuppressWarnings("unchecked")
private void resize() {
int curCapacity = array.length; // 현재 저장 공간 크기
// 현재 저장 공간 크기 == 0
if (curCapacity == 0) {
// array를 DEFAULT_CAPACITY 크기로 초기화한다.
array = (T[]) new Object[DEFAULT_CAPACITY];
return;
}
// 현재 저장 공간 크기 == 저장된 데이터 개수
if (size == array.length) {
int newCapacity = curCapacity * 2;
// 현재 저장 공간 크기 * 2의 새로운 배열 생성
// 새로운 배열에 기존 데이터 복사 및 새로운 배열을 array로 지정
array = Arrays.copyOf(array, newCapacity);
return;
}
// 현재 저장 공간 크기 / 2 > 저장된 데이터 개수
if (size < curCapacity / 2) {
int newCapacity = curCapacity / 2;
// 현재 저장 공간 크기 / 2의 새로운 배열 생성
// 새로운 배열에 기존 데이터 복사 및 새로운 배열을 array로 지정
array = Arrays.copyOf(array, newCapacity);
}
}
// 데이터 추가 메소드
public boolean add(T data) {
// 기본적으로 저장 공간 맨 끝에 데이터를 추가하므로 addLast(...) 호출
addLast(data);
return true;
}
// 저장 공간 맨 끝에 데이터를 추가하는 메소드
public void addLast(T data) {
// 데이터 저장 전에 저장 공간 크기 조정
resize();
// 저장 공간 맨 끝에 데이터 저장
array[size] = data;
size++;
}
// 목표 인덱스에 데이터를 저장하는 메소드
public void add(int index, T data) {
// 목표 인덱스가 가능한 범위의 값인지 확인
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 목표 인덱스 == 저장된 데이터 개수 : 저장 공간 맨 끝에 데이터 추가
if (index == size) {
addLast(data);
} else {
// 데이터 저장 전에 저장 공간 크기 조정
resize();
// 목표 인덱스 이후의 데이터들을
// 기존 인덱스 + 1에 복사
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
// 목표 인덱스에 새로운 데이터 추가
array[index] = data;
size++;
}
}
// 목표 인덱스의 데이터를 반환하는 메소드
public T get(int index) {
// 목표 인덱스의 값이 가능한 범위의 값인지 확인
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
return array[index];
}
// 목표 인덱스의 데이터를 변경하는 메소드
public void set(int index, T data) {
// 목표 인덱스의 값이 가능한 범위의 값인지 확인
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
array[index] = data;
}
// 목표 데이터의 첫 번째 인덱스를 반환하는 메소드
public int indexOf(T data) {
// 첫 번째 데이터부터 목표 데이터와 일치하는 지 확인
for (int i = 0; i < size; i++) {
if (array[i].equals(data)) {
// 일치할 경우 인덱스 반환
return i;
}
}
// 일치하는 데이터가 없는 경우 -1 반환
return -1;
}
// 목표 데이터의 마지막 인덱스를 반환하는 메소드
public int lastIndexOf(T data) {
// 마지막 데이터부터 목표 데이터와 일치하는 지 확인
for (int i = size - 1; i >= 0; i--) {
if (array[i].equals(data)) {
// 일치할 경우 인덱스 반환
return i;
}
}
// 일치하는 데이터가 없는 경우 -1 반환
return -1;
}
// 목표 데이터가 저장되어 있는 지 확인하는 메소드
public boolean contains(T data) {
// indexOf(...)는 일치하는 데이터가 없을 때만 -1을 반환한다.
return indexOf(data) >= 0;
}
// 목표 인덱스의 데이터를 삭제하는 메소드
public boolean remove(int index) {
// 목표 인덱스의 값이 가능한 범위의 값인지 확인
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 목표 인덱스 다음의 데이터들을
// 기존 인덱스 - 1에 복사한다.
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
array[i + 1] = null;
}
size--;
// 저장 공간 조정
resize();
return true;
}
// 목표 데이터를 삭제하는 메소드
public boolean remove(T data) {
// 목표 데이터의 인덱스 확인
int index = indexOf(data);
// 목표 데이터의 인덱스가 -1이면 데이터가 존재하지 않는 것
if (index == -1) {
return false;
} else {
// 목표 데이터 삭제
remove(index);
return true;
}
}
// 저장된 데이터 개수를 반환하는 메소드
public int size() {
return size;
}
// 저장된 데이터 존재 여부를 반환하는 메소드
public boolean isEmpty() {
return size == 0;
}
// 저장 공간을 비우는 메소드
@SuppressWarnings("unchecked")
public void clear() {
// 저장 공간을 새로운 배열로 변경
array = (T[]) new Object[size];
size = 0;
resize();
}
// toString() 오버라이딩
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(" " + array[i]);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
사용 예시
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i + 1);
}
System.out.println("list = " + list);
// list = [ 1 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
for (int i = 0; i < 10; i++) {
list.add(i, (i + 1) * 100);
}
System.out.println("list = " + list);
// list = [ 100 200 300 400 500 600 700 800 900 1000 1 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
list.remove(0);
list.remove(Integer.valueOf(1));
System.out.println("list = " + list);
// list = [ 200 300 400 500 600 700 800 900 1000 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.contains(1000) = " + list.contains(1000));
// true
System.out.println("list.contains(100) = " + list.contains(100));
// false
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.indexOf(200) = " + list.indexOf(200));
// 0
System.out.println("list.lastIndexOf(10) = " + list.lastIndexOf(10));
// 17
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.isEmpty() = " + list.isEmpty());
// false
list.clear();
System.out.println("list.isEmpty() = " + list.isEmpty());
// true
}
}