Introduction
Collection에서 간단하게 자바에서 지원하는 자료구조에 대해서 알아보았습니다. 이번에는 가장 기초가 되는 List, 그 중에서도 가장 일반적인 ArrayList에 대해서 알아보고 이를 직접 자바로 구현해 보겠습니다.
배열 vs ArrayList
리스트는 일렬로 데이터를 배치한 자료구조이기에 아무것도 import하지 않고 사용하는 배열과 비교합니다. 물론 ArrayList는 필드에 배열을 넣어 데이터를 저장하기에 배열에 기반하고 있는 자료구조이긴 합니다. 다만 데이터의 추가, 삭제 등에 있어 사용자 입장 좀 더 편리한 것이 ArrayList 입니다. 내부 코드로 이미 이전에 모든 걸 구현해놓았기 때문입니다.
데이터의 추가 및 삭제와 관련하여 자세히 알아보도록 합시다.
데이터의 추가 및 삭제
배열
배열의 경우에 데이터 추가 및 삭제를 진행하는 방법은 새로운 배열을 만들어서 진행해야 됩니다. 추가의 경우 아래와 같이 (1)새로운 배열을 하나 생성하여서 (2)기존 값들을 새로운 배열에 모두 이동하고 (3)추가된 데이터를 대입하며 (4)새로운 배열을 다시 기존 참조 변수에 대입해야 됩니다.
값 삭제의 경우에도 마찬가지입니다. 삭제로 인해 줄어든 배열을 다시 생성해야 합니다.
어떤 것이 문제인가를 생각해보면 아래와 같습니다.
-
배열이 2개가 필요합니다. 메모리적인 것 뿐만 아니라 무엇보다 다시 생성하기 귀찮습니다.
-
시간복잡도의 문제입니다. 겨우 값 하나를 늘리는데, 값을 넣기 위해서는 기존 길이
n인 배열에서n+1배열을 추가로 생성하고 단 하나만 수정함에도 불구하고 불필요하게 값을 다 옮겨야 합니다. 즉 데이터 하나 추가할 때마다 시간복잡도가O(n)이 되는 꼴입니다.
이를 ArrayList에서는 어떤 방식으로 접근했는지 알아봅시다.
ArrayList
단순하게 이렇게 생각해볼 수 있습니다.
그냥 배열 자체를 크게 만들고 그냥 부족할 때마다 한번에 100개씩 늘리면 안되나요?
단순하게 생각하면 늘리는 과정 자체가 줄기는 합니다. 다만 어느정도 크게 만들어도, 100개씩 늘려도 1억번 진행한다면 최소 100만번은 늘려야되서 거시적인 관점에서는 평균적으로 데이터 하나 추가 시 시간복잡도가 O(n)입니다.
다만, 배열에 여유 공간을 두는 것 자체는 늘리는 과정 자체가 줄어서 좋은 접근이긴 합니다.
그럼 어떻게 늘려야 될지 생각해보면 됩니다. 배열 길이 n이라 둘 때 아래와 같은 아이디어도 생각해볼 수 있습니다.
n + c짜리 배열 대신 c * n 짜리 배열로 만들어줍니다. (c는 상수)
그리고 이렇게 하면 시간복잡도는 놀랍게도 (amortized)O(1) 이 됩니다. 근데 앞에 이상한 amortized가 붙어 있습니다.
완전 엄밀하게 O(1)은 아니고 평균적으로 O(1)이라는 뜻입니다.
만약 N개의 데이터를 집어넣어야되는 상황을 생각해봅니다. 이 때 N을 넣었을 때 딱 공간이 두 배(c = 2)로 늘어나는 시점이라 가정해봅니다. 그러면 처음 길이가 1이라면 N은 다음과 같이 가정할 수 있습니다.
그리고 이를 이용해 총 수행 횟수를 보도록 합니다. 우선 현재 N의 크기에 늘어날 때 자료를 옮기면서 발생하는 모든 수행 횟수를 더해줍니다. 현재 막 늘어난 횟수에 기존까지 이동한 모든 횟수의 누적합을 고려합니다.
그런데 이를 정리해보면 아래와 같습니다.
N번 수행했을 때 O(N)입니다. 그렇다면 1회 실행 시 평균적으로는 O(1)이 됩니다. 정확히는 이것이 바로 (amortized)O(1) 이 됩니다.
그리고 기본적으로 c*n 으로 배열이 증가한다고 했는데, Java에서는 ArrayList의 경우 c = 1.5, 즉 1.5배만큼 증가하고, Vector의 경우에는 c = 2만큼 증가합니다. 시간 및 공간 복잡도를 이유로 1.5배로 설정이 되어 있는데, 구현할 때는 편의상 2배로 하였습니다.
구현
MyList Interface
우선 인터페이스 구현을 해봅니다. 물론 실제로는 이보다 더 많은 메소드를 가진 것이 List이지만, 편의상 핵심 기능만을 넣었습니다. 우선 구현할 인터페이스를 아래와 같이 작성하였습니다.
package com.example.list;
public interface MyList<E> {
void add(E e);
void add(int index, E e);
boolean contains(E e);
E get(int index);
int indexOf(E e);
void remove(int index);
void set(int index, E e);
int size();
}각 메소드, 즉 List의 핵심 기능은 다음과 같습니다.
add(E e): 요소를 맨 끝에 추가합니다.add(int index, E e): 해당 인덱스 위치에 요소를 넣습니다.contains(E e): 요소가 있는지 확인합니다.get(int index): 해당 인덱스에 해당하는 값을 반환합니다.indexOf(E e): 해당 요소의 인덱스를 반환합니다. 없으면 -1을 반환합니다.remove(int index): 해당 인덱스에 해당하는 값을 삭제합니다.set(int index, E e): 해당 인덱스에 해당하는 값을 수정합니다.size(): 리스트의 크기를 반환합니다.
MyArrayList class
List에서 구현해야하는 역할에 맞게, 그리고 ArrayList의 동작 원리에 맞게 MyArrayList class 코드를 작성하였습니다. 특히 신경을 쓴 부분은 아래와 같습니다.
- 모든 것을 받는 Object 배열을 하나 만들어 줍니다. 초기 사이즈는 1이고, 초기 인덱스는 -1입니다.
- 여기서 size는 Object 배열의 크기, index는 배열로 부터 구현되는 리스트의 마지막 인덱스입니다.
- 만약 값이 추가되는데 현재 인덱스가 배열을 잡아 놓은 공간(사이즈) 보다 1이 작은 경우(인덱스가 배열의 끝을 가리기고 있는 경우) 배열을 2배로 늘려주는
doubling()메소드가 실행됩니다. System.out.println(list)와 같이 출력할 경우toString()을 통해 현재 리스트를 보여줍니다.
package com.example.list;
public class MyArrayList<E> implements MyList<E> {
private Object[] array;
private int size;
private int index;
public MyArrayList() {
super();
this.size = 1;
this.array = new Object[this.size];
this.index = -1;
}
public void doubling() {
this.size = this.size * 2;
Object[] newArray = new Object[this.size];
for(int i = 0; i < array.length; i++) {
newArray[i] = array[i];
}
this.array = newArray;
System.out.println("Doubling! " + this.size / 2 + " -> " + this.size);
}
@Override
public void add(E e) {
add(this.index + 1, e);
}
@Override
public void add(int index, E e) {
if(index < 0 || index > this.size()) {
throw new IndexOutOfBoundsException("Index: "+ index + ", Size: " + this.size());
}
if(this.index == this.size - 1) {
doubling();
}
for(int i = this.index; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = e;
this.index++;
}
@Override
public boolean contains(E e) {
for(int i = 0; i <= this.index; i++) {
if(array[i].equals(e)) {
return true;
}
}
return false;
}
@Override
public E get(int index) {
return (E)array[index];
}
@Override
public int indexOf(E e) {
for(int i = 0; i <= this.index; i++) {
if(array[i].equals(e)) {
return i;
}
}
return -1;
}
@Override
public void remove(int index) {
for(int i = index; i < this.index; i++) {
array[i] = array[i + 1];
}
this.index--;
}
@Override
public void set(int index, E e) {
array[index] = e;
}
@Override
public int size() {
return this.index + 1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for(int i = 0; i <= this.index - 1; i++) {
sb.append((E)array[i]).append(", ");
}
if(this.index >= 0) sb.append((E)array[this.index]);
sb.append("]");
return sb.toString();
}
}실행
package com.example.list;
public class MyArrayListRun {
public static void main(String[] args) {
MyList<Integer> list = new MyArrayList<>();
System.out.println(list); // []
list.add(1);
System.out.println(list); // [1]
list.add(2); // Doubling! 1 -> 2
System.out.println(list); // [1, 2]
list.add(3); // Doubling! 2 -> 4
System.out.println(list); // [1, 2, 3]
System.out.println(list.indexOf(3)); // 2
System.out.println(list.size()); // 3
list.remove(1);
System.out.println(list); // [1, 3]
list.add(1, 4);
list.add(1, 5);
list.add(0, 6); // Doubling! 4 -> 8
System.out.println(list); // [6, 1, 5, 4, 3]
System.out.println(list.contains(7)); // false
list.set(1, 7);
System.out.println(list); // [6, 7, 5, 4, 3]
System.out.println(list.contains(7)); // true
for(int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " "); // 6 7 5 4 3
}
System.out.println();
}
}참고
