ArrayList 와 LinkedList 의 밑바닥 실현 과 비교
ArrayList 와 LinkedList 의 차이
public class ArrayList extends AbstractList Array List 의 부 류 는 AbstractList 류 이 고 구체 적 인 부 류, 인터페이스의 관계 입 니 다. 저 는 HashMap 상세 한 해석 에서 집합 류 의 관계 도 를 가지 고 있 습 니 다.
우선, Array List 의 데이터 구 조 를 살 펴 보 겠 습 니 다.
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;ArrayList 의 데이터 구조
Array List 는 element Data 와 size 두 가지 중요 한 속성 을 포함 합 니 다.
ArrayList 에 포 함 된 요소 의 개수 입 니 다.
(1) Object 배열 (즉, 흔히 말 하 는 Array List 의 바 텀 은 배열) 이기 때문에 Array List 는 기본 데 이 터 를 넣 을 수 없습니다 (이것 은 배열 과 의 큰 차이 입 니 다).
（2）transient 수식 을 사용 합 니 다. transient 로 인 스 턴 스 변 수 를 설명 하면 대상 이 저장 할 때 값 을 유지 할 필요 가 없습니다. 다시 말 하면 transient 키워드 로 표 시 된 구성원 변 수 는 직렬 화 과정 에 참여 하지 않 습 니 다. 그러나 실제 전송 과정 에서 우 리 는 분명히 배열 의 요 소 를 얻 을 수 있 습 니 다. 그러면 이것 은 어떻게 이 루어 졌 습 니까? 또 왜 이 루어 졌 습 니까?transient 로 장식 할 까요? Array List 의 구조 함수 가 이미 확장 되 었 는 지 살 펴 보 겠 습 니 다.
ArrayList 용량
Array List 는 두 개의 구조 함수, Public Array List () 와 Public Array List (int initial Capacity) 가 있 습 니 다.
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}상기 소스 코드 와 같이:
ArrayList () 의 기본 capacity 는 10 이 고 ArrayList (int initialCapacity) 의 capacity 는 initialCapacity 입 니 다.
PS: size 는 배열 에 저 장 된 요소 의 개수 이 고 capacity 는 배열 의 용량 입 니 다.
Array List 의 Add
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return true (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}Array List 가 요 소 를 추가 할 때 먼저 ensureCapacity Internal (size + 1) 작업 을 해 야 합 니 다. 즉, capacity 와 size + 1 의 크기 를 판단 하고 capacity > 1) 가 원래 의 1.5 배 배열 로 확대 한 다음 에 원래 의 요 소 를 새 배열 로 복사 합 니 다. 코드 는 다음 과 같 습 니 다.
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);
}elementData transient 앞 에 이 의문 을 남 겼 으 니 이제 야 풀 수 있 게 되 었 다.
위 에서 우 리 는 capacity 가 size 보다 크 고 대부분 size 보다 크다 는 것 을 알 고 있다.따라서 element Data 배열 을 직접 직렬 화하 면 (capacity - size) 개 요소 의 공간 을 낭비 하 게 된다. 특히 capacity - size 가 매우 클 때 이런 낭 비 는 매우 수지 가 맞지 않 는 다.그렇다면 element Data 는 시리 얼 번호 에 의 해 전송 되 지 않 고 어떻게 읽 고 썼 을 까?ArrayList 는 writeObject (java. io. Object OutputStream s) 와 readObject (java. io. Object InputStream s) 방법 을 실현 했다.이 두 가지 방법의 역할 은 구체 적 으로 writeObject 와 readObject 가 무엇 입 니까?맞 춤 형 직렬 화 과정.
/**
* Save the state of the ArrayList instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the ArrayList
* instance is emitted (int), followed by all of its elements
* (each an Object) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; iArrayList instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i ArrayList remove 동작
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}위의 소스 코드 에서 보 듯 이 Array List 의 소스 코드 는 size 의 값 만 바 꿀 수 있 지만 capacity 의 값 은 자동 으로 바 뀌 지 않 습 니 다. 그러나 Array List 는 trimToSize () 를 제공 하여 우리 가 스스로 제어 할 수 있 도록 합 니 다.
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}Array List 의 다른 방법 은 말 하기 가 귀찮다.
LinkedList
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable 그것 의 부류 관 계 는 구체 적 으로 내 가 HashMap 상세 해석 에서 집합 류 의 관계 도 를 보 았 다.
LinkedList 의 데이터 구조
transient int size = 0;
transient Node first;
transient Node last; 위의 소스 코드 에서 보 듯 이 링크 드 리스트 의 바 텀 실현 은 양 방향 링크 이다.
LinkedList 의 추가 작업
LinkedList 는 세 가지 요 소 를 추가 하 는 방법 을 제공 합 니 다.
public void addFirst(E e)；
public void addLast(E e)；
public boolean add(E e)； ，add ： public boolean add(E e) {
linkLast(e);
return true;
}LinkedList 아래 표 시 를 누 르 면 요 소 를 가 져 옵 니 다.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} 다른 것 도 별거 아니 야.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Spring 자동 조립 이해현재 이 클래스 는 @ Repository 표지 가 있 고 내부 에 @ Autowired 가 있 습 니 다. 이 클래스 가 구성 요소 에 스 캔 되면 spring 은 자동 으로 bean 을 생 성하 고 dbAcess...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
