[F-Lab 모각코 챌린지 15일차] ArrayList 주요 메소드의 시간복잡도

TIL

• ArrayList 주요 메소드의 시간복잡도
  
  • 요소 추가
  • 요소 삭제
  • 요소 가져오기
  • 요소 위치 검색

 

---

 

ArrayList 주요 메소드의 시간복잡도

 

 

 

요소 추가

public boolean add(E e) {}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Website");

    // 같은 요소 추가하기
    boolean isSuccessFullyAdded = list.add("GOAL");

    System.out.println(list); // [JAVA, GOAL, Website, GOAL]
}

add(E e) 메소드는 데이터 추가 위치(마지막/중간)에 따라 서로 다른 시간복잡도를 가진다. add(E e) 메소드는 맨 마지막 위치에 요소를 추가한다. 마지막 위치에 요소를 추가만 하면 되는 경우엔 O(1) 시간복잡도를 가진다. 그러나 배열의 크기를 늘려야 하는 임계점에 도달한 경우, grow() 메소드를 호출하여 배열의 크기를 늘리고 기존 배열의 요소들을 복사해와야 하기 때문에 O(N) 시간복잡도를 갖는다.

이와 같이 add(E e) 메소드는 2가지의 시간복잡도를 갖지만 일반적으로 배열의 마지막 위치에 요소를 추가하는 작업이 훨씬 많으므로 O(1)의 시간복잡도를 갖는다고 얘기한다.

 

 

public void add(int index, E element) {}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Website");

    // 1번째 index에 요소 추가
    list.add(1, "Learning");

    System.out.println(list); // [JAVA, Learning, GOAL, Website]
}

add(int index, E e) 메소드는 배열 중간에 요소를 추가하는 기능이다. 요소를 추가하려는 위치의 뒤쪽에 존재하는 모든 요소들은 오른쪽으로 한칸씩 옮겨 빈 공간을 만들어야 하므로 시간복잡도는 배열 요소의 갯수 N개에 비례한다. 따라서 시간복잡도는 O(N)이다.

 

 

 

요소 삭제

public E remove(int index) {}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Learning");
    list.add("GOAL");

    list.remove(3);
    list.remove(0);

    System.out.println(list); // [GOAL, Learning]
}

해당 index에 위치한 데이터를 삭제하고 index 뒤쪽에 위치한 요소들을 앞으로 한칸씩 이동시켜야 하므로 시간복잡도는 배열 요소의 갯수인 N개에 비례한다. 따라서 시간복잡도는 O(N)이다.

 

 

public boolean remove(Object o) {}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Learning");
    list.add("GOAL");

    list.remove("GOAL");

    System.out.println(list); // [JAVA, Learning, GOAL]
}

remove(Object o) 메소드는 ArrayList에서 파라미터로 넘어온 객체와 동일한 첫 번째 요소를 제거하는데 사용된다. ArrayList에 중복 요소가 포함된 경우 요소의 첫번째 항목만 제거한다. remove(int index) 메소드와 과정을 수행하므로 시간복잡도는 O(N)이다.

 

 

 

요소 가져오기

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Learning");
    list.add("GOAL");

    System.out.println(list.get(2)); // Learning
}

ArrayList는 index 값을 이용하여 삽입 순서를 유지한다. 그러므로 특정 index를 이용해 배열의 요소들에 무작위, 순차적으로 접근할 수 있다. 따라서 시간복잡도는 O(1)이다.

 

 

 

요소 위치 검색

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Learning");
    list.add("GOAL");

    System.out.println(list.indexOf("GOAL")); // 1
}

index(Object o) 메소드는 지정된 요소의 index를 가져오는데 사용된다. ArrayList에 중복 요소가 있는 경우 요소가 처음 나타나는 인덱스 값을 반환한다. 만약 ArrayList에 요소가 없으면 -1을 반환한다. 최악의 경우, 파라미터로 받은 해당 요소가 어디에 있는지 배열 전체를 순회해야하므로 시간복잡도 O(N)을 갖는다.

 

 

public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JAVA");
    list.add("GOAL");
    list.add("Learning");
    list.add("GOAL");

    System.out.println(list.lastIndexOf("GOAL")); // 3
}

lastIndexOf(Object o) 메소드도 지정된 요소의 index을 찾는데 사용되지만 지정된 요소의 마지막 index를 반환한다. 배열 전체를 순회해야하므로 시간복잡도 O(N)을 갖는다.

 

 

 

정리

ArrayList를 맛집 '줄서기' 개념으로 생각하자.

내 앞에 서있는 사람이 줄서기를 포기하면, 나와 내 뒤에 있는 사람들 모두 앞으로 한칸씩 이동한다.

반대로 내가 새치기를 당하면, 나와 내 뒤에 있는 사람들 모두 뒤로 한칸씩 이동한다.

 

이와 같이 ArrayList 중간에 데이터를 넣거나 지울 때, 데이터들의 이동이 필요하므로 많은 시간이 소요된다.

그러나 맛집 줄서기에 대기번호가 있는 것처럼 각 요소에 index 값이 있으므로 데이터를 검색하는 속도는 빠르다.

 

 

 

📚 참고
ArrayList in java
ArrayList의 사용법과 주요 메서드의 시간복잡도
Java LinkedList class