[JAVA] ArrayList의 사용법과 주요 메서드의 시간복잡도

• ArrayList란?
• ArrayList의 특징과 기본사용법
• ArrayList의 생성자
• ArrayList 데이터 추가/삭제
• ArrayList 데이터 조회/변경
• toArray() : List -> Array
• ArrayList 메서드의 시간복잡도

 

---

 

ArrayList란?

: List 인터페이스를 구현한 클래스로 데이터 저장공간이 가변적인 자료구조 = 동적 배열

 

출처: https://blog.kakaocdn.net/dn/qp1KU/btqEiLKhVVi/h1IfW46J1Ks7nu1DBvgUmk/img.png

---

ArrayList의 특징과 기본사용법

• 확장 가능한 배열이므로 순서가 매우 중요하다 (index 존재)
• 배열처럼 쓰이지만, 객체생성 시 대괄호를 사용하지 않고 주로 제네릭을 사용한다
• 데이터 공간의 초기 크기(capacity)는 10이며, 10개 이상의 값이 올 경우 데이터 공간은 자동 추가 생성된다

ArrayList objList = new ArrayList(); // 제네릭 미사용 시, Object 타입
ArrayList<String> strList = new ArrayList<String>(); // 주로 제네릭 사용
ArrayList<String> strList2 = new ArrayList<>(); // new에서 타입 생략가능
ArrayList<Integer> intList = new ArrayList<Integer>(20); // 저장되는 데이터 크기가 예측가능하면 초기 capacity를 지정한다
ArrayList<Integer> intList2 = new ArrayList<Integer>(intList); // 깊은 복사를 해야할 경우에 컬렉션을 매개변수로 갖는 생성자를 사용한다

---

ArrayList의 생성자

1. ArrayList() : 초기 저장공간이 10개인 기본 ArrayList
2. ArrayList(int initialCapacity) : 매개변수로 넘어온 개수 만큼의 저장공간을 갖는 ArrayList
3. ArrayList(Collection<T> c) : 매개변수로 넘어온 컬렉션 객체가 저장되는 ArrayList

---

ArrayList의 메서드

1) 데이터 추가

1. add(int index, E e) : 매개변수로 넘어온 하나의 데이터(E=요소)를 index 위치에 추가한다. int index 생략 시, 맨끝에 추가
2. addAll(Collection<T> c) : 매개변수로 넘어온 컬렉션 데이터를 담는다

ArrayList<String> list = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();

list.add("A");
list.add("B");
list.add(1,"C"); // 'index 1'에 위치한 B가 뒤로 한 칸 밀리고, 그 빈자리에 C가 들어온다.
for(String value : list){
	System.out.print(value); // ACB
} 

list2.add("D");
list2.addAll(list); // 컬렉션 데이터인 list의 모든 데이터를 list2에 담는다.
for(String value2 : list2){
	System.out.print(value2) // DACB
}

: 데이터 추가 시, 해당 인덱스를 기준으로 뒤쪽에 위치한 모든 데이터를 맨뒤부터 한칸씩 뒤로 이동하고, 빈 공간에 데이터를 넣는다.

2) 데이터 삭제하기

1. clear() : 모든 데이터 삭제
2. remove(int index) : index 위치의 데이터를 지우고 삭제한 데이터를 리턴한다
3. remove(Object o) : 매개변수로 넘어온 객체와 동일한 첫 번째 데이터를 삭제한다
4. removeAll(Collection<T> c) : 매개변수로 넘어온 객체와 동일한 모든 데이터를 삭제한다

System.out.println(list); // [A,B,C]
System.out.println(list2); // [A,B,C,D]

list.clear(); // 
list.remove(0); // [B,C]
list.remove("C"); // [A,B]
list2.removeAll(list); // [D]

: 데이터 삭제 시, 삭제할 데이터 뒤쪽의 데이터들을 한칸씩 앞으로 복사해 삭제할 데이터를 덮어쓰고, 맨마지막 데이터를 null로 바꾼다. 

 

모든 element를 순차적으로 삭제 시, 주의할 점

=>  끝 index부터 첫 index까지 증감하며 삭제해야 한다.
       앞에서부터 index 대로 삭제 시, 데이터의 이동이 불가피하고 삭제되지 않는 데이터가 생긴다.

ArrayList 중간에 데이터 추가/삭제 시,

해당 인덱스 뒤의 모든 element가 앞뒤로 이동해야 하므로,  많은 시간이 소요된다 

중간에 데이터를 추가/삭제하기에 ArrayList는 비효율적

---

3) 데이터 조회하기

1. size() : 실제로 들어가 있는 데이터의 개수를 리턴 
   • length : 배열에서 저장공간 개수
2. get(int index) : index 위치의 데이터를 꺼낸다
   • 전체 데이터를 꺼내려면 for-each문 or Iterator 사용
     (Collection 인터페이스의 구현체는 forEach문 / Iterator() 모두 사용가능)
