'자료구조(Java)/구현' 카테고리의 글 목록

자료구조(Java)/구현

[자바/자료구조] ArrayList 구현해보기 2022.01.08

[자바/자료구조] ArrayList 구현해보기

2022. 1. 8. 16:29

ArrayList는 배열을 사용하는 스택, 큐와 더불어 가장 구현하기 쉬운 자료구조가 아닐까 생각헌다. 배열과 메모리에 대한 이해가 어느정도 되어 있다면 그리 어렵지 않을 것이라 생각하고, 추가적으로 인터페이스와 제네릭, 오버로딩에 대한 지식이 필요하다.

iterator는 구현하지 않았기 때문에 컬렉션에서 제공하는 ArrayList처럼 for each로 순회하거나 iterator()를 호출할 수 없다. 반복자까지 구현하면 포스팅이 너무 커져서 생략했다.

구현하면서 멤버 변수, 메서드의 이름, 파라미터 이름 등은 ArrayList API Documentation를 보고 작성했다. 또한 배열 인덱스 범위를 확인하는데 있어 ArrayList 클래스에서 사용하는 방법이 너무 마음에 들어 나도 적용해보았다. 내가 작성한 코드는 add, remove 등 배열에 접근해야 하는 메서드를 작성할 때 메서드 초기에 계속 범위 체크를 해주고 있었다. 그런데 ArrayList 클래스는 "rangeCheck.." 같은 범위 체크 메서드를 만들어놓고 단 한 줄로 호출하여 검사하니 코드가 눈에 띄게 줄어들었고 중복이 상당히 줄어들어 있었다.

ArrayList를 다루는 메서드들(add, remove, etc)에 대한 구현은 그다지 어렵지 않았다. 하지만 구현하고 난 뒤 ArrayList에서 범위 체크 메서드를 따라하니 거의 같은 코드가 되어 버린 것 같다.

목차 겸 바로가기

아래 "전체 코드 보기"를 누르면 전체 코드를 볼 수 있다.

public class ArrayList<E> {
	private int size;
	private final int DEFAULT_CAPACITY = 10;
	
	private final Object[] EMPTY_ELEMENT_DATA = {};
	private Object[] elementData;
	
	public ArrayList() {
		elementData = EMPTY_ELEMENT_DATA;
	}
	
	public ArrayList(int initialCapacity) {
		if(initialCapacity > 0)
			elementData = new Object[initialCapacity];
		else if(initialCapacity == 0)
			elementData = EMPTY_ELEMENT_DATA;
		else if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
	}
	
	private void rangeCheckForAdd(int index) {
		if(index > size || index < 0)
			throw new IndexOutOfBoundsException(
					"Index " + index + " out of bounds for length " + size);
	}
	
	private void rangeCheck(int index) {
		if(index >= size || index < 0)
			throw new IndexOutOfBoundsException(
					"Index " + index + " out of bounds for length " + size);
	}
	
	private void reallocate() {
		if(elementData == EMPTY_ELEMENT_DATA) {
			elementData = new Object[DEFAULT_CAPACITY];
			return;
		}
		
		int capacity = elementData.length + (elementData.length >> 1);
		reallocate(capacity);
	}
	
	private void reallocate(int capacity) {
		Object[] newArray = new Object[capacity];
		
		for(int i = 0; i < size; i++) {
			newArray[i] = elementData[i];
			elementData[i] = null;
		}
		
		elementData = newArray;
	}
	
	public void ensureCapacity(int capacity) {
		if(capacity > elementData.length
				&& capacity >= DEFAULT_CAPACITY)
			reallocate(capacity);
	}
	
	public void trimToSize() {
		if(size < elementData.length) {
			if(size == 0)
				elementData = EMPTY_ELEMENT_DATA;
			else
				reallocate(size);
		}
	}
	
	public boolean add(E value) {
		add(size, value);
		return true;
	}

	public void add(int index, E e) {
		rangeCheckForAdd(index);
		if(elementData.length == size)
			reallocate();
		
		if(index == size) { 
			elementData[size] = e;
		} else {
			for(int i = index; i < size; i++)
				elementData[i+1] = elementData[i];
			elementData[index] = e;
		}

		size++;
	}

