[JAVA] ArrayList가 뭔가요?

[ ArrayList ]

 

- 배열을 좀 더 편리하게 사용할 수 있도록 java에서 제공하는 class이다.

- 크기를 조정할 수 있는 배열이다.

- 배열 크기를 지정하지 않으면, 초기 배열의 크기는 10이다.

- 인덱스로 요소를 검색할 수 있다.

- 제네릭을 지원한다.

 

- 크기가 고정된 배열과 달리, ArrayList는 새 요소가 추가될 때 자동으로 크기를 늘린다.

   그럼 ArrayList는 어떻게 배열의 크기를 조정하는 것일까?

1. add()로 인해 사이즈가 꽉 찼을 시 현재의 1.5배를 증가시켜 새로운 배열을 생성한다.
2. 1.5배 증가시킨 새로운 배열에 현재의 배열을 copy한다.

 

int newCapacity = oldCapacity + (oldCapacity >> 1); 

is equivalent of multiplying the old capacity by 1.5. (1 bit shift to the right)

-> 현재 크기의 절반만큼의 크기가 추가된 새로운 배열을 만든다는 의미.

 

---

 

 

• ArrayList는 AbstractList class를 extends한다.
• List, RandomAccess, Cloneable, Serializable을 implements 한다.

---

 

📍List<E> : 목록형 데이터를 처리하는 것과 관련된 메소드 지정

 

📍RandomAccess : index를 통해 바로 접근할 수 있는 자료구조라는 의미

 

📍 Cloneable : Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미

 

 

📍 Serializable : 객체를 직렬화 하여 전송 가능한 형태로 만드는 것을 의미

 

---

* Add

 

- add(Object)는 ArrayList의 제일 마지막에 값을 하나 추가하는 method이다.

  중간에 삽입하고 싶은 경우, add(index, Object)를 사용한다.

 

 

 

---

* Remove

 

1) value에 대한 삭제 

 

 

 

2) index 기준으로 삭제 

 

삭제를 할때 index + 1에서 부터의 값을 index부터 시작하게끔 복사.

그 때 O(n)의 시간복잡도를 가지며 마지막 값을 null로 변경한다.

삭제에 대해서는 항상 시간복잡도 O(n)을 가진다.