[JAVA] ArrayList

뚜밍·2023년 3월 24일

JAVA

목록 보기

1/4

스터디 시작! 😆

구글 개발자 책 이후 스터디에서 선정된 책은 [Think Data Structures 자바로 배우는 핵심 자료구조와 알고리즘] 이고였따.

막연히 "arrayList는 배열(array)를 기반으로 두고있다"라는 사실만 알고있었다. 이번 챕터에서는 java collection 중 익숙하다고 할 수 있는 ArrayList에 대하여 공부한 내용을 정리해보려고 한다.

이 책의 예제코드에는 (git 링크참고) TODO로 코드안이 비어있는 곳이 있다. 최대한 책을 찾아보지않고 구현해보았다. 책을 보며 정리하면서 놓친부분도 함께 정리했다.

ArrayList 메서드 분류

get 메서드

	@Override
	public T get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		return array[index];
	}

-> get 메서드에 있는 모든 것은 상수 시간

set 메서드

@Override
	public T set(int index, T element) {
		// TODO: FILL THIS IN!

		//1. i 잇나?
		//2. e set 
		if(array.length -1 > index){
			array[index] = element;
		}
		return null;
	}

set 메서드의 TODO 구현

array의 범위를 검사하기 위해 if문에서 validation을 추가해주었다.
아래 코드는 책에 나온 코드

@Override
	public T set(int index, T element) {
		T old = get(index);
		array[index] = element;
		return old;
	}

... get메서드에서 배열의 범위를 검사해주는데 생각조차 못하고 if문을 추가해서 검사한 사실을 깨달음ㅋ..

~~ㅋ 우울하네요..~~

set 메서드는 명시적으로 배열의 범위를 검사하지 않는다. 왜냐! 인덱스가 유효하지않으면 예외를 던지는 get 메서드를 호출하기 때문.

-> get메서드 호출을 포함한 set메서드의 모든 것은 상수 시간

indexOf 메서드

	@Override
	public int indexOf(Object target) {
		// TODO: FILL THIS IN!

		if(target== null){
			return -1;
		}

		for (int i=0; i < array.length; i++) {
			// 1. array[i] 타겟이랑 동일한 값인가?
			// 2. 같다? i 리턴
			// 3. 다르다 넘어간다
			// 4. 없을때? -1이 넘어간다.
			// 5. null 이면? 

			// object == 주소값 비교, hash code 값 비교
			if(array[i].equals(target)){
				return i;
			}

		}

		return -1;
	}


	/** Checks whether an element of the array is the target.
	 *
	 * Handles the special case that the target is null.
	 *
	 * @param target
	 * @param object
	 */
	private boolean equals(Object target, Object element) {
		if (target == null) {
			return element == null;
		} else {
			return target.equals(element);
		}
	}

index of 메서드는 target.equals 메서드를 호출함. 이 메서드 실행 시간은 target 또는 element의 크기에 의존한다. 하지만 배열의 크기에는 의존하지 않으므로 indexOf 메서드를 분석하기위해 equals 메서드를 상수시간으로 생각한다.

indexOf 메서드의 반복문 안에 있는 모든 것은 상수시간이므로 반복문이 몇번 실행됐는가를 생각해야함

운이 좋으면 1개의 요소만 테스트한 후 반환하고, 운이 좋지않으면 모든 요소를 테스트해야함. 평균적으로 요소 개수의 절반을 테스트하기를 기대한다.
-> 따라서 indexOf 메서드는 선형

remove 메서드

@Override
	public T remove(int index) {
		// TODO: FILL THIS IN!

		// 1. 해당 index 값을 지운다.
		//2. index가 없으면 return 한다.
		//3. 붙인다. 양옆을 
		
		if(array.length -1 > index){
			array[idenx] = null;
			for(int i = index; i < array.length - 1; i++ ){
				//swap한다
				object temp = array[i];
				array[i] = array[i+1];
				array[i+1] =temp;
			}
		}
		return null;
	}

예제코드 remove 메서드의 TODO를 채워넣어 보았다.

생각의 흐름으로 순서를 주석으로 정리해보았는데 다 구현하고난걸 보니 size 조절을 안해준것도 보인다. ㅋ.ㅋ.ㅋ..😅🤡

아래는 책에나온 콛으.

@Override
public E remove(int index) {
    E element = get(index);
    for(int i = index; i<size-1; i++){
        array[i] = array[i+1];
    }
    size--;
    return element;

상수시간인 get메서드를 상요하고 index부터 배열에 반복문을 실행한다. 첫 번째 요소를 제거하면 나머지 모든 요소에 접근하여 선형이 된다. 따라서 remove는 선형으로 간주

(책에는 요소가 배열의 끝에 있거나 끝에서 상수 거리에 있음을 아는 특수한 경우는 제외라고 적혀있음)

add 메서드

arrayList의 특징을 볼 수 있엇던 메서드였다.

@Override
	public void add(int index, T element) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException();
		}
		// add the element to get the resizing
		add(element);

		// shift the elements
		for (int i=size-1; i>index; i--) {
			array[i] = array[i-1];
		}
		// put the new one in the right place
		array[index] = element;
	}

add 메서드를 호출하면 단일인자 add 메서드를 호출 한 후, 다른 요소를 오른쪽으로 이동 시키고 새로운 요소를 넣게 된다.

따라서 add(int, E) 메서드를 분류하려면 먼저 add(E) 메서드를 분류해야한다.

@Override
public boolean add(E e) {
    if(size >= array.length) {
        E[] bigger = (E[]) new Object[array.length * 2];
        System.arraycopy(array, 0, bigger, 0, array.length);
        array = bigger;
    }
    array[size] = e;
    size++;
    return true;
}