	@SuppressWarnings("unchecked")
	public E remove(int index) {
		rangeCheck(index);
		
		E removeElement = (E)elementData[index];
		
		if(index != size-1)
			for(int i = index; i < size-1; i++)
				elementData[i] = elementData[i+1];
		
		elementData[--size] = null;
		return removeElement;
	}

	public boolean remove(Object o) {
		int idx = indexOf(o);
		
		if(idx != -1) {
			for(int k = idx; k < size-1; k++)
				elementData[k] = elementData[k+1];
			elementData[--size] = null;
			return true;
		}
		
		return false;
	}
	
	@SuppressWarnings("unchecked")
	public E get(int index) {
		rangeCheck(index);
		return (E)elementData[index];
	}

	@SuppressWarnings("unchecked")
	public E set(int index, E e) {
		rangeCheck(index);
		
		Object oldElement = elementData[index];
		elementData[index] = e;
		return (E)oldElement;
	}

	public boolean contains(Object o) {
		return indexOf(o) == -1 ? true : false;
	}

	public int indexOf(Object o) {
		for(int i = 0; i < size; i++)
			if(elementData[i].equals(o))
				return i;
		
		return -1;
	}
	
	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		for(int i = 0; i < size; i++)
			elementData[i] = null;
		size = 0;
	}
}

Method Summary (public)

Method	Description
boolean add(E)	리스트 끝에 데이터 삽입
void add(int, E)	리스트 index 위치에 전달받은 요소 추가
E remove(int)	리스트 index 위치에 존재하는 요소 삭제하고 삭제된 요소 반환
boolean remove(Object)	리스트에서 특정 요소를 0부터 탐색하여 처음 발견하는 요소를 삭제
E get(int)	리스트 index 위치에 있는 요소를 반환
E set(int, E)	리스트 index 위치에 있는 요소를 수정하고 수정하기 전의 값을 반환
void ensureCapacity(int)	배열의 크기를 capacity로 축소 혹은 확장
void trimToSize()	배열의 크기를 현재 리스트가 가진 요소의 수에 맞게 축소
boolean contains(Object)	리스트에서 특정 요소에 대한 존재여부를 반환
int indexOf(Object);	리스트에서 특정 요소가 존재하는 index를 반환
int size();	리스트가 가진 요소 수를 반환
boolean isEmpty()	리스트가 비었는지에 대한 여부를 반환
void clear()	리스트를 초기화

Method Summary (private)

Method	Description
void rangeCheckForAdd(int)	데이터 삽입에 있어서의 index에 대한 유효 범위 확인
void rangeCheck(int)	데이터 삽입을 제외하고 index를 사용하는 상황에서의 유효 범위 확인
reallocate()	배열의 크기를 일정한 배율(1.5)로 확장
reallocate(int)	배열의 크기를 capacity에 따라 축소 혹은 확장

Variable

private int size;
private final int DEFAULT_CAPACITY = 10;
	
private final Object[] EMPTY_ELEMENT_DATA = {};
private Object[] elementData;

size : 현재 배열에 담긴 요소의 개수를 카운팅하는 변수.
DEFAULT_CAPACITY : 사용자가 배열 크기를 지정해주지 않았을 경우의 배열 크기 기본 값.
EMPTY_ELEMENT_DATA : 사용자가 배열 크기를 할당하지 않았을 경우 elementData가 가리키게 되는 빈 배열로, length가 0인 것과는 달리 할당되지 않은 배열이라는 의미.
elementData : 실제 데이터가 저장될 Object 타입 배열.(모든 클래스는 Object 클래스를 상속받기 때문에 타입이 Object인 배열은 어떠한 데이터도 담을 수 있음을 의미한다.)

생성자

public ArrayList() {
	elementData = EMPTY_ELEMENT_DATA;
}
	
public ArrayList(int initialCapacity) {
	if(initialCapacity > 0)
		elementData = new Object[initialCapacity];
	else if(initialCapacity == 0)
		elementData = EMPTY_ELEMENT_DATA;
	else if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}

