참고자료:
김영한의 실전 자바 - 중급 2편 | 김영한 - 인프런
김영한 | 자바 제네릭과 컬렉션 프레임워크를 실무 중심으로 깊이있게 학습합니다. 자료 구조에 대한 기본기도 함께 학습합니다., 국내 개발 분야 누적 수강생 1위, 제대로 만든 김영한의 실전
www.inflearn.com
지금까지 그저 사용하기만 했던 ArrayList를 직접 구현해 보고 어떤 원리로 동작하는지 자세히 이해해 보자.
단계별로 밟아나가면서 점차 완성시켜 보자.
ArrayList는 본인의 데이터를 결국 배열이라는 자료 구조로 관리하고 사용한다. 그래서 말 그대로 'Array'List이다.
CustomArrayList
package org.example.collection.array;
public class CustomArrayList {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
}
기본틀을 만들자. 지금까지 사용해 왔던 ArrayList는 어떤 타입이든 받아들일 수 있었다. 그것은 결국 모든 타입을 다 허용해 주는 Object 타입의 배열을 사용한다는 것을 의미한다. 그래서 다음과 같이 필드를 선언한다.
private Object[] elements;
그리고 또 한 가지 가장 많이 사용되는 메서드 중 하나인 size()는 별 게 아니다. 그저 자신이 가지고 있는 size라는 필드를 반환할 뿐이다.
private int size;
...
public int size() {
return size;
}
그다음 배열은 항상 고정된 사이즈가 있다. 그 고정된 사이즈를 기존에 ArrayList를 사용하면서 사이즈를 직접 명시한적은 거의 없다. 일반적으로 다음과 같이 사용했을 것이다.
List<String> strings = new ArrayList<>();
이렇게 사용해도 상관없는 이유는 이 클래스는 DEFAULT_CAPACITY라는 상수를 가지고 있기 때문이다.
private static final int DEFAULT_CAPACITY = 5;
그래서 생성자로는 이렇게 명시하지 않으면 기본 사이즈로 배열을 생성하고 명시하는 값을 집어넣으면 그 사이즈로 배열의 사이즈를 초기화한다.
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
이게 ArrayList의 초기 틀이다. 생각보다 간단하다. 그다음 이 ArrayList에서 가장 많이 사용했던 메서드가 뭔가? `add()`다.
public void add(Object element) {
elements[size++] = element;
}
완전한 소스는 아니지만 이게 가장 핵심이다. 추가한 후 본인의 사이즈를 하나 증가시키는.
근데, 이제 만약 배열이 꽉 찬 상태에서 추가를 하려고 하면? 배열은 그렇게 할 수 없다. 근데 우리가 사용했던 ArrayList는 잘만 됐다. 그 이유가 여기에 있다.
public void add(Object element) {
if (size == elements.length) {
elements = Arrays.copyOf(elements, size * 2);
}
elements[size++] = element;
}배열의 사이즈가 꽉 찼다면, 더 큰 배열을 새로 만들어서 그 배열로 바꿔치기 하는 것이다. copyOf() 메서드는 기존 배열을 그대로 카피하는데 사이즈를 전달받은 크기로 만들어버리는 메서드이다. 그렇게 새로 만들어진 배열의 참조값을 elements에 할당해서 elements가 새로운 참조값을 참조하도록 한다. 그러고 난 후 그 배열에 새로운 값을 추가한다. 그럼 기존에 참조하고 있던 배열은? `GC` 대상이 된다.
그리고 사이즈를 늘려서 새로운 배열을 만드는 저 코드는 이곳저곳 많이 사용되니까 메서드로 뽑아낸다.
private void grow() {
elements = Arrays.copyOf(elements, size * 2);
}
add() 메서드는 이것만 있는게 아니라 특정 위치(인덱스)에 추가하는 것도 있다.
public void add(int index, Object element) {
if (size == elements.length) {
grow();
}
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
}뭐 좀 알수 없는 코드가 추가됐다. 생각해보면 만약 마지막 인덱스에 값을 추가하는 거라면 아무런 상관없이 거기에 딱 넣고 끝나겠지만, 중간이나 처음에 넣는거라면 기존에 있던 값들은 다 한칸씩 오른쪽으로 밀어야한다. 그 한칸씩 오른쪽으로 미는 코드가 이 코드이다.
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}근데 무턱대고 다 밀어버리는게 아니라 내가 지정한 곳에 새로운 값을 넣는다는건 그 곳부터 이후의 값을 한칸씩 밀어야하니까 뒤에서 부터 하나씩 순환해서 그 곳(index)까지만 뒤로 밀어야한다. 다 밀었으면 원하는 위치에 원하는 값을 추가한다.
이쯤 되면 좀 실행해보고 싶어진다. 그리고 결과물도 봐야하니 toString()을 오버라이딩하자.
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}왜 사이즈만큼 카피를 해서 찍어낼까? 주어진 사이즈에 꽉 찬 배열이면 상관이 없겠지만 그게 아니라면 남는 값은 `null`이 들어간다. ArrayList를 사용할 때 toString() 호출하면 `null`을 본적이 없다. 이런 이유 때문이다.
또 자주 사용되는 메서드가 뭐가 있을까? 특정 인덱스의 값을 가져오는 메서드 get()이 있다.
public Object get(int index) {
return elements[index];
}
특정 위치의 값을 변경하거나 적용하는 메서드 set()이 있다.
public Object set(int index, Object element) {
Object oldValue = get(index);
elements[index] = element;
return oldValue;
}
CustomArrayListMain
package org.example.collection.array;
public class CustomArrayListMain {
public static void main(String[] args) {
CustomArrayList list = new CustomArrayList();
list.add(1);
list.add(2);
list.add(3);
System.out.println("list = " + list);
}
}실행결과
list = [1, 2, 3]
이쁘게 값을 세 개 넣고 가지고 있는 것을 찍어내는 것까지 해봤다. 이제 넣었으면 지우기도 해야한다. 지워보자.
ArrayList의 대표적인 remove() 메서드는 이렇게 인덱스로, 특정값으로 지우는 두 가지가 있다.
removeAll(), removeFirst(), removeLast()는 생략하도록 한다.
public Object remove(int index) {
if (index < 0 || index >= size) {
return null;
}
Object removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
public boolean remove(Object element) {
Object removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
두 메서드 다 지우고 나서 지운 요소의 인덱스가 비어있지 않도록 한칸씩 앞으로 밀어야한다. 그 코드가 다음 코드.
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
이제 indexOf(Object element) 메서드를 구현해보자. 이 메서드는 주어진 요소가 몇번째 인덱스에 해당하는지 확인하는 메서드.
public int indexOf(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
여기까지의 최종 코드
CustomArrayList
package org.example.collection.array;
import java.util.Arrays;
public class CustomArrayList {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
public void add(Object element) {
if (size == elements.length) {
grow();
}
elements[size++] = element;
}
public void add(int index, Object element) {
if (size == elements.length) {
grow();
}
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
}
public Object remove(int index) {
if (index < 0 || index >= size) {
return null;
}
Object removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
public boolean remove(Object element) {
Object removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
public int indexOf(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
public Object get(int index) {
return elements[index];
}
public Object set(int index, Object element) {
Object oldValue = get(index);
elements[index] = element;
return oldValue;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
private void grow() {
elements = Arrays.copyOf(elements, size * 2);
}
}
이제 실행해서 테스트를 해보자.
CustomArrayListMain
package org.example.collection.array;
public class CustomArrayListMain {
public static void main(String[] args) {
CustomArrayList list = new CustomArrayList();
list.add("Hello");
list.add("Java");
list.add("I Love");
list.add("U");
System.out.println("list = " + list);
Object remove = list.remove(2);
System.out.println("remove = " + remove);
System.out.println("list = " + list);
boolean isDeleted = list.remove("Java");
System.out.println("isDeleted = " + isDeleted);
System.out.println("list = " + list);
int u = list.indexOf("U");
System.out.println("u = " + u);
}
}실행결과
list = [Hello, Java, I Love, U]
remove = I Love
list = [Hello, Java, U]
isDeleted = true
list = [Hello, U]
u = 1
근데 지금 문제가 있는데, 가장 큰 문제는 이 CustomArrayList는 받는 요소의 타입이 Object라는 점이다. 모든 타입이 다 가능하기 때문에 꺼내올 때 그것을 어떤 타입으로 다운 캐스팅해야 할지 확신할 수 없다. 근데 기존에 종종 사용하는 ArrayList는 제네릭을 사용하니까 이 CustomArrayList도 제네릭을 사용해보자.
제네릭 타입 도입하기
CustomArrayList
package org.example.collection.array;
import java.util.Arrays;
public class CustomArrayList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elements;
private int size;
public CustomArrayList() {
elements = new Object[DEFAULT_CAPACITY];
}
public CustomArrayList(int capacity) {
elements = new Object[capacity];
}
public int size() {
return size;
}
public void add(E element) {
if (size == elements.length) {
grow();
}
elements[size++] = element;
}
public void add(int index, E element) {
if (size == elements.length) {
grow();
}
for (int i = size - 1; i > index ; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
}
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
}
E removed = get(index);
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return removed;
}
@SuppressWarnings("unchecked")
public boolean remove(E element) {
E removedItem = null;
int removedIndex = -1;
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
removedItem = (E) elements[i];
removedIndex = i;
break;
}
}
if (removedItem == null) {
return false;
}
for (int i = removedIndex; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size = size - 1;
return true;
}
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
return -1;
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elements[index];
}
public E set(int index, E element) {
E oldValue = get(index);
elements[index] = element;
return oldValue;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
private void grow() {
elements = Arrays.copyOf(elements, size * 2);
}
}코드를 보면 필드로 가진 배열 elements는 여전히 Object타입의 배열이다. 왜 그럴까? 제네릭의 타입 이레이저 때문에 new T[]같은게 불가능하기 때문이다. 결국 컴파일하고 나면 .class 파일은 제네릭이 없어지고 그 자리에 전부 Object로만 남게되는걸 말하는데 그럼 new T는 언제나 new Object가 될 것이므로 제네릭을 사용하는 경우 자바 자체적으로 new, instanceof 키워드는 사용할 수가 없다.
대신, 해당 배열에 넣고 빼고 어떤 요소에 대한 작업이든 다 제네릭의 타입 매개변수를 사용하면 문제를 일으키지 않고 정확히 원하는 타입으로 넣고 뺄 수 있어진다. 그 결과 이 CustomArrayList를 가져다가 사용하는 쪽은 이제 타입 안정성을 보장받을 수 있게 된다.
결론
이렇게 직접 ArrayList를 구현해보니, 안에서 어떤 식으로 동작하는지 완벽하게 이해할 수 있었다. 어떻게 사이즈를 동적으로 계속해서 늘릴수 있는지와 지우거나 중간에 추가할 때 어떻게 기존 배열을 다시 정돈해주는지 등을.
근데, 이 ArrayList는 단점이 있다.
- 사이즈를 늘리고 나서 더이상 사용하지 않으면 불필요하게 메모리를 낭비한다.
- 삽입, 삭제를 중간이나 첫번째에 하는 경우 뒤로 밀거나 앞으로 밀 때 O(n)만큼의 시간이 소요된다.
다음엔 저 두가지의 단점을 해결해주는 LinkedList를 직접 구현해보겠다.
'JAVA의 가장 기본이 되는 내용' 카테고리의 다른 글
| 컬렉션 프레임워크 - List 인터페이스 (0) | 2024.05.13 |
|---|---|
| 컬렉션 프레임워크 - LinkedList 직접 구현해보기 (0) | 2024.05.12 |
| 제네릭 (0) | 2024.05.08 |
| 예외 처리 3 (예외 처리 도입) (0) | 2024.04.23 |
| 예외 처리 2 (예외 계층) (0) | 2024.04.23 |