개념만 알고 ArrayList 구현 해보기
해당 글은 저의 개념을 바탕으로 자료구조를 구현한 뒤 틀린 부분을 파악해 나가는 과정을 가지고 있습니다.
초반에 틀린 설명으로 시작할 수 있다는 점 유의 부탁드립니다.
자료구조 개념을 다시 복습하는 겸 자바로 다양한 자료구조를 구현하는 과정을 기록해보려고 한다.
다른 사람이 자료구조를 공부할 거면 C언어로 하는 것을 추천하기도 했지만 자바만의 자료구조 구현 방식이 있을 것이고, 개념은 언어의 문제가 아니라 생각했기에 자바로 시작해보려고 한다.
ArrayList
내가 아는 ArrayList의 개념은 다음과 같다.
- 자바의 Collection 프레임워크에 포함된 List의 구현체이다.
- 내부적으로 Array(배열)을 이용해서 구현하고 있다.
- 배열로 이루어져 있기에 조회에 강한 이점을 가지고 있다.
위 개념만 가지고 추가(add), 삭제(remove), 포함여부(contains), 인덱스 조회(indexOf), 비어있는지(isEmpty), 크기(size) 메서드를 구현해보려고 한다.
내가 직접 구현한 ArrayList
추후에 LinkedList를 구현하게 될 것 같아서 기존 Collection처럼 List를 인터페이스로 만들어서 설계를 진행했다.
List 인터페이스
public interface CustomList<T> {
void add(T element);
boolean remove(T element);
boolean contains(T element);
int indexOf(T element);
boolean isEmpty();
int size();
}
1. add
ArrayList에서 add는 O(1) ~ O(N)의 시간을 가지고 있는 것으로 알고 있다.
마지막에 추가할 때는 O(1)의 시간복잡도를 가지고 중간에 삽입하는 경우는 O(N)의 시간 복잡도를 가지게 된다.
중간 삽입의 경우 N번째 인덱스부터 마지막 인덱스까지 데이터를 하나씩 미룬 후 N번째 자리에 삽입해야 하기 때문으로 알고 있다.
일단 내부 변수로 3가지를 선언해 두고 시작한다.
1. 요소를 저장할 Array
2. 초기 용량
3. 현재 사이즈
// 요소 저장
private Object[] elements;
// 초기 용량
private static final int initCapacity = 10;
// 현재 사이즈
private int size = 0;
public ArrayCustomList() {
elements = new Object[initCapacity];
}
초기 용량으로 ArrayList를 생성하게 만들었고 size는 마지막 데이터의 인덱스를 가리키도록 사용한다.
add 메서드는 아래와 같이 구현했다.
// 파라미터를 더하는 메서드
@Override
public void add(T element) {
if (elements.length == size) {
expansionCapacity();
}
elements[size++] = element;
}
처음에 elements의 길이가 size와 같다면 마지막 데이터까지 꽉 찼다고 판단을 진행한다.
이후 expansionCapacity 메서드를 통해 elements의 확장을 진행한 뒤 element를 추가하도록 구현했다.
// 내부 사이즈 확장 메서드
private void expansionCapacity() {
int newCapacity = elements.length * 2;
elements = Arrays.copyOf(elements, newCapacity);
}내부 확장 메서드는 private으로 만들어서 ArrayList에서만 사용하도록 구현했다.
자바에서는 1.5배의 사이즈를 늘리는 것으로 알고 있으나 그냥 2배의 사이즈를 늘리는 것으로 구현을 진행했다.
2. remove
ArrayList에서 remove는 O(N)의 시간 복잡도를 가지는 것으로 알고 있다.
element라는 값을 넣을 경우 해당 값을 전부 찾아야 하기 때문이다.
// 파라미터를 제거하는 메서드
@Override
public boolean remove(T element) {
for (int i = 0; i < size; i++) {
if (elements[i] == null || !elements[i].equals(element))
continue;
elements[i] = null;
for (int j = i + 1; j < size; j++) {
elements[j - 1] = elements[j];
}
elements[--size] = null;
return true;
}
return false;
}
element의 값과 같은 경우만 진행하도록 구현했다. 만약에 같은 경우 해당 자리를 null로 만들고 뒤의 값을 하나씩 당겨주는 방식으로 구현했다.
그리고 마지막에 당겨준 부분까지 null로 초기화를 진행하고 true를 리턴한다.
3. contains
ArrayList에서 contains는 O(N)의 시간 복잡도를 가질 것이라 예상한다.
결국은 배열을 전부 탐색하면서 N과 일치하는 값을 찾아야 하기 때문이라고 생각했다.
// 파라미터가 포함되어 있는지 확인하는 메서드
@Override
public boolean contains(T element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element))
return true;
}
return false;
}
해당 값을 찾으면 true, 없으면 false를 리턴하도록 구현했다.
4. indexOf
ArrayList에서 indexOf는 O(N)의 시간 복잡도를 가질 것이라 예상했다.
N과 일치하는 값을 찾는 건 contains와 같고 boolean 대신 해당 위치의 인덱스를 리턴해주면 되기 때문이다.
// 파라미터가 위치한 인덱스를 반환하는 메서드(없으면 -1을 반환)
@Override
public int indexOf(T element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element))
return i;
}
return -1;
}
5. isEmpty()
ArrayList에서 isEmpty() 메서드는 O(1)의 시간 복잡도를 가질 것이라 생각한다.
내부 변수로 이미 size를 가지고 있기 때문에 size의 값만 확인하면 문제없을 것이라 생각했다.
(물론 이건 size가 잘 관리되고 있다는 가정이 있어야겠지?..)
// List가 비었는지 확인하는 메서드
@Override
public boolean isEmpty() {
return size == 0;
}
6. size()
ArrayList에서 size() 메서드는 O(1) 시간 복잡도를 가질 것이라 생각한다.
이것도 size를 그냥 리턴해주면 될 것이라 판단.
// 현재 리스트의 사이즈를 반환하는 메서드
@Override
public int size() {
return size;
}
테스트
public static void main(String[] args) {
CustomList<Integer> arrayCustomList = new ArrayCustomList<>();
System.out.println("현재 리스트의 크기 : " + arrayCustomList.size());
-> 현재 리스트의 크기 : 0
arrayCustomList.add(15);
arrayCustomList.add(20);
arrayCustomList.add(11);
System.out.println(arrayCustomList);
-> ArrayCustomList{elements=[15, 20, 11, null, null, null, null, null, null, null]}
System.out.println("현재 리스트의 크기 : " + arrayCustomList.size());
-> 현재 리스트의 크기 : 3
System.out.println("현재 리스트의 isEmpty 여부 : " + arrayCustomList.isEmpty());
-> 현재 리스트의 isEmpty 여부 : false
boolean remove = arrayCustomList.remove(10);
System.out.println("10 삭제 여부 : " + remove);
-> 10 삭제 여부 : false
remove = arrayCustomList.remove(11);
System.out.println("11 삭제 여부 : " + remove);
-> 11 삭제 여부 : true
remove = arrayCustomList.remove(15);
System.out.println("15 삭제 여부 : " + remove);
-> 15 삭제 여부 : true
System.out.println(arrayCustomList);
-> ArrayCustomList{elements=[20, null, null, null, null, null, null, null, null, null]}
System.out.println("현재 리스트의 크기 : " + arrayCustomList.size());
-> 현재 리스트의 크기 : 1
System.out.println("현재 리스트의 isEmpty 여부 : " + arrayCustomList.isEmpty());
-> 현재 리스트의 isEmpty 여부 : false
arrayCustomList.add(1);
arrayCustomList.add(3);
arrayCustomList.add(2);
System.out.println(arrayCustomList);
-> ArrayCustomList{elements=[20, 1, 3, 2, null, null, null, null, null, null]}
System.out.println("20의 인덱스 위치 : " + arrayCustomList.indexOf(20));
-> 20의 인덱스 위치 : 0
System.out.println("20 포함 여부 : " + arrayCustomList.contains(20));
-> 20 포함 여부 : true
System.out.println("16 포함 여부 : " + arrayCustomList.contains(16));
-> 16 포함 여부 : false
}
그럼 실제 자바에서와 내가 구현한 방법은 어떤 차이가 있을까?
Java가 구현한 ArrayList
우선 자바에서도 기본 용량, Object 배열, size를 변수로 만들어두었다.
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
생성자로는 초기 용량을 파라미터로 받는 방법, 빈 배열을 할당하는 방법을 사용하고 있다.
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1. add
(1)
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
(2)
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
(1)번 add 메서드를 호출하면 modCount를 1 더해주고 (2)번 add 메서드를 호출한다.
(2)번 메서드의 경우 현재 size와 배열의 길이가 같으면 꽉 찼다고 판단해서 grow() 메서드를 호출해서 배열의 크기를 늘려준다.
이후 값을 할당한 뒤 size를 1 늘려준다.
내부 grow() 메서드는 아래와 같이 구현되어 있다.
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}간단하게 보면 현재 배열 크기의 1.5배를 만들어서 copyOf 메서드를 통해 기존 값을 옮기는 방식이다.
(즉, 값이 꽉 차면 1.5배 크기를 늘린다고 보면 된다)
2. remove
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
우선 파라미터가 null이면 for문을 통해 null을 찾고, 값이 있으면 for문을 통해 es[i]와 값을 비교한다.
일치하는 값이 있다면 fastRemove 메서드를 통해 값을 제거하게 된다.
fastRemove 메서드는 아래와 같다.
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
여기서 System.arraycopy라는 메서드를 사용하는데 나도 처음 봤다.
찾아보니 아래와 같이 네이티브로 구성된 메서드여서 매우 빠르고 내부적으로 최적화가 되어 있다고 한다.
@IntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
100만 개 데이터 기준으로 아래처럼 시간 차이가 발생한다.
3. contains, indexOf
contains는 indexOf() 메서드를 빌려서 사용하고 있다. indexOf의 값이 0보다 크거나 같으면 true, 아니면 false를 리턴한다.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
indexOf()는 아래와 같이 구현이 되어 있다.
public int indexOf(Object o) {
int index = root.indexOfRange(o, offset, offset + size);
checkForComodification();
return index >= 0 ? index - offset : -1;
}
root.indexOfRange를 통해 객체 o에 대한 인덱스를 반환받는다.(없으면 -1을 반환한다)
이후 checkForComodification()을 통해 외부에서 동시에 리스트를 수정했을 경우 예외를 던진다.
(별의별 안전장치가 다 구현되어 있다...)
private void checkForComodification() {
if (root.modCount != modCount)
throw new ConcurrentModificationException();
}
4. isEmpty()
size의 값이 0인지 아닌지로 판단하고 있다.
(이건 그래도 사람처럼 구현했네)
public boolean isEmpty() {
return size == 0;
}
5. size()
여기도 동일하게 checkForComodification() 메서드를 통해 리스트 동시 수정을 방지해서 예외를 던지고 있다.
(이러한 안전장치를 도입했던 이유가 궁금하긴 하다. 싱크로나이즈를 걸기에는 부담이 있었던 걸까?)
public int size() {
checkForComodification();
return size;
}
여기까지 구현했던 메서드를 비교하면서 살펴봤다.
ArrayList 구현체를 보면서 가장 놀라웠던 점은 아래 2가지였다.
1. remove를 진행할 때 System.arraycopy를 통해 네이티브 메서드를 사용했다는 것.
2. 동기화를 쓰지 않는 대신 checkForComodification() 메서드를 만들었다는 것.
생각보다 더 다양한 기능을 활용해서 ArrayList를 구현했다.
내가 만들었던 ArrayList는 기본적인 동작은 하지만 동시성에 대한 예외가 처리되어있지 않고 remove에서 시간이 많이 느리다는 특징이 있었다.
다음에는 LinkedList를 개념만 가지고 직접 구현해 보는 시간을 가져보려고 한다.