3. indexOf(Object o) : 매개변수로 넘어온 객체와 동일한 데이터의 위치를 리턴
4. lastIndexOf(Object o) : 매개변수로 넘어온 객체와 동일한 마지막 데이터의 위치를 리턴

Q. 데이터의 위치를 찾는 메서드가 indexOf() 와 lastIndexOf()로 구분되는 이유는?
: ArrayList는 Set과 다르게 중복을 허용하기 때문이다.
배열(Array)도 당연히 value의 중복을 허용한다.

System.out.println(list); // [A,B,B,C]

list.size(); // 4
list.get(0); // A
list.indexOf("B"); // 1
list.lastIndexOf("B"); // 2

 

4) 데이터 변경하기

set(int index, E e) : index 위치의 데이터를 E로 변경하고, index에 위치했던 데이터를 리턴

System.out.println(list); // [A,B,B,C]

list.set(2,"D"); // B 
System.out.println(list); // [A,B,D,C]

---

Q. List의 데이터를 Array 로 나타내야 할 경우, 어떤 메서드를 사용해야 하는가?

: toArray

1. toArray() : 매개변수가 없는 경우는 ArrayList 객체의 데이터를 Object[] 타입의 배열로만 만든다
2. toArray(T[] a) : ArrayList 객체에 있는 값들을 매개변수로 넘어온 T 타입의 배열로 만든다
   • 제네릭을 사용한 ArrayList는 1번 사용불가, 2번 사용 !

System.out.println(list); // [A,B,C]

String[] str = list.toArray(new String[0]); 
// 길이가 0인 배열을 넘겨주면, ArrayList 길이만큼 배열을 자동으로 생성하고 데이터를 복사

for(String e : str){
	System.out.print(e): // ABC
}

---

ArrayList 메서드의 시간복잡도

 

 

add Method 

: add 메서드는 데이터 삽입 위치(마지막 or 중간)에 따라 오버로딩된 메서드를 가지고 서로 다른 시간 복잡도를 가진다. 또, 마지막에 데이터를 삽입하는 아래 1번 메서드에서도 ArrayList의 Object 배열의 사이즈를 늘려야하는 임계점에 도달했는지 여부에 따라 다른 시간복잡도를 가진다.

 

• add(Element e) : 맨 마지막에 element 추가
  
  1. 추가하기만 하면 되는 경우 :  O(1) 시간복잡도를 가진다.
  2. 배열의 크기를 늘려야하는 경우 :  grow 메서드를 호출해서 배열의 크기를 늘리고 기존 배열의 element들을 복사해와야 하기 때문에 O(N) 시간복잡도를 가진다. (copy한다는 것은 시간복잡도 O(N)을 쓴다는 것)
     
     그럼 결국, add(e) 메서드의 시간복잡도는 무엇인가??
     => add(Element e) 메서드는 두 시간복잡도를 가지지만,
     배열 마지막 인덱스에 element를 추가하는 작업이 훨씬 더 많으므로, 평균내서 O(1)의 시간복잡도를 가진다.
     
     
• add(int index, Element e) : 중간에 element 추가
  • 해당 index의 뒤쪽에 존재하는 모든 element들을 우측으로 한칸씩 옮겨 빈 공간을 만들어야 하므로, 시간복잡도는 배열의 원소의 갯수 N에 비례한다. 시간복잡도는 O(N)이다.

 

remove Method 

• remove(int index)
  • 해당 index에 위치한 데이터를 삭제하고, index 뒤쪽의 element들을 앞으로 한칸씩 이동하므로 시간복잡도는 배열의 원소의 갯수 N에 비례한다. 시간복잡도는O(n)이다.
• remove(Object o)
  • 앞에서부터 순차적으로 해당 객체와 동일한 객체를 찾고 remove(int index)와 동일한 과정을 수행한다. 시간복잡도는 O(n)이다.

 

get, set Method

• get(int index) : O(1)
• set(int index, Object o) : O(1)

 

indexOf, lastIndexOf, contains Method

: 매개변수로 Object를 받아 obj의 위치와 포함 여부를 리턴하므로, 배열 전체를 순회하는 작업이 필요하다.

O(N)의 시간복잡도를 가진다.

 

size, isEmpty, iterator, listIterator Method

: 모두 O(1)

 

 

 

⇒ ArrayList의 remove() 메서드는 비용이 많이드는 비싼 작업이다..

    또, ArrayList는 중간이나 앞부분에서 데이터를 추가, 삭제하는 경우는 늘 O(N)이 든다는 것을 기억하자 !

---

정리

ArrayList를 '줄서기' 개념으로 생각하면 이해가 쉽다.

내 앞사람이 줄서기를 포기하면, 나를 포함한 내 뒷사람들은 모두 앞으로 한칸씩 이동한다.
반대로 내가 앞자리를 새치기 당하면, 내 뒤에 모든 사람들이 뒤로 한칸씩 밀리게 된다.

이렇게, ArrayList 중간에 데이터를 넣거나 지울 때, 데이터의 이동이 필요하므로, 많은 시간이 소요된다. O(N)
하지만, 데이터를 검색하는 속도가 빠르다. O(1)