ArrayList의 코드를보며 ArrayList에 대해 알아보자
| 용도 | 메소드 | 쿼리당 시간복잡도 | 리턴값 |
| 사이즈 확인 | .size() | O(1) | int |
| 비어있는지 확인 | .isEmpty() | O(1) | boolean |
| 요소의 인덱스 확인 | .indexOf(Object o) | O(n) | int |
| 요소 포함 확인 | .contains | O(n) | boolean |
| 요소의 마지막 인덱스 확인 | .lastIndexOf(Ojbect o) | O(n) | int |
| 복제 | .clone() | O(n) | Object |
| 인덱스값 참조 | .get(int) | O(1) | generic |
| 인덱스 값 변경 | .set(int, generic) | O(1) | generic |
| 값 추가 | .add(generic) | O(1) | boolean |
| 특정 인덱스 에 값 추가 | .add(int, generic) | O(n) | void |
| 원소 삭제 | .remove(int), .remove(Object) | O(1), O(n) | generic, boolean |
| 전체 삭제 | .clear() | O(n) | void |
| colleciton객체 추가 | .addAll(Collection<? extends generic>) | O(n) | boolean |
목차
1. 생성자
2. 사이즈
- 별도의 size변수를 지정해 확인 O(1)
3. 비어있는지확인
- 별도의 size변수를 지정해 확인 O(1)
4. 요소 인덱스 확인
- ArrayList를 반복하며 요소체크 O(n)
5. 요소 포함 확인
- 요소인덱스 호출을 하며 포함 확인 O(n)
6. 요소 마지막 인덱스 확인
- 요소인덱스확인의 뒤에서부터 탐색버전 O()n
7. 복제
- 얕은복사가아닌 깊은복사임 O(n)
8. get
- 내부적으로 배열을 사용하기때문에 값 참조가 자유로움 O(1)
9. set
- get과 마찬가지 이유로 O(1)
10. add
- O(1)메소드, O(n)메소드가 있음 최대크기재할당이 일어나면 두 메소드 모두 O(n)의 시간복잡도를 가짐
11. remove
- 삭제후 삭제된 위치뒤의 요소들을 앞으로 땡겨야함 O(n)
12. clear
- ArrayList의 요소들을 모두 null로 바꿈 O(n)
13. addAll
- 배열을 모두 집어넣음 O(n)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{정의하는부분
제네릭 타입 덕분에 ArrayList에 다양한것(우리가만든 객체등등,,)을 넣을수있다.
private static final int DEFAULT_CAPACITY = 10;기본용량은 10으로 설정된다..(size와는 다르다.)
size의 경우 배열안에있는 요소들의 갯수를 반환하지만, Capcity는 요소들이 추가될때 할당할수있는 크기이다.
private static final Object[] EMPTY_ELEMENTDATA = {};이후에 비어있는 ArrayList를 만들때 사용하기위해 비어있는 Object를 만든다.
transient Object[] elementData;transient형으로 선언되어있는데, 찾아보니 transient는 직렬화하는과정에서 제외하고 싶은 경우에 적용한다고한다.
내부적으로 배열을 사용해서 자료를 저장한다. 즉, 요소들을 index값을 이용해 참조할수있다.
생성자
생성자 부분은 빠르게 넘어가겠다.
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
ArrayList생성자이다.
메소드 호출시 initialCapactiy가 음수라면 (이런 예외를 만들어놓은걸보면 배열의 크기를 음수로 설정하는 사람도 있나보다.. )
IllegalArgumentException을 던진다.(부적합한 인수를 전달함)
아니라면, this.elementData에 Object[initialCapacity]를 넣는다.
(new를 사용해서 새로운 인스턴스를 만들어 넣는걸 볼수있음)
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}ArrayList의 기본 생성자이다.
배열을 비어있는배열로 초기화한다.
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}ArrayList에 Collection 배열을 넣으면서 선언할때 사용하는 생성자이다.
사이즈
public int size() {
return size;
}사이즈를 리턴한다.
시간복잡도가 O(1)인걸 볼수있다.
(사이즈 매개변수를 따로 저장해서 add,remove메소드가 호출될때마다 size를 변경하는방식으로 O(1)시간복잡도를 만든거같다.)
비어있는지 확인
public boolean isEmpty() {
return size == 0;
}비어있다면 true 아니라면 false를 반환한다.
마찬가지로 시간복잡도가 O(1)인걸 알수있다.
요소 인덱스 확인
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}시간복잡도가 O(n) 인걸 볼수있다.
null타입의 경우 equals메소드를 사용하지못해 조건문을 사용해 따로 봐준다.
요소 포함 확인
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
오브젝트가 배열에 포함되어있는지 확인한다. 있다면 true아니라면 false를 반환하며, 내부적으로 indexOf를 사용하고있다.
시간복잡도 또한 O(n)이다.
요소 마지막 인덱스 확인
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
indeoxOf와 마찬가지로 시간복잡도는 O(n)이다 찾고자하는 인덱스의 마지막위치를 반환하기위해 뒤에서부터 탐색하는걸 볼수있다.
복제
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}ArrayList<?> v 에 super.clone()을 통해, 부모를 복사후 형변환해서 자신과 같은 새로운 객체를 만든다.
object.clone의 규약은 다음과 같다.
1. object.clone()을 통해 복사한 객체의 레퍼런스는 object와 다르다.
- (다른주솟값을 참조하는 새로운 인스턴스가 생성된다는뜻임)
2. object.clone()의 클래스는 object이다.
3. ojbect.clone().equals(object)는 true다.
쉽게말해, 깊은복사를 한다는 말이다.
위 메소드에서 시간복잡도에 직접적인 영향을 끼치는 메소드는
v.elementData = Arrays.copyOf(elementData, size);일것이다.
copyOf를 열어보자.
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}(동일한 이름의 메소드가 많지만 대표적으로 int[]를 copy하는 copyOf로 알아보자. 구현은 대부분 비슷하다)
CopyOf는 내부적으로 System.arraycopy를 호출한다.
system.arrayCopy메소드의 시간복잡도는 O(n)이므로 clone()의 시간복잡도 또한 O(n)이다.
get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}get메소드는 이렇게 생겼다.
내부적으로 rangeCheck를 통해, index가 배열의 size보다 큰지 확인한다. 이때, index가 배열의 크기보다 크다면 예외를 던진다.
선형자료구조 ArrayList의 경우 배열을 사용하므로 시간복잡도는 O(1)이다
set
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}get과 마찬가지로 rangeCheck를 통해 index가 size보다 작은지 확인한다.
배열을 사용하므로 값의 변경역시 O(1)이다.
바뀌기전 값을 return하는게 보인다.
add
개인적으로 가장 중요한 메소드라고 생각한다. 배열의 할당량 늘리는 원리를 알고있어야지 더 효율적으로 사용할수있다.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}add는 두개의 오버로딩 메소드가있다.
우선, 동적배열인 ArrayList에서 자신의 용량을 늘리는 원리를 알아보자.
add메소드에서 호출하는 ensureCapacityInternal는 내부적으로 ensureExplicitCapacity를 호출한다.
ensureExplicitCapacity는 grow를 호출해 사이즈를 늘린다.
grow 메소드는 다음과 같다.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}내부적으로 배열의 크기를 재할당할 필요가있을때, copyOf메소드를 사용한다. 즉, O(n)시간이 걸린다
배열의 크기는 기존 배열크기의 절반만큼의 크기로 재할당한다. (이는 프로그램 수행시간과 메모리 효율의 절충안으로 보인다.)
이제 add메소드를 알아보자.
첫번째 add메소드는 요소를 배열의 맨 뒤에 추가한다. 따라서, 시간복잡도는 O(1)이다.
두번째 add메소드는 요소를 index위치에 삽입한다. 이 과정에서 index이전위치부터 끝 위치까지 복사가 일어난다. 따라서, 시간복잡도는 O(n)이다.
remove
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
(첫번째는 index에 의한 remove 두번째는 object에 의한 remove)
마찬가지로 요소를 삭제한후 배열 복사가 일어난다. 따라서, 시간복잡도는 O(n)이다.
- Object에 의한 remove의 경우 object를 찾는시간이 있어서 index에 의한 remove보다 시간이 평균적으로 더 걸린다.
배열의 크기가 줄어듦으로 마지막값을 null처리해 가비지 콜렉터가 삭제할수있도록한다.
(fastRemove메소드의 경우 E remove의 동작과 비슷하기때문에 그냥 index에 해당하는 object를 지우는 메소드 정도로 생각하고 넘어가면된다.)
주의할점이, remove연산이 일어났다고해서, Capacity가 항상 줄어드는것은 아니다. (Size는 줄어든다)
Capacity와 Size는 다른개념이라는것을 알아두자.
clear
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
clear 메소드다. (생각했던 동작과 달라서 놀랐다)
size의 크기만큼 반복하며 요소들을 null로 변경한다.(가비지콜렉터가 삭제할수있도록)
시간복잡도는 O(n)이다.
인스턴스에대한 레퍼런스를 없애는방식으로 O(1)의 시간복잡도를 갖고있을줄알았는데 O(n)이다... 문제풀때 주의하도록 해야겠다
addAll
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
} public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}addAll메소드는 배열의 모든 요소들을 집어넣는다.
와일드카드를 사용해서 <? extends E>을해서 E(기존의 배열)의 저수준 클래스들만 넣을수있는것이 보인다.
복사를 통해 요소를 집어넣음으로 시간복잡도는 둘다 O(n)이다.
이상으로 많이쓰이는 ArrayList 메소드들에대해 알아봤다.
'Java > Java' 카테고리의 다른 글
| [Java] Future.cancel() vs CompletableFuture.cancel() (0) | 2023.02.15 |
|---|---|
| [Java] 스레드와 Synchronized (0) | 2021.10.25 |
| [Java] Java Heap Stack Static (0) | 2021.10.23 |
| [Java] compareTo (0) | 2021.05.05 |
| [Java] Wrapper Class (0) | 2021.05.02 |
