java.util 패키지의 ArrayList를 봐보면 메소드가 굉장히 많다. 따라서 이들을 모두 구현하는 것보다는 ArrayList 자료형의 특징을 알 수 있는 메소드만 구현을 함으로써, ArrayList가 코드 내부에서 어떻게 동작하는지 위주로 구현을 해보고자 한다.
그동안 자료의 흐름을 그림으로만 눈대중으로 보고 넘어 갔을텐데, 직접 ArrayList를 구현해보면 자연스럽게 자료구조에 대해 심도 깊은 체득이되며, 앞으로의 새로운 자료구조를 만들어서 써야할때 코드를 설계하는 밑바탕이 될 수도 있기 때문에, 그냥 메서드를 가져가 쓰는 것을 넘어 직접 구현 경험을 해보는 걸 권장한다.
List 인터페이스 정의
실제로 ArrayList 클래스는 List 인터페이스를 implements 하여 구현하기 때문에 본 포스팅에서도 이와 비슷하게 인터페이스를 구현하고 추상 메소드를 재정의 해보며, 이른바 클론 데이터 스트럭쳐 코딩을 해보는 시간을 가져볼것이다.
다음은 실제 List 인터페이스에 정의되어 있는 추상 메소드들 중 핵심적인 부분만 발췌하여 나만의 인터페이스인 MyList로 제네릭을 이용하여 정의하였다. 이 MyList 인터페이스를 implements 하여 나만의 MyArrayList를 만들어보자.
public interface MyList<T> {
boolean add(T value); // 요소를 추가
void add(int index, T value); // 요소를 특정 위치에 추가
boolean remove(Object value); // 요소를 삭제
T remove(int index); // 특정 위치에 있는 요소를 삭제
T get(int index); // 요소 가져오기
void set(int index, T value); // 특정 위치에 있는 요소를 새 요소로 대체
boolean contains(Object value); // 특정 요소가 리스트에 있는지 여부를 확인
int indexOf(Object value); // 특정 요소가 몇 번째 위치에 있는지를 반환 (순차 검색)
int lastIndexOf(Object o); // 특정 요소가 몇 번째 위치에 있는지를 반환 (역순 검색)
int size(); // 요소의 개수를 반환
boolean isEmpty(); // 요소가 비어있는지
public void clear(); // 요소를 모두 삭제
}
public class MyArrayList<E> implements MyList<E> {
// ...
}
클래스 필드 정의하기
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5; // 생성자로 배열이 생성될때 기본 용량
private static final Object[] EMPTY_ELEMENTDATA = {}; // 빈 배열
private int size; // elementData 배열의 총 개수(크기)를 나타내는 변수
Object[] elementData; // 자료를 담을 배열
// ...
}
DEFAULT_CAPACITY : 배열이 생성 될 때의 디폴트 할당 용량
EMPTY_ELEMENTDATA : 아무 것도 없는 빈 배열
elementData :실제 MyArrayList에 들어오는 데이터들을 담는 배열 자료
size : elementData배열에 담긴 요소의 총개수(배열 크기)
ArrayList 클래스에 데이터들을 저장하기 위해 내부에 Object 배열이 구현 되어 있다. 이 내부 배열을 가지고 메서드로 조작하여 리스트 자료를 이용하는 것이다.
그런데 여기서 가장 중요한 멤버가 바로 size 변수이다. size는 배열의 크기를 나타내는 변수인데, 어차피elementData.length로 곧바로 배열의 크기를 얻을수 있음에도 불구하고 따로 변수로 분리한 이유는, 자료를 담은 배열elementData의 크기가 MyArrayList 클래스의 크기를 대변해주지 못하기 때문이다. 예를들어 데이터를 add 한다고 하면 배열이 꽉차있는지 비어있는지 확인을하고 추가해야 되는데, 이러한 검사를 size 변수의 값을 비교를 통해 처리하기 때문이다. 또한 적재할 인덱스 위치값으로도 쓰여진다.
리스트의 capacity와 size의 차이를 혼동하지 말아야 한다. capacity는 배열의 전체 공간 용량을 말하는 것이고, size는 배열의 모든 요소의 갯수(크기)를 뜻하는 개념이다.
생성자 구현하기
자바의 ArrayList 사용법을 보면 인스턴스화 할때 파라미터를 주기도 하고 주지 않기도 한다.
파라미터를 줄 경우 미리 지정한 수만큼 공간(capacity)을 할당하는데, 이를 구현하기 위해 생성자를 overloading 처리한다. 또한 사용자가 파라미터에 옳지 않은 값을 줄수도 있으니 이를 캐치하여 잘 분기 처리하여야 한다.
MyArrayList<Object> list2 = new MyArrayList<>();
MyArrayList<Object> list1 = new MyArrayList<>(50);
MyArrayList<Object> list2 = new MyArrayList<>(0);
MyArrayList<Object> list3 = new MyArrayList<>(-50);
// 생성자 (초기 공간 할당 X)
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY]; // 디폴트 용량으로 초기화
this.size = 0;
}
// 생성자 (초기 공간 할당 O)
public MyArrayList(int capacity) {
// 파라미터의 값이 양수일 경우 그대로 용량으로 배열을 생성
if (capacity > 0) {
this.elementData = new Object[capacity];
}
// 파라미터의 값이 0일 경우 인자를 주지 않고 인스턴스화 한 것과 같으니 디폴트 용량으로 초기화
else if (capacity == 0) {
this.elementData = new Object[DEFAULT_CAPACITY];
}
// 파라미터의 값을 음수로 설정할 경우 예외를 발생시키도록 안전하게 설계
else if (capacity < 0) {
throw new RuntimeException(new IllegalAccessException("리스트 용량을 잘못 설정 하였습니다")); // Checked 예외를 Unchecked 예외로 변환
}
this.size = 0;
}
resize 구현하기
리스트와 배열의 가장 큰 차이점은 리스트는 동적으로 크기를 늘렸다 줄였다 할 수 있는 것이다. (가변 배열)
만일 용량(capaciy)가 꽉 차서 빈공간이 없는데 새로운 데이터가 들어오면 배열의 용량을 늘릴 필요가 있다. 반대로 데이터를 삭제해서 들어있는 데이터 갯수에 비해 용량이 너무 크다면 배열을 용량을 줄여 메모리적으로 최적화를 노릴 수도 있다.
resize() 메서드는 리스트에 요소가 추가, 삭제 등의 동작이 될때 기본적으로 호출된다. 그리고 배열의 크기(size)와 배열의 용량(capaciy)을 비교하여, 크거나 작은 경우 이를 감지해서 리사이징을 처리하여 메모리 최적화를 노린다고 보면 된다.
다음과 같이 배열에 데이터가 추가/삭제 될때마다 실행되는 resize() 내부용 메소드 구현하고, size와 capacity를 비교하는 총 3가지의 분기를 구현해준다.
// 클래스 내부에서만 실행되는 메소드이니 private
private void resize() {
int element_capacity = elementData.length; // 현재 배열의 크기를 얻음
// 용량이 꽉찬 경우
if() ...
// 용량에 비해 데이터 양이 적은 경우
if() ...
// 들어있는 데이터가 하나도 없을 경우 (빈 배열 일경우)
if() ...
}
1. 용량이 꽉찬 경우
아래 코드에서 용량의 2배로 설정하는 이유는 넉넉하게 공간을 유지하기 위해서이다. 왜냐하면 resize 메서드가 자주 호출되어 배열을 복사하여 새로 만드는 행위가 빈번히 일어난다면 성능에 마이너스가 될 수 있기 때문이다. 빈 공간은 자동으로 null로 채워지기 때문에 문제는 없다.
다만 자료구조 알고리즘에 따라 확장 기준이 다를수 있다는 점은 유의하자.
// 용량이 꽉찬 경우
if (element_capacity == size) {
int new_capacity = element_capacity * 2; // 넉넉하게 공간을 유지하기 위해 현재 용량의 두배로 설정
elementData = Arrays.copyOf(elementData, new_capacity); // 복사할 배열을 new_capacity 용량 만큼 설정하고 elementData 원소들을 전체 복사해서 넣고 반환 (빈공간은 null)
return;
}
2. 용량에 비해 데이터 양이 적은 경우
적정한 공간을 유지하다 너무 배열 원소가 공간에 비해 적게 들어있을 경우 최적화를 위해 리사이징 하는 작업이다.
크기 계산 기준은 현재 배열 원소 갯수(size)가 현재 배열 용량(capacity)의 절반 보다 작을 경우로 정하였다. 그리고 배열을 복사할때 축소할 배열의 용량을 정할때 Math.max() 메서드를 이용하였는데, 위에서 리스트의 기본 할당 용량을 정하였으니, 이에 대한 원칙을 따르기 위해 절반으로 줄인 용량보다 기본 용량이 더 클 경우 기본 용량으로 설정하기 위해서다.
// 용량에 비해 데이터 양이 적은 경우
if ((element_capacity / 2) > size) {
int half_capacity = element_capacity / 2;
elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY)); // half_capacity 와 디폴트 용량 중 큰걸 복사
return;
}
3.들어있는 데이터가 하나도 없을 경우
만일clear()와 같은 데이터 전체 삭제를 실행할 경우, 더이상 들어있는 배열 원소가 없으니 이때 디폴트 용량으로 배열을 초기화 한다. 이때 빈배열인 것을 확인하기 위해Arrays.equals()메서드를 이용해 비교를 한다.
// 들어있는 데이터가 하나도 없을 경우 (빈 배열 일경우)
if (Arrays.equals(elementData, EMPTY_ELEMENTDATA)) {
elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
return;
}
add 구현하기
자료를 추가하는 메서드는 add(E value) 메서드와 add(int index, E value) 가 있다.
add(E value) : 가장 끝 부분에 추가
add(int index, E value) : 특정 위치에 추가
add(E value)
가장 마지막 부분에 데이터를 넣으면 되니 구현 자체는 어렵지 않다.
@Override
public boolean add(Object value) {
resize(); // 현재 배열이 꽉 차있는 상태이면 리사이징
elementData[size] = value; // size가 원소의 갯수이고, 배열의 인덱스는 0부터 시작하니 결국 추가할 수 있는 마지막 위치를 가리키게 된다.
size++; // 원소가 추가되었으니, 배열 크기를 나타내는 size도 올린다.
return true;
}
이때 유의해서 볼 점은 배열의 인덱스로 size 변수를 사용했다는 점인데, size 값 자체가 배열 안에 있는 요소의 갯수이고, 배열의 index는 0부터 시작하니, 결국은 size 값이 요소 마지막의 다음 위치를 가리키는 것과 다름이 없다. (비어있는 공간중 첫번째 위치)
데이터를 넣으면 마지막으로 size 변수도 반드시 업데이트 해주는 것을 잊지말자. 이를 그림으로 나타내자면 아래 로직대로 흘러가게 된다.
add(int index, E value)
중간에 데이터를 삽입하는 것은 기본 삽입보다 확인해야할 절차가 약간 있다. 왜냐하면 리스트는 데이터가 연속되어 저장되어 있는 배열인데 중간에 빈공간이 있는 채로 요소가 들어있거나 음수가 들어로면 안되기 때문이다.
매개변수로 받아온인덱스 범위가 음수와 같은 옳지 않은 값이 올 경우 (index < 0)
매개변수로 받아온 인덱스 범위가 현재 배열 용량(capacity)보다 초과 되거나, 중간에 빈공간이 남은채로 끝 부분에 추가 하는지 (index > size)
@Override
public void add(int index, Object value) {
// 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생 (리스트는 데이터가 연속되어야함)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// ...
}
만일 요소 중간에 데이터를 삽입한다고 하면, 기존 원소들에 대해 한칸씩 옆으로 이동하는 절차를 구현하여야 한다. 그래야 빈공간이 중간에 생기게 되고 그곳에 값을 삽입할 수 있기 때문이다.
코드를 보기 전에 데이터가 중간에 추가되는 과정을 그린 그림을 먼저 보여 중간 삽입 과정을 이해해보자.
@Override
public void add(int index, Object value) {
// 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생 (리스트는 데이터가 연속되어야함)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// 인덱스가 마지막 위치일 경우
if (index == size) {
add(value); // 그냥 추가
}
// 인덱스가 중간 위치를 가리킬 경우
else {
resize(); // 현재 배열이 꽉 차있는 상태이면 리사이징
// 루프변수에 배열 크기를 넣고, index 위치 까지 순회해서 요소들 한 칸 씩 뒤로 밀어 빈 공간 만들기
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
elementData[index] = value; // index 위치에 요소 할당
size++;
}
}
indexOf 구현하기
배열에서 해당 값이 들어있는 인덱스 위치를 얻는 메서드는 다음과 같다.
indexOf(Object value) : 순차대로 검색해서 위치 반환
LastindexOf(Object value) : 거꾸로 검색해서 위치 반환
만일 찾고자 하는 값이 배열에 중복으로 여러개 들어있으면, 가장 먼저 검색되는 요소의 위치를 반환한다. 그리고 만일 찾고자 하는 값이 없을 경우-1을 반환하도록 설정한다.
유의해야 할 점은 컬렉션에는 무조건 객체만 들어올 수 있기 때문에 요소끼리 비교할 때는 동등 연산자(==)가 아니라 반드시 equals() 메서드로 비교해야 한다.동등 연산자를 쓰면 객체의 주소값을 비교하는 것이기 때문이다.
indexOf(Object value)
ArrayList는 유한한 값과 더불어 null도 저장할 수 있는 자료구조이다. 그런데 null 비교 같은 경우 동등 연사자로 해야하기 때문에 어쩔수 없이 매개변수가 null일 경우가 실질 값인 경우를 나누어야 한다.
@Override
public int indexOf(Object value) {
// 매개변수가 null 일경우 (null 비교는 동등연산자로 행하기 때문에 비교 로직을 분리)
if (value == null) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null) {
return i; // 인덱스 반환
}
}
}
// 매개변수가 실질적인 값일 경우
else {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(value)) {
return i; // 인덱스 반환
}
}
}
return -1; // 찾은 값이 없을 경우
}
LastindexOf(Object value)
순차 검색이 0 에서 size 미만까지 검색한 것이니, 역순 검색은 그 반대인, size - 1 서부터 0 까지 순회하며 검색하면 역순 로직을 구현할 수 있다.
@Override
public int lastIndexOf(Object value) {
if (value == null) {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i] == null) {
return i; // 인덱스 반환
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i].equals(value)) {
return i; // 인덱스 반환
}
}
}
return -1; // 찾은 값이 없을 경우
}
remove 구현하기
요소 제거 메소드의 경우 크게 2가지로 나뉜다.
remove(int index) : 특정 index의 요소를 삭제
remove(Object value) : 특정 요소를 삭제
remove(int index)
어렵게 생각할 필요없이 위에서 다루었던 add(int index, E value) 방식을 거꾸로 구현하면 된다.
@Override
@SuppressWarnings("unchecked")
public E remove(int index) {
// 1. 인덱스가 음수이거나, size 보다 같거나 클경우 (size와 같다는 말은 요소 위치가 빈공간 이라는 말)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. 반환할 값 백업
E element = (E) elementData[index];
// 3. 요소 제거 (명시적으로 요소를 null로 처리해주어야 GC가 수거해감)
elementData[index] = null;
// 4. 배열 요소 이동 (삭제한 요소의 뒤에 있는 모든 요소들을 한 칸씩 당겨옴)
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
elementData[i + 1] = null;
}
// 5. 요소를 제거했으니 size도 감소
size--;
// 6. 현재 배열이 capacity가 너무 남아도는 상태이면 리사이징
resize();
// 7. 백업한 삭제된 요소를 반환
return element;
}
먼저 인덱스가 옳지않은 값이거나 배열 크기(size)보다 큰 경우는 예외를 발생시키도록 한다.
기본적으로 remove() 메서드 스펙은 반환값을 삭제된 요소를 보내기 때문에, 리스트에서 요소를 삭제하기 전에 변수에 백업을 해야한다. 이때 가져오게되는 요소가 Object 타입이라 제네릭 E 타입으로 형변환해줘야 하는데, 형변환 하는 과정에서 경고창이 뜨게 된다. 제네릭 자체가 확인되지 않은 모호한 타입이라 그렇다. 따라서 어차피 리스트에서 제네릭 타입으로만 요소를 다루기 때문에 형 안정성이 확보되므로 @SuppressWarnings("unchecked") 어노테이션을 붙인다. 한마디로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 의미이다.
그리고 해당 위치에 null을 대입함으로써, 기존의 요소의 객체가 가비지 값이 되어 GC가 처리하도록 해준다.
for문을 돌려서 add() 메서드와 같이 이번엔 반대로 순회하여 뒤에 있는 요소들을 한칸씩 앞으로 당겨온다. 이때 적재되어있는 마지막 요소의 위치는 size - 1 인 점을 유의해야 된다. 왜냐하면 앞으로 당겨오는 과정에서 끝 원소 이전까지만 순회하면 되기 때문이다.
요소를 삭제했으면 size 변수값을 줄여주고
혹시나를 위해 리사이징도 해준다.
마지막으로 백업한 삭제된 요소를 반환한다.
@SuppressWarnings("unchecked") 어노테이션은 형 변환시 예외 가능성이 없을 확실한 경우에만 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있기 때문이다.
remove(Object value)
remove(Object value) 메소드는 인덱스로 위치를 찾아서 그 요소를 삭제하는 것이 아닌, 요소 자체를 뒤져서 찾아 삭제하는 동작이다. 이때 중복된 같은 값의 요소가 있을 경우 indexOf() 메서드와 같이 가장 먼저 매칭되는 요소만 삭제된다.
remove(Object value)메소드를 위와 같이 for문으로 일일히 구현해도 되지만, 이번엔 먼저 만들었던 remove(int index) 메서드와 indexOf() 메서드를 재활용하여 조합하여 보다 간단하게 구현할 수 있다.
@Override
public boolean remove(Object value) {
// 1. 먼저 해당 요소가 몇번째 위치에 존재하는지 인덱스를 얻어온다.
int idx = indexOf(value);
// 2. 만약 값이 -1이면 삭제하고자 하는 값이 없는 것이니 그대로 메서드를 종료한다.
if(idx == -1) return false;
// 3. 인덱스를 찾았으면 그대로 remove() 메서드로 넘겨 삭제한다. (remove() 에서 요소 삭제 및 size감소 리사이징 처리)
remove(idx);
return true;
}
get / set 구현하기
add와 remove 까지 구현한 독자분들이라면 이 부분은 쉽게 구현이 가능할 것이다. 잊지말아야 할점은 get과 set 동작 역시 인덱스를 파라미터로 넘겨 리스트 요소를 가져오기 때문에 적절치 않은 인덱스 범위에 대한 예외 처리를 해주어야 된다.
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (E) elementData[index]; // 요소값 반환 (형변환 필요)
}
@Override
public void set(int index, Object value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
elementData[index] = value; // 요소 교체
}
코드를 보면, remove 메서드에서나 get과 set 메서드에서 동일한 범위 체크 if문 코드가 반복되어 코드 중복이 발생하는데, 이를 따로 rangeCheck() 이라는 private 메서드로 빼서 객체의 응집도를 높이는 리팩토링도 가능하다.
기타 요소 구현하기
size 구현
MyArrayList 클래스에서는 size 변수가 private 접근제한자를 갖기 때문에 만일 외부에서 참조가 필요하다면 메서드를 통해 반환하는 식으로 처리해야 한다. 만일 size 변수가 pubilc이라면 외부에서 고의적으로 size값을 바꿔버리면 MyArrayList 동작 자체가 이상해버릴수 있기 때문이다.
@Override
public int size() {
return size;
}
isEmpty 구현
리스트가 비어있는지 아닌지 확인하려면 아주 간단하게 요소의 갯수인 size 변수값이 0인지만 확인하면 된다.
@Override
public boolean isEmpty() {
return size == 0;
}
clear 구현
모든 요소들을 지우기 위해 반복문으로 배열 전체를 순회하여 각 요소 공간에 null을 대입하는 식으로 구성할수도 있겠지만, 생각을 환기하여 그냥 빈 배열을 넣어주면 훨씬 간단하게 구성할 수 있다.
@Override
public void clear() {
elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
size = 0; // 모든 요소를 지웠으니 size도 초기화
}
contains 구현
indexOf() 메소드는 사용자가 찾고자 하는 요소(value)의 위치를 반환하는 메소드였다면, contains() 메서드는 사용자가 찾고자 하는 요소가 존재 하는지 안하는지를 반환하는 메소드다. 찾고자 하는 요소가 존재한다면 true를, 존재하지 않는다면 false를 반환한다. 이 역시 기존의 indexOf() 메서드를 재활용하여 매우 간단하게 구현할 수 있다.
@Override
public boolean contains(Object value) {
// 인덱스값이 0보다 크면 곧 요소의 위치로서 요소가 존재한다는 것이고, 0보다 작으면 -1 로서 요소가 존재하지 않는다는 것이다.
return indexOf(value) >= 0 ? true : false;
}
toString 구현
ArrayList 컬렉션 객체를 그대로 print 했을때 별다른 작업없이 배열로 이쁘게 출력되는 것을 봐왔을 것이다.
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list); // [1, 2, 3, 4]
왜냐하면 ArrayList 클래스에는 Object 클래스의 toString() 메서드를 재정의해서 이쁘게 출력하도록 만들었기 때문이다. 우리의 MyArrayList 컬렉션도 다음과 같이 간단하게 재정의하면 위와 같이 배열을 이쁘게 출력할 수 있다.
@Override
public String toString() {
return Arrays.toString(elementData);
}
ArrayList 실전 구현하기 (심화편)
지금까지 ArrayList의 주요 메서드들을 직접 구현해 보았다. 이정도면 기본적인 ArrayList 자료구조의 동작 원리를 습득하는데 있어 충분할 것이다.
그래도 배열을 조작하는 좀 더 심화적인 기능과 더불어 Collection의 이터레이터(Iterator) 객체의 동작 원리도 알아보고 싶다면 한번 도전해보는 것도 나쁘지 않다.
ListIterator 구현하기
리스트를 순회할때 for문으로도 충분하지만 이터레이터 패턴 기법을 사용해 순회하는 방법도 있는 걸 배웠을 것이다.
ListIterator 인터페이스는 Iterator 인터페이스를 상속받아 여러 기능을 추가한 리스트용 이터레이터 인터페이스이다. Iterator 인터페이스는 컬렉션의 요소에 접근할 때 한 방향으로만 이동할 수 있지만, ListIterator 인터페이스는 양방향으로 이동이 가능하며, 요소의 추가, 삭제 기능도 지원한다.
// ListIterator 객체를 listIterator() 메서드를 통해 받음
ListIterator<Integer> iter = lnkList.listIterator();
// 만일 다음 요소가 있다면 반복
while (iter.hasNext()) {
System.out.println(iter.next()); // 요소를 출력하고 반복 위치를 뒤로 이동
}
// 만일 이전 요소가 있다면 반복
while (iter.hasPrevious()) {
System.out.println(iter.previous()); // 요소를 출력하고 반복 위치를 앞으로 이동
}
그런데 이터레이터라고 해서 무슨 대단한 구조인줄 알겠지만, 사실 그냥 내부 클래스이며, 메서드로 부터 내부 인스턴스 객체를 생성하여 리턴받아 객체의 메서드를 실행하는 것일 뿐이다. (정말 별거없다)
ListIterator 내부 클래스 생성
우선 위의 리스트 이터레이터 사용 코드를 보면 변수의 타입을 ListIterator<E> 인터페이스 타입으로 받는 걸 볼 수있다. 다형성을 이용해 DIP 원칙을 따른 예이다. 이와 똑같이 우리도 MyListIterator 인터페이스를 먼저 만들어준다.
public interface MyListIterator<T> {
T next();
boolean hasNext();
T previos();
boolean hasPrevios();
void add(Object element);
void remove();
}
그리고 ListIterator 내부 클래스를 MyArrayList 클래스안에 중첩으로 선언해주고, 위에서 만든 MyListIterator 인터페이스를 implements 해준다.
ListIterator 내부 클래스는 static 이 아닌 일반 inner class로 선언해주는데, 왜냐하면 외부 클래스 MyArrayList의 내부 배열을 참조하여 사용해야되기 때문이다.
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5; // 생성자로 배열이 생성될때 기본 용량
private static final Object[] EMPTY_ELEMENTDATA = {}; // 빈 배열
// ...
// ...
// ...
// DIP 원칙을 위해 인터페이스를 상속
class ListIterator implements MyListIterator<E> {
private int nextIndex = 0; // 커서 위치
public E next() {
}
public boolean hasNext() {
}
public E previos() {
}
public boolean hasPrevios() {
}
public void add(Object element) {
}
public void remove() {
}
}
// 내부 클래스 ListIterator 객체를 만들어 반환
public ListIterator listIterator() {
return new ListIterator();
}
}
ListIterator 내부 클래스를 만들었으면, 내부 클래스를 인스턴스화 하여 반환해주는listIterator()메서드도 선언해준다. 그러면 클라이언트에서 리스트 이터레이터 객체를 반환받을 준비가 끝나게 된다.
이렇게 이터레이터 자체는 간단하지만, 여기서 유심히 살펴봐야 할 멤버는nextIndex변수이다. nextIndex변수는 이터레이터가 현재 배열 어느 위치를 가리키고 있는지에 대한 이터레이터 전용 커서 역할을 한다.
이 변수를 이용해서 size 처럼 리스트를 차례로 순회를 돌 것이며 또한 값을 반환하기도 할 것이다. 다만 반환과 동시에 커서가 이동하기 때문에, 두뇌를 조금 회전해야 한다.
hasNext 구현
while 문의 반복 요소로 사용되는 멤버이며, 순회할 요소가 남아있는지 체크하는 메서드이다. 배열 요소의 갯수를 나타내는 size 변수값과 nextIndex를 비교하여 구현하면 된다.
@Override
public boolean hasNext() {
// nextIndex가 배열 사이즈보다 작다는 것은 순회할 요소가 남아있다는 뜻
return nextIndex < size();
}
next 구현
리스트 요소를 반환하고 이터레이터 커서를 다음으로 옮기는 메서드이다. 증감연산자를 이용해 반환 및 인덱스 증가 로직을 한 줄로 처리하였다. 그리고 @SuppressWarnings("unchecked") 어노테이션을 통해 제네릭 타입 형변환이 안전하다고 컴파일로 알려준다.
@Override
@SuppressWarnings("unchecked")
public E next() {
// 배열 요소를 반환하고 nextIndex 1 증가
return (E) elementData[nextIndex++]; // elementData[nextIndex] 와 nextIndex++ 를 한줄로 합친 것이다.
}
hasPrevious 구현
hasNext() 메서드의 반대버전이다. 주의할점은 배열의 인덱스가 0부터 시작한다고 해서, 0보다 크거나 같으면 안된다. 왜냐하면 바로 다음에 구현할 preivous 메서드에서의 로직 때문에 그렇다.
@Override
public boolean hasPrevios() {
// nextIndex가 0보다 크면 이전 요소가 남아있다는 뜻
return nextIndex > 0; // 인덱스가 0부터 라고해서 >= 0 이 아니다. previous 메서드에서 --nextIndex를 하기 때문에 0보다 무조건 커야된다.
}
previous 구현
next 메서드의 로직을 반대로 구현하면 되지만, 증감 연산자의 위치가 다르다는 점에 유의하자.
즉, next 로직은 값을 반환하고 커서를 뒤로 이동하는 것이라면, previous 로직은 커서를 앞으로 먼저 이동을하고 나서야 값을 반환한다는 순서의 차이점이 존재한다. 왜냐하면 nextIndex 커서는 반환한 요소 다음 위치를 가리키는 특수한 인덱스 이기 때문이다.
@Override
@SuppressWarnings("unchecked")
public E previos() {
// 배열 요소를 반환하고 nextIndex 1 감소
return (E) elementData[--nextIndex]; // 이때 증감연산자를 앞에다 붙여주어야 한다
}
add / remove 구현
실제 리스트 이터레이터 메서드 목록을 보면 요소를 추가하고 제거하는 기능도 따로 지원한다. 비록 선택적 메서드이긴 하지만, 리스트를 순회하면서 혹여나 수정할 것이 생긴다면 사용하라고 있는 것이다.
처음부터 생으로 구현할 필요없고 이미 add와 remove 기능은 MyArrayList 클래스에서 구현을 하였으니 재활용 하면 된다. 이때 내부 클래스에서 외부 클래스의 메서드를 불러오기 위해서는 정규화된 this 라는 기법을 사용하여야 한다. 상속 관계라면 super를 쓰면 되겠지만, 내부-외부 관계는 상속이 아니기 때문이다.
이때 remove 메서드에서 nextIndex 처리가 약간 복잡한데, nextIndex 자체가 반환한 다음 요소를 가리키는 것이니 previos 메서드 처럼 반드시 1을 감소 시켜야 한다.
@Override
public void add(Object element) {
// 이터레이터 커서 위치에 요소를 추가
MyArrayList.this.add(nextIndex, element);
}
@Override
public void remove() {
// 이터레이터 커서 위치의 전 요소를 제거 (next 메서드 자체가 현재 위치의 요소를 반환하고 커서를 1 더하니까)
MyArrayList.this.remove(nextIndex-1);
// 요소가 배열에서 제거 되었으니 size가 줄어든다. 그리고 커서도 앞으로 당겨야 한다. (요소가 제거되었으니까)
nextIndex--;
}
clone 구현하기
객체를 단순히 = 대입 연산자로 할당하면, 요소가 복사 되는게 아니라 객체 주소가 복사되게 된다. 왜냐하면 기본적으로 컬렉션들은 간단한 정수, 실수라도 모두 Wrapper 객체로 저장하기 때문에, 사실 배열에 적재되어있는 요소들은 값 자체가 적재되어있는게 아니라 주소 번지값이 적재 되어있기 때문이다.
따라서 컬렉션 자체도 객체이고 안에 들어있는 요소도 객체이기 때문에 이들을 완벽히 clone 하기 위해서는 하나하나 순회하여 일일히 요소들을 복사하는 약간 딥(deep)한 작업이 필요하다.
객체 복사를 구현하기 위해서, 자바의 Object 클래스에 있는 clone() 메서드를 재정의하여 구현할 것이다. 이부분은 어려운 파트라 선수 지식이 필요하다. Object 클래스의 clone 메서드 사용법은 다음 포스팅을 참고하길 바란다.
clone 메서드를 재정의하고, CloneNotSupportedException를 throws 한다. (clone의 기본 스펙)
MyArrayList 자체를 복사하여 변수에 저장한다.
이때 복사 과정에서 배열 내용물이 그대로 복사되는데, 이때 복사되는 요소들은 객체 데이터가 아니라 주소 번지들이 복사되어 버린다.
따라서 복사한 MyArrayList의 Object 배열을 재생성하고,
Arrays.copyOf 메서드를 이용해 요소의 객체들을 깊은 복사를 행하도록 한다.
@Override
public Object clone() throws CloneNotSupportedException {
// 1. MyArrayList 자체를 복사하여 변수에 저장
MyArrayList<?> cloneList = (MyArrayList<?>) super.clone();
// 2. 복사한 MyArrayList의 Object 배열에 사이즈를 미리 지정하여 재생성
cloneList.elementData = new Object[size];
// 3. 리스트에 저장하는 데이터는 객체(reference 타입)이기 때문에 반드시 안의 요소들도 따로따로 복사를 해줘야 함
cloneList.elementData = Arrays.copyOf(elementData, size); // 새로운 배열 = Arrays.copyof(원본 배열, 원본 배열에서 복사하고 싶은 요소들의 범위);
return cloneList;
}
정말로 객체의 깊은 복사가 이루어졌는지 확인하기 위해 메인 함수에 다음과 같이 리스트를 직접 만들어서 테스트를 해보자.
public static void main(String[] args) throws Exception {
MyArrayList<Integer> l = new MyArrayList<>();
l.add(new Integer(1));
l.add(new Integer(2));
l.add(new Integer(3));
// 리스트 복사
MyArrayList<Integer> l2 = (MyArrayList<Integer>) l.clone();
// 리스트가 잘 복사되었는지 리스트 주소값이 다른지 비교
System.out.println(l.hashCode());
System.out.println(l2.hashCode());
// 리스트의 요소들이 서로 따로따로 인지 확인
l2.set(1, new Integer(100)); // 복사된 리스트에 다른 값을 대체
l2.add(new Integer(200)); // 복사된 리스트에 다른 값을 추가
// toStirng을 재정의하였으니 배열을 예쁘게 출력
System.out.println(l);
System.out.println(l2);
}
toArray 구현하기
실제 리스트를 배열로 변환하는 toArray() 메서드에는 두가지 종류로 이용된다.
Object[] toArray() : 리스트를 Object[] 배열로 변환하고 그대로 반환
T[] toArray(T[] a) : 리스트를 T[] 배열로 변환하고 매개변수 a에 삽입
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3));
// get list to array (toArray())
Object[] copy1 = list.toArray(); // list를 배열로 변환하고 반환
System.out.println(Arrays.toString(copy1)); // [1, 2, 3]
// get list to array (toArray(T[] a)
Integer[] copy2 = new Integer[10];
Integer[] array = { 100,200,300,400,500,600 };
copy2 = list.toArray(array); // list를 배열로 변환하고 매개변수로 받은 배열에 끼워넣기
System.out.println(Arrays.toString(copy2)); // [1, 2, 3, null, 500, 600]
}
마지막 배열 출력에서 null이 삽입되어 있는 이유는 자바 메서드 스펙이다. javadoc에 따르면 삽입된 리스트의 길이를 알리기 위해서 일부로 null을 넣기 위해서 라고 한다.
첫번째 분기에서는 파라미터 배열의 길이가 해당 ArrayList 객체의 size 보다 작기 때문에 그냥 고대로 복사해서 반환해주면 된다.
두번째 분기에서는 파라미터 배열의 길이가 해당 ArrayList 객체의 size 보다 크거나 같은 경우, 파라미터 배열의 원소들을 유지한채로, 리스트 요소들만 삽입하는 동작이 필요하다. 반복문으로 구현할수도 있지만 System.arraycopy() 메서드를 통해 간단히 구현한다.
null 할당 부분은 솔직히 왜 있는 건지 모르겠지만 스펙이니까 구현해준다. (어디까지 할당되었느냐를 null 표시를 통해 알려주기 위해 스펙상 저리 설계됨)
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] arr) {
// 만약 인자로 받은 배열 공간이 작은 경우
if(arr.length < size) {
// Arrays.copyOf(원본 배열, 복사할 길이)
return (T[]) Arrays.copyOf(elementData, size);
}
// 만약 인자로 받은 배열 공간이 큰 경우
else {
// System.arraycopy(원본배열, 원본배열 시작위치, 복사할 배열, 복사할배열 시작위치, 복사할 요소 수)
System.arraycopy(elementData, 0, arr, 0, size);
if(arr.length > size) arr[size] = null;
return arr;
}
}
ArrayList 구현 전체 코드
MyList.java
public interface MyList<T> {
boolean add(T value); // 요소를 추가
void add(int index, T value); // 요소를 특정 위치에 추가
boolean remove(Object value); // 요소를 삭제
T remove(int index); // 특정 위치에 있는 요소를 삭제
T get(int index); // 요소 가져오기
void set(int index, T value); // 특정 위치에 있는 요소를 새 요소로 대체
boolean contains(Object value); // 특정 요소가 리스트에 있는지 여부를 확인
int indexOf(Object value); // 특정 요소가 몇 번째 위치에 있는지를 반환 (순차 검색)
int lastIndexOf(Object o); // 특정 요소가 몇 번째 위치에 있는지를 반환 (역순 검색)
int size(); // 요소의 개수를 반환
boolean isEmpty(); // 요소가 비어있는지
public void clear(); // 요소를 모두 삭제
}
MyListIterator.java
public interface MyListIterator<T> {
T next();
boolean hasNext();
T previos();
boolean hasPrevios();
void add(Object element);
void remove();
}
MyArrayList.java
class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5; // 생성자로 배열이 생성될때 기본 용량
private static final Object[] EMPTY_ELEMENTDATA = {}; // 빈 배열
private int size; // elementData 배열의 총 요소 개수를 나타내는 변수
Object[] elementData; // 자료를 담을 내부 배열
// 생성자 (초기 공간 할당 X)
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY]; // 디폴트 용량으로 초기화
this.size = 0;
}
// 생성자 (초기 공간 할당 O)
public MyArrayList(int capacity) {
// 파라미터의 값이 양수일 경우 그대로 용량으로 배열을 생성
if (capacity > 0) {
this.elementData = new Object[capacity];
}
// 파라미터의 값이 0일 경우 인자를 주지 않고 인스턴스화 한 것과 같으니 디폴트 용량으로 초기화
else if (capacity == 0) {
this.elementData = new Object[DEFAULT_CAPACITY];
}
// 파라미터의 값을 음수로 설정할 경우 예외를 발생시키도록 안전하게 설계
else if (capacity < 0) {
throw new RuntimeException(new IllegalAccessException("리스트 용량을 잘못 설정 하였습니다")); // Checked 예외를 Unchecked 예외로 변환
}
this.size = 0;
}
// 클래스 내부에서만 실행되는 메소드이니 private
private void resize() {
int element_capacity = elementData.length; // 현재 배열의 크기를 얻음
// 용량이 꽉찬 경우
if (element_capacity == size) {
int new_capacity = element_capacity * 2; // 넉넉하게 공간을 유지하기 위해 현재 용량의 두배로 설정
elementData = Arrays.copyOf(elementData, new_capacity); // 복사할 배열을 new_capacity 용량 만큼 설정하고 elementData 원소들을 전체 복사해서 넣고 반환 (빈공간은 null)
return;
}
// 용량에 비해 데이터 양이 적은 경우
if ((element_capacity / 2) > size) {
int half_capacity = element_capacity / 2;
elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY)); // half_capacity 와 디폴트 용량 중 큰걸 복사
return;
}
// 들어있는 데이터가 하나도 없을 경우 (빈 배열 일경우)
if (Arrays.equals(elementData, EMPTY_ELEMENTDATA)) {
elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
return;
}
}
@Override
public boolean add(Object value) {
resize(); // 현재 배열이 꽉 차있는 상태이면 리사이징
elementData[size] = value; // size가 원소의 갯수이고, 배열의 인덱스는 0부터 시작하니 결국 추가할 수 있는 마지막 위치를 가리키게 된다.
size++; // 원소가 추가되었으니, 배열 크기를 나타내는 size도 올린다.
return true;
}
@Override
public void add(int index, Object value) {
// 인덱스가 음수이거나, 배열 크기(size)를 벗어난 경우 예외 발생 (리스트는 데이터가 연속되어야함)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// 인덱스가 마지막 위치일 경우
if (index == size) {
add(value); // 그냥 추가
}
// 인덱스가 중간 위치를 가리킬 경우
else {
resize(); // 현재 배열이 꽉 차있는 상태이면 리사이징
// 루프변수에 배열 크기를 넣고, index 위치 까지 순회해서 요소들 한 칸 씩 뒤로 밀어 빈 공간 만들기
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
elementData[index] = value; // index 위치에 요소 할당
size++;
}
}
@Override
@SuppressWarnings("unchecked")
public E remove(int index) {
// 1. 인덱스가 음수이거나, size 보다 같거나 클경우 (size와 같다는 말은 요소 위치가 빈공간 이라는 말)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. 반환할 값 백업
E element = (E) elementData[index];
// 3. 요소 제거 (명시적으로 요소를 null로 처리해주어야 GC가 수거해감)
elementData[index] = null;
// 4. 배열 요소 이동 (삭제한 요소의 뒤에 있는 모든 요소들을 한 칸씩 당겨옴)
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
elementData[i + 1] = null;
}
// 5. 요소를 제거했으니 size도 감소
size--;
// 6. 현재 배열이 capacity가 너무 남아도는 상태이면 리사이징
resize();
// 7. 백업한 삭제된 요소를 반환
return element;
}
@Override
public boolean remove(Object value) {
// 1. 먼저 해당 요소가 몇번째 위치에 존재하는지 인덱스를 얻어온다.
int idx = indexOf(value);
// 2. 만약 값이 -1이면 삭제하고자 하는 값이 없는 것이니 그대로 메서드를 종료한다.
if (idx == -1) return false;
// 3. 인덱스를 찾았으면 그대로 remove() 메서드로 넘겨 삭제한다.
remove(idx);
return true;
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (E) elementData[index]; // 요소값 반환 (형변환 필요)
}
@Override
public void set(int index, Object value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
elementData[index] = value; // 요소 교체
}
@Override
public int indexOf(Object value) {
// 매개변수가 null 일경우 (null 비교는 동등연산자로 행하기 때문에 비교 로직을 분리)
if (value == null) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null) {
return i; // 인덱스 반환
}
}
}
// 매개변수가 실질적인 값일 경우
else {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(value)) {
return i; // 인덱스 반환
}
}
}
return -1; // 찾은 값이 없을 경우
}
@Override
public int lastIndexOf(Object value) {
if (value == null) {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i] == null) {
return i; // 인덱스 반환
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i].equals(value)) {
return i; // 인덱스 반환
}
}
}
return -1; // 찾은 값이 없을 경우
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
elementData = new Object[DEFAULT_CAPACITY]; // 기본 용량으로 초기화
size = 0; // 모든 요소를 지웠으니 size도 초기화
}
@Override
public boolean contains(Object value) {
// 인덱스값이 0보다 크면 곧 요소의 위치로서 요소가 존재한다는 것이고, 0보다 작으면 -1 로서 요소가 존재하지 않는다는 것이다.
return indexOf(value) >= 0 ? true : false;
}
@Override
public String toString() {
return Arrays.toString(elementData);
}
class ListIterator implements MyListIterator<E> {
private int nextIndex = 0; // 커서 위치
@Override
public boolean hasNext() {
// nextIndex가 배열 사이즈보다 작다는 것은 순회할 요소가 남아있다는 뜻
return nextIndex < size();
}
@Override
@SuppressWarnings("unchecked")
public E next() {
// 배열 요소를 반환하고 nextIndex 1 증가
return (E) elementData[nextIndex++];
}
@Override
public boolean hasPrevios() {
// nextIndex가 0보다 크면 이전 요소가 남아있다는 뜻
return nextIndex > 0; // 인덱스가 0부터 라고해서 >= 0 이 아니다. previous 메서드에서 --nextIndex를 하기 때문에 0보다 무조건 커야된다.
}
@Override
@SuppressWarnings("unchecked")
public E previos() {
// 배열 요소를 반환하고 nextIndex 1 감소
return (E) elementData[--nextIndex]; // 이때 증감연산자를 앞에다 붙여주어야 한다
}
@Override
public void add(Object element) {
// 이터레이터 커서 위치에 요소를 추가
MyArrayList.this.add(nextIndex, element);
}
@Override
public void remove() {
// 이터레이터 커서 위치의 전 요소를 제거 (next 메서드 자체가 현재 위치의 요소를 반환하고 커서를 1 더하니까)
MyArrayList.this.remove(nextIndex - 1);
// 요소가 배열에서 제거 되었으니 size가 줄어든다. 그리고 커서도 앞으로 당겨야 한다. (요소가 제거되었으니까)
nextIndex--;
}
}
// 내부 클래스 ListIterator 객체를 만들어 반환
public ListIterator listIterator() {
return new ListIterator();
}
@Override
public Object clone() throws CloneNotSupportedException {
// 1. MyArrayList 자체를 복사하여 변수에 저장
MyArrayList<?> cloneList = (MyArrayList<?>) super.clone();
// 2. 복사한 MyArrayList의 Object 배열에 사이즈를 미리 지정하여 재생성
cloneList.elementData = new Object[size];
// 3. 리스트에 저장하는 데이터는 객체(reference 타입)이기 때문에 반드시 안의 요소들도 따로따로 복사를 해줘야 함
cloneList.elementData = Arrays.copyOf(elementData, size); // 새로운 배열 = Arrays.copyof(원본 배열, 원본 배열에서 복사하고 싶은 요소들의 범위);
return cloneList;
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size());
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] arr) {
// 만약 인자로 받은 배열 공간이 내부 배열보다 작은 경우
if (arr.length <= size) {
return (T[]) Arrays.copyOf(elementData, size); // 그냥 복사해서 반환
}
// 만약 인자로 받은 배열 공간이 큰 경우
else {
// System.arraycopy(원본배열, 원본배열 시작위치, 복사할 배열, 복사할배열 시작위치, 복사할 요소 수)
System.arraycopy(elementData, 0, arr, 0, size);
// 내부 배열을 복사한 후 바로 다음에 null을 삽입
if (arr.length > size)
arr[size] = null;
return arr;
}
}
}
마지막으로 직접 구현해본 MyArrayList 컬렉션을 이용해 정말로 실제 ArrayList 처럼 동작하는지 테스트를 해보자.
