Java ArrayList 학습 노트
21057 단어 Java
최근 에 저 는 자바 기 초 를 공부 하고 있 는데 자주 사용 하 는 Array List 가 중요 하 다 는 것 을 알 게 되 었 습 니 다.그래서 찾 아 볼 수 있 도록 필 기 를 했 습 니 다.필 기 는 많은 선배 들 의 글(링크 첨부)을 참고 하고 이 필 기 는 점차적으로 업 데 이 트 될 것 이다.본 고 는 자바 1.8.0 을 참고 하 였 다.45 버 전)
정의.
공식 문서 의 정의:
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
이것 은 List 인터페이스의 가 변 배열 의 실현 이다.선택 할 수 있 는 모든 list 작업 을 실 현 했 고 null 을 포함 한 모든 요 소 를 포함 할 수 있 습 니 다.List 인 터 페 이 스 를 실현 하 는 것 을 제외 하고 이 종 류 는 내부 에서 list 를 저장 하 는 배열 의 크기 를 조작 하 는 방법 을 제공 합 니 다.(이 큰 문 제 는 벡터 와 같 습 니 다.동기 화 되 지 않 는 것 을 제외 하고.)
Array List 는 가장 자주 사용 하 는 데이터 구조 중의 하나 이다.자바 집합 에 대한 설명(선택):
Array List 가 제한 을 초과 하면 50%용량 이 증가 하고 System.array copy()로 새 배열 로 복사 합 니 다.기본 값 으로 요 소 를 처음 삽입 할 때 10 크기 의 배열 을 만 듭 니 다.배열 아래 에 표 시 된 접근 요소-get(i),set(i,e)의 성능 이 매우 높다.아래 표 시 를 누 르 면 요소-add(i,e),reove(i),reove(e)를 삽입 하고 이동 부분 에 영향 을 받 는 요 소 를 System.array copy()로 복사 하면 성능 이 떨어진다.앞의 요소 일수 록 수정 할 때 이동 해 야 할 요소 가 많 습 니 다.배열 끝 에 요 소 를 직접 추가 합 니 다.자주 사용 하 는 add(e)는 마지막 요 소 를 삭제 하 는 데 영향 을 주지 않 습 니 다.
자동 용량 확장 에 대하 여
배열 의 용량 이 부족 할 때 원 배열 보다 용량 이 큰 새 배열 을 만 들 고 배열 의 요 소 를 새 배열 로 옮 긴 다음 에 새로운 요 소 를 새 배열 에 넣 고 마지막 으로 새 배열 을 원 배열 에 부여 하면 됩 니 다.
주 함수
구조 함수
코드 는 다음 과 같 습 니 다:
/**
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
*
* @param capacity
* the initial capacity of this {@code ArrayList}.
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
* Constructs a new {@code ArrayList} instance with zero initial capacity.
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
/**
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
*
* @param collection
* the collection of elements to add.
*/
public ArrayList(Collection extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}위 코드 에서 보 듯 이 Array List 는 세 개의 구조 함수 가 있 습 니 다.첫 번 째 구조 함수 의 매개 변 수 는 용량 이 고 매개 변수 가 0 일 때 용량 이 0 인 Object 배열 을 형성한다.그렇지 않 으 면 용량 이 매개 변수 인 Object 배열 을 만 듭 니 다.두 번 째 는 우리 가 흔히 볼 수 있 는 것 이 니 군말 하지 않 는 것 이다.세 번 째 구조 함수 의 매개 변 수 는 collection 관련 클래스 입 니 다.먼저 부분 변수 a 를 현재 대상 toArray 의 값(현재 용기 에 있 는 모든 요 소 를 되 돌려 주 고 배열 형식 으로)이 라 고 설명 합 니 다.현재 부분 변수 a 의 유형 이 Object[]류 라면 직접 할당 작업 을 합 니 다.그렇지 않 으 면 System.array copy 작업 을 진행 합 니 다.System.array copy 작업 은 a 배열 의 요 소 를 모두 new Array(유형 은 Object[])에 복사 한 다음 에 똑 같이 할당 작업 을 합 니 다.
add 함수
코드 는 다음 과 같 습 니 다:
/**
* Adds the specified object at the end of this {@code ArrayList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
/**
* Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
*
* @param index
* the index at which to insert the object.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}코드 에서 알 수 있 듯 이 Array List 류 는 두 개의 add 함 수 를 다시 불 러 왔 다.첫 번 째 add 함수 의 인 자 는 add 가 필요 한 요소 입 니 다.그것 의 역할 은 현재 이 요 소 를 배열 의 끝 에 추가 하 는 것 이다.함수 내 에서 size 는 ArrayList 의 요소 의 수량 이 고 a.length 는 현재 배열 의 길이 입 니 다.size 가 a.length 와 다 르 면 size
Object[] newArray = new Object[s + (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];
새 배열 newArray 를 만 들 었 습 니 다.용량 은 이렇게 설정 되 어 있 습 니 다.현재 배열 의 길이 가 MIN 보다 작 으 면CAPACITY_INCREMENT(상수)의 절반 을 확대 하면 새로운 용량 을 원래 의 용량 에 MINCAPACITY_INCREMENT 의 값;그렇지 않 으 면 원래 용량 의 1.5 배로 확대 한다.
두 번 째 add 함 수 는 특정한 위치 에 요 소 를 삽입 하면 더 이상 군말 하지 않 습 니 다(코드 는 위 와 같 습 니 다).그러나 여기에 한 마디 를 추가 합 니 다.현재 요소 의 수량 이 배열 의 길이 보다 적 을 때 삽입 하 는 것 도 귀 찮 습 니 다.전체 배열 을 index 에서 뒤의 요 소 를 모두 뒤로 옮 겨 야 합 니 다.그래서 Array List 의 삽입 효율 이 높 지 않 을 것 입 니 다.
newCapacity 함수
앞에서 알 수 있 듯 이 new Capacity 함 수 는 확장 을 담당 하 는 것 으로 그 역할 은
Object[] newArray = new Object[s + (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];
비슷 합 니 다.그 코드 는 다음 과 같 습 니 다.
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}이전 코드 가 왜 new Capacity 함 수 를 직접 인용 하지 않 았 는 지 모 르 겠 습 니 다~new Capacity 함수 해석 은 add 의 한 단락 과 같 아야 합 니 다.현재 배열 의 길이 가 MIN 보다 작 으 면CAPACITY_INCREMENT(상수)의 절반 을 확대 하면 새로운 용량 을 원래 의 용량 에 MINCAPACITY_INCREMENT 의 값;그렇지 않 으 면 원래 용량 의 1.5 배로 확대 한다.
addAll 함수
/**
* Adds the objects in the specified collection to this {@code ArrayList}.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
@Override public boolean addAll(Collection extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
/**
* Inserts the objects in the specified collection at the specified location
* in this List. The objects are added in the order they are returned from
* the collection's iterator.
*
* @param index
* the index at which to insert.
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override
public boolean addAll(int index, Collection extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}두 개의 addAll 함 수 를 다시 불 러 왔 습 니 다.첫 번 째 addAll 함 수 는 Collection 대상 의 요 소 를 배열 뒤에 삽입 합 니 다.기본 원 리 는 add 와 사실 매우 유사 하 다.두 번 째 addAll 함수 도 더 이상 군말 하지 않 습 니 다.
get 함수 와 set 함수
코드 는 다음 과 같 습 니 다:
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}/**
* Replaces the element at the specified location in this {@code ArrayList}
* with the specified object.
*
* @param index
* the index at which to put the specified object.
* @param object
* the object to add.
* @return the previous element at the index.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location >= size()}
*/
@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
}get 함 수 는 매우 직접적 입 니 다.Array List 는 배열 이기 때문에 색인 을 통 해 직접 값 을 얻 으 면 됩 니 다.set 함수 역시 색인 을 통 해 해당 요소 의 내용 을 변경 합 니 다.그래서 Array List 의 액세스 효율 이 매우 빠 를 것 임 을 알 수 있다.
제거 함수
코드 는 다음 과 같 습 니 다:
/**
* Removes the object at the specified location from this list.
*
* @param index
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location >= size()}
*/
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
@Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}remove 함수 두 개 를 다시 불 러 왔 습 니 다.첫 번 째 remove 함수 의 인 자 는 색인 입 니 다.현재 색인 요 소 를 삭제 하 는 것 입 니 다.사실은 그 본질은 새로운 배열 을 복사 한 것 이다.작 동 하 는 배열 은 index+1 이 위치 에서 시작 하 는 오른쪽 모든 요 소 를 전체적으로 왼쪽으로 이동 하 는 동시에 a[s](즉,원래 배열 의 끝 요소)의 요 소 를 null 로 설정 하 는 것 이다.두 번 째 remove 함수 의 인 자 는 현재 삭제 해 야 할 요소 입 니 다.들 어 오 는 인자 가 null 이면 현재 배열 을 옮 겨 다 닙 니 다.한 요소 의 값 이 null 이면 이 요 소 를 제거 하고 복사 요소(System.array copy)방식 으로 현재 null 요소 의 위치 오른쪽 요 소 를 전체적으로 왼쪽으로 이동 합 니 다.들 어 오 는 인자 가 null 이 아 닐 때 도 현재 배열 을 옮 겨 다 니 며 하나의 요소 equals(인자)가 true 인 것 을 찾 으 면 위 와 같은 복사 작업 을 하여 삭 제 를 완료 합 니 다.위 에서 알 수 있 듯 이 삭제 작업 reove 역시 배열 의 복사 와 관련 되 기 때문에 Array List 의 reove 작업 의 효율 은 get,set 만큼 높 지 않 을 것 입 니 다.
작은 매듭
Array List 류 에는 위 에 열거 되 지 않 은 함수 도 있 습 니 다.나중에 제 가 보충 하 겠 습 니 다.(시간 이 있 으 면)Array List 는 거의 제 가 가장 자주 사용 하 는 용기 이기 때문에 저 는 특별히 필 기 를 한 편 써 서 자신의 이 해 를 적 었 고 다른 선배 들 의 글 도 참고 하 였 습 니 다.(그들의 자바 버 전 은 저 와 다 르 고 구체 적 인 함수 실현 은 약간 차이 가 있 을 수 있 습 니 다)자신의 언어 이기 때문에 잘 모 르 는 부분 이 있 을 수 있 습 니 다.어디 에 잘못 썼 는 지 지적 해 주세요.감사합니다.
참고:자바 집합 에 관 한 커닝 자바 ArrayList 작업 원리 및 ArrayList 원리 실현 및 학습 총화
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