파라미터가 없는 생성자와 정수형 변수 1개를 파라미터로 받는 생성자가 있다. 파라미터가 없는 생성자를 호출할 경우 elementData는 크기가 0인 EMPTY_ELEMENT_DATA를 가리키게 되는데, 이는 아직 메모리가 할당된 적이 없다는 것을 나타낸다.

파라미터가 1개인 생성자는 파라미터로 배열의 크기를 정할 수 있다. 받는 값이 정수이기 때문에 음수, 0, 정수 등이 입력될 수 있는데 배열을 할당받을 때 음수를 입력할 경우 예외를 발생시키고 0을 입력할 경우 의미없는 코드가 된다. 때문에 0을 입력할 경우 파라미터가 없는 생성자를 호출하였을 때와 같은 동작을 하게 하고 음수를 입력할 경우 인위적으로 예외를 발생시킨다. 파라미터로 1 이상의 값이 들어올 경우 비로서 정상적으로 배열을 할당한다.

데이터 삽입

public boolean add(E value) {
	add(size, value);
	return true;
}

public void add(int index, E e) {
	rangeCheckForAdd(index);
	if(elementData.length == size)
		reallocate();
	
	if(index == size) { 
		elementData[size] = e;
	} else {
		for(int i = index; i < size; i++)
			elementData[i+1] = elementData[i];
		elementData[index] = e;
	}
	size++;
}

데이터를 삽입할 때 호출되는 메서드들이다. 데이터만 삽입하는 메서드 add(E)와 특정 위치를 지정하여 데이터를 삽입하는 메서드 add(int, E)가 있다. 데이터만 삽입하는 경우 elementData의 마지막 위치인 index에 삽입되고, 인덱스를 지정하여 삽입하는 경우 해당 위치에 있는 데이터부터 마지막에 있는 데이터까지 모든 데이터를 한칸 씩 뒤로 미루고 해당 위치에 삽입한다.

단 데이터를 삽입하기 전에 index가 정상 범주에 속하는지 rangeCheckForAdd 메서드를 통해 체크한다. 문제가 없다면 배열의 현재 크기와 데이터 수를 비교하여 데이터가 다 찼을 경우 배열의 크기를 재할당한다.

데이터 삭제

@SuppressWarnings("unchecked")
public E remove(int index) {
	rangeCheck(index);
	
	E removeElement = (E)elementData[index];
	
	if(index != size-1)
		for(int i = index; i < size-1; i++)
			elementData[i] = elementData[i+1];
	
	elementData[--size] = null;
	return removeElement;
}

public boolean remove(Object o) {
	int idx = indexOf(o);
	
	if(idx != -1) {
		for(int k = idx; k < size-1; k++)
			elementData[k] = elementData[k+1];
		elementData[--size] = null;
		return true;
	}
	
	return false;
}

데이터를 삭제할 때 호출되는 메서드들이다. 특정 위치에 있는 데이터를 삭제하는 메서드 remove(int)와 특정 데이터를 삭제하는 메서드 remove(Object)가 있다. remove(int)는 먼저 인덱스가 정삼 범주 내인지 확인한 후 정상 범주라면 해당 위치에 있는 데이터를 반환하기 위해 미리 저장해둔다. 삭제 위치가 마지막이 아닐 경우 반복문을 구성하여 삭제할 위치의 데이터를 기준으로 뒤의 데이터를 하나씩 앞으로 당기는 작업을 수행한다. 마지막으로 배열의 마지막 요소에 null을 저장하고 이전에 저장해둔 값을 리턴한다.

remove(Object)는 내부의 indexOf(Object) 메서드를 호출하여 파라미터로 들어온 값이 elementData에 있는지 체크한다. 존재할 경우 0이상의 값을, 존재하지 않을 경우 -1을 리턴한다. -1이 아닐 경우 루프를 구성하여 삭제할 위치의 데이터를 기준으로 뒤의 데이터를 하나씩 앞으로 당기는 작업을 수행하고 elementData의 마지막에 null을 저장한 후 true를 반환한다. 반대로 -1일 경우 false를 반환한다.

데이터 검색

@SuppressWarnings("unchecked")
public E get(int index) {
	rangeCheck(index);
	return (E)elementData[index];
}
    
public boolean contains(Object o) {
	return indexOf(o) == -1 ? true : false;
}

