[JAVA] ArrayList 구성과 시간 복잡도

ArrayList란?

- ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다. 이렇게 말하면 Object배열과 다를게 없지만. ArrayList는 동적으로 배열의 공간을 조절하며 배열이 아닌 ArrayList를 쓰게되면 요소가 용량을 넘어서게 되면 용량을 자동으로 늘려 추가적으로 요소를 넣을 수 있게 해준다.

 

 

ArrayList Constructors

- ArrayList() 는 초기 용량을 10으로 설정하여 빈 ArrayList를 생성합니다.

- ArrayList(Collection<? extends E> c) 는 파라미터로 Collection 클래스를 받고 ArrayList로 반환한다.

- ArrayList(int initialCapacity) 는 파라미터로 용량을 받아 빈 ArrayList를 생성한다.

 

ArrayList Method

- ArrayList에 담긴 elemets(요소)의 개수를 반환한다. CAPACITY(용적)와는 다르다. 시간복잡도는 O(1)이다.

 

- 배열에 담긴 요소가 있다면 true를 없다면 false를 반환하는 메소드이다. 시간복잡도는 O(1)이다.

 

- 매개변수로는 포함됐는지 확인할 요소를 넣어주고 하나 이상의 지정된 요소가 포함된 경우에만 true를 반환함.

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

 

- 매개변수로 요소를 넣어주고 지정된 요소가 있다면 요소가 처음 발견되는 index를 반환한다. 만약 요소를 배열에서 찾기 못한다면 -1 을 반환한다. 이 메소드는 우선순위의 index를 반환하며 나중 순위부터 찾고 싶다면 lastIndexOf() 메소드를 사용하면 된다. 시간복잡도는 O(n)이다.

 

- clone() 은 배열 복사를 위한 메소드로 Arrays.copyOf를 이용한다. copyOf()는 내부에서 다시 System.arraycopy를 호출한다. 시간복잡도는 O(n)이다. clone()은 얕은 복사로 clone() 이용하여 만든 배열의 요소를 변경시 원본 배열에도 변화가 같이 일어난다.

 

- toArray()는 List를 일반배열로 반환하고 싶을때 사용한다. 이 배열은 목록에서 해당 배열에 대한 참고를 유지하지 않는다.  시간복잡도O(n) 이다.

 

- 매개변수로 index를 받아 배열에 지정된 위치에 있는 요소를 반환하는 메소드이다. 인덱스 범위가 벗어난 경우

IndexOutOfBoundsException가 발생한다. 시간복잡도는 O(1) 이다.

 

- 매개변수로 인덱스와 요소를 받은뒤 입력받은 위치에 요소를 지정된 요소로 바꾸며 바뀌기전 요소를 반환한다.   이 경우에도 인덱스가 범위를 벗어난 경우 IndexOutOfBoundsException 가 발생하며 시간복잡도는 O(1) 이다.

 

- 매개변수로 인덱스와 요소를 받아 지정된 요소를 삽입한다. 만약 지정된 위치에 요소가 이미 있는 경우에는 모든 요소    들을 오른쪽 인덱스(현재 인덱스+1)로 이동후 지정된 위치에 요소를 삽입한다. 시간복잡도는 O(n) 이다.

 

- remove() 메소드는 매개변수로 인덱스 or 요소를 받을 수 있다. 인덱스를 받게 되면 배열에 지정된 위치에 있는 요소를 제거하고 제거한 요소의 오른쪽 요소들을 왼쪽으로 하나씩(인덱스-1)이동한다.

매개변수로 요소를 받게되면 목록에 요소가 있는지 get()메소드를 이용해 요소를 얻어와 equals()로 지정 요소와 비교후에 먼저 발견되는 지정된 요소를 제거후 나머지 요소를 왼쪽으로 이동한다. 시간복잡도는 O(n) 이다. 발견되는 모든 요소를 제거 하려면 removeAll(Collection<?> c) 를 사용하면 된다.

 

ArrayList 예제

import java.util.ArrayList;


class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList(); // ArrayList 선언
        ArrayList<Integer> list1 = new ArrayList();
        list.add(1);     // ArrayList 값 추가
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(1, 2);  //1번인덱스에 2를 삽입

        list1.add(2);
        list1.add(3);
        list.remove(0);     // 인덱스 1의 값 제거
        list.removeAll(list1);     // list에서 list1의 담긴 값을 제거
        for (Integer i : list) {   //for문을 통한 전체출력
            System.out.println(i);
        }
    }
}

출력