[JAVA] ArrayList 구현

개인 정리 내용이니 틀린 부분이 있을 수도 있습니다. 피드백 해주시면 감사드리겠습니다.

학습 내용 

기능 구현을 하며 시간 복잡도를 구별 해보자.

 

1. 구현 상세 내용

• 추가
  • 요소 추가 
  • 인덱스 지정하여 요소 추가
• 수정
  • 인덱스 지정하여 요소 수정
• 조회
  • 해당 인덱스의 값 조회
  • 해당 인덱스의 값과 target 값을 비교하여 인덱스 값 반환
• 삭제
  • 인덱스를 설정하여 값 삭제
  • 요소 전체 삭제

---

필드

int size;
private E[] array;

public MyArrayList() {
    size = 0;
    array = (E[]) new Object[10];
}

ArrayList 와 비슷하게 기본 Size 를 10으로 설정 하였습니다.

---

추가

1. 요소 추가

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;
}

size 가 배열의 길이보다 크거나 같을 때 배열의 길이를 2배로 늘려 줘야 합니다.

 

배열을 복사하는 과정만 빼놓고 봤을 때는 시간 복잡도가 O(1)입니다.

하지만 배열이 복사되면서 시간 복잡도는 O(n)로 바뀝니다

 

 

1.2 해당 인덱스 자리에 요소 추가

public void add(int index, E element) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    add(element);
    for (int i = size - 1; i > index; i--) {
        array[i] = array[i -1];
    }
    array[index] = element;
}

인덱스를 지정하여 요소를 추가하는 기능입니다.

인덱스가 size 의 범위에 벗어나면 우리는 예외를 던져 줘야 합니다.

그리고 인덱스들을 한 칸씩 옮겨서 해당 인덱스에 요소를 저장합니다.

 

 

시간 복잡도는 O(n)입니다.

그러면 배열의 길이가 복사되는 순간의 시간 복잡도는 어떻게 될까요??

시간 복잡도는 O(n^2)으로 바뀌겠죠?

 

---

수정

1. 인덱스를 받고 해당 인덱스에 요소 추가

public E set(int index, E element) {
    array[index] = element;
    return get(index);
}

입력 받은 인덱스 값에 요소를 수정하는 기능입니다.

 

시간 복잡도는 O(1) 로 보입니다.

---

조회

1. 해당 인덱스의 값 반환

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

인덱스가 0보다 작거나 size 보다 크거나 같으면 예외를 던져줘야합니다.

 

시간 복잡도는 O(1) 로 보입니다.

 

 

1.2 해당 인덱스의 값과 타겟 값을 비교하여 인덱스 반환

private boolean equals(Object target, E e) {
    if (target == null) {
        return e == null;
    } else {
        return target.equals(e);
    }
}

public int indexOf(Object target) {
    for (int i = 0; i < size; i++) {
        if (equals(target, array[i])) {
            return i;
        }
    }
    return -1;
}

target 이 null 이면 요소 값도 null 로 지정해주며 null 이 아닐 경우 target 과 요소를 비교하여 해당 인덱스 값을 반환 해 줍니다.

 

시간 복잡도는 O(n) 으로 보입니다.

 

---

삭제

1. 인덱스를 받아 해당 인덱스의 값을 삭제

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

해당 인덱스의 값을 삭제하고 한 칸씩 쉬프트 합니다.

 

시간 복잡도는 O(n) 으로 보입니다.

 

 

1.2 요소 전체 삭제

public boolean remove(Object o) {
    return false;
}

public boolean removeAll(Collection<?> c) {
    boolean flag = false;
    for (Object obj : c) {
        flag |= remove(obj);
    }
    return flag;
}

제거가 완료 되면 true를 반환 해줍니다.

 

시간 복잡도는 O(n) 으로 보여집니다.

 

 

---