public int indexOf(Object o) {
	for(int i = 0; i < size; i++)
		if(elementData[i].equals(o))
			return i;
	
	return -1;
}

주로 특정 데이터를 찾는데 쓰이는 메서드들이다. get(int)는 파라미터로 받은 index로 elementData를 참조하여 데이터를 반환한다.

contains(Object)는 파라미터로 받은 값이 elementData에 존재하는지 탐색하여 존재하는지 존재하지 않는지에 대한 판단만 하여 boolean 값으로 반환한다.

indexOf(Object)는 파라미터로 받은 값이 elementData에 존재하는지 탐색하여 그 위치를 정수형으로 반환한다. 존재한다면 0이상의 값을, 존재하지 않을 경우 -1을 반환한다.

데이터 수정

@SuppressWarnings("unchecked")
public E set(int index, E e) {
	rangeCheck(index);
	
	Object oldElement = elementData[index];
	elementData[index] = e;
	return (E)oldElement;
}

데이터를 수정하는 메서드로 특정 인덱스를 지정하여 해당 위치에 있는 값을 수정할 수 있다. 먼저 수정될 위치에 있는 값을 복사한 후 elementData에 있는 값을 수정한다. 마지막으로 처음에 복사해둔 값을 반환한다.

내부에서의 배열 관리

private void reallocate() {
	if(elementData == EMPTY_ELEMENT_DATA) {
		elementData = new Object[DEFAULT_CAPACITY];
		return;
	}
	
	int capacity = elementData.length + (elementData.length >> 1);
	reallocate(capacity);
}

private void reallocate(int capacity) {
	Object[] newArray = new Object[capacity];
	
	for(int i = 0; i < size; i++) {
		newArray[i] = elementData[i];
		elementData[i] = null;
	}
	
	elementData = newArray;
}

ArrayList의 핵심은 유동적인 배열의 크기라고 할 수 있다. 파라미터가 없는 메서드가 호출되면 elementData가 할당되어있는 상태인지, 아닌지를 판단한 후 할당되어 있지 않다면 기본값인 10으로 배열을 할당받는다. 이에 해당하지 않는 경우는 현재 배열이 "element.length == size"인 경우 뿐이다. 따라서 배열의 크기를 증가시켜줘야 하는데 이때 새 배열의 크기를 현재 배열 크기에서 1.5배 곱한 크기로 결정하였다. 이 메서드에서는 오로지 생성할 배열의 크기만 결정하고 그 크기를 아래 메서드로 넘겨 실제로 배열 크기를 증설한다.

파라미터가 있는 메서드의 경우 파라미터에 들어온 값으로 배열 크기를 증설한다. 파라미터로 들어온 값으로 배열을 생성하고 기존 배열에 있는 값을 복사한다. 마지막으로 elementData가 가리키는 주소를 새로 만든 배열의 주소로 변경해준다.

외부에서의 배열 관리

public void ensureCapacity(int capacity) {
	if(capacity > elementData.length
			&& capacity >= DEFAULT_CAPACITY)
		reallocate(capacity);
}

public void trimToSize() {
	if(size < elementData.length) {
		if(size == 0)
			elementData = EMPTY_ELEMENT_DATA;
		else
			reallocate(size);
	}
}

ensureCapacity 메서드는 파라미터로 들어온 값이 elementData의 크기보다 크면서 DEFAULT_CAPACITY보다 클 경우 파라미터 크기로 배열을 재할당한다. 해당 메서드는 접근제한자가 private인 reallocate와는 달리 public이다. 즉 외부에서 원하는 타이밍에 호출할 수 있는 배열 재할당 메서드라는 뜻이다.

데이터가 계속 삽입되면 증설이 필요하지만 반대로 데이터를 계속 삭제하면 남는 공간이 점점 늘어나게 되는데 이는 메모리 공간 낭비로 이어지게 된다. reallocate가 내부에서 증설을 담당했다면 trimToSize 메서드는 elementData의 크기를 현재 데이터 개수인 size로 알맞게 재할당하는 메서드라고 볼 수 있다. 이 메서드 또한 접근 제한자가 public인 만큼 외부에서 호출가능하다.

PREV 1 NEXT

오래된 연습장