저는 거의 모든 학생들이 필기시험과 면접 시 ArrayList와 LinkedList의 유사점과 차이점에 대해 질문을 받을 것이라고 믿습니다. 전자는 배열 구현을 기반으로 하고 후자는 연결 목록 구현을 기반으로 하는 반면 전자는 임의의 방법이 빠르며 지정된 위치에 삭제 및 삽입이 느립니다. 임의 액세스는 느리고 지정된 위치에서 삭제 및 삽입은 빠릅니다. 둘 다 목록과 배열 사이의 차이점입니다.
목록과 배열의 가장 큰 차이점 중 하나는 배열은 초기화 중에 크기를 조정해야 하며 동적으로 확장할 수 없는 반면 목록은 동적으로 확장할 수 있다는 것입니다. ArrayList는 배열을 기반으로 구현되는데 어떻게 동적 확장을 달성합니까?
ArrayList를 초기화하는 방법에는 세 가지가 있습니다.
첫 번째 기본 구성 방법의 경우 ArrayList는 용량을 초기화하지 않지만 목록의 요소 데이터 참조를 빈 배열로 가리킵니다.
private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {};//1.ArrayList默认构造方法public ArrayList() { super();this.elementData = EMPTY_ELEMENTDATA;
}JDK1.6은 기본 생성자를 호출할 때에도 용량을 초기화합니다. JDK1.7은 확실히 초기화를 사용하지 않으면 낭비가 됩니다. 저장 공간을 추가한 후 용량을 초기화할 때까지 기다리세요.
//JDK1.6 ArrayListpublic ArrayList() {this(10);
}두 번째 구성 방법은 지정된 크기의 배열을 직접 만들고 목록의 요소 배열 참조를 가리킵니다.
//2.ArrayList带有初始化大小的构造方法public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity];
}세 번째 생성 방법은 컬렉션을 매개 변수로 전달할 수 있지만 컬렉션의 요소는 ArrayList의 요소에서 상속되어야 합니다.
//3.可将一个集合作为ArrayList的参数构造成ArrayListpublic ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //将集合转换为数组size = elementData.length; //集合中的元素大小// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}위에 언급된 버그가 있는데, 이는 컬렉션을 배열로 변환할 때 실수로 Object[]가 반환되지 않을 수 있다는 것을 의미합니다.
1 package com.algorithm.sort; 2 3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6 7 /** 8 * bug编号:6260652。toArray有可能不会返回Object[] 9 * Created by yulinfeng on 2017/6/26.10 */11 public class Test {12 public static void main(String[] args) {13 correctly();14 incorrectly();15 }16 17 /**18 * 返回Object[]19 */20 private static void correctly() {21 List<String> list = new ArrayList<String>();22 list.add("test");23 System.out.println(list.getClass());24 Object[] objArray = list.toArray();25 System.out.println(objArray.getClass());26 }27 /**28 * 不返回Object[]29 */30 private static void incorrectly() {31 List<String> list = Arrays.asList("test");32 System.out.println(list.getClass());33 Object[] objArray = list.toArray();34 System.out.println(objArray.getClass());35 }36 }실행 결과:
위의 예에서는 toArray가 항상 Object[]를 반환하지 않는다는 것을 보여줍니다. Object[]가 반환되면 Object 요소를 삽입할 수 없으므로 JDK는 "6260652"에 있습니다. 이 버그는 수정되었습니다.
다음으로 요소 삽입, 삭제 등 다른 방법을 살펴보겠습니다.
//ArrayList#addpublic boolean add(E e) {
ensureCapacityInternal(size + 1); //确保容量是否充足elementData[size++] = e; //将元素添加至数组return true;
}//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10 }
ensureExplicitCapacity(minCapacity); //检查容量是否充足}//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) {
modCount++; //注意此变量if (minCapacity - elementData.length > 0)
grow(minCapacity); //容量不够则进行扩容}sureEcplicitCapacity 메소드에서 증가하는 modCount(수정 횟수) 변수가 있습니다.
protected transient int modCount = 0;
이 변수는 add 메소드에서 자동으로 증가할 뿐만 아니라 추가 또는 삭제 등 ArrayList 구조가 변경될 때마다 기록되어 1씩 증가합니다. 그 이유는 Iterator 순회와 관련이 있습니다. 멀티스레딩에서. AbstractList$Itr에도 이에 해당하는 변수가 있습니다.
//AbstractList$Itrint expectedModCount = modCount;
checkForComodification 메소드는 AbstractList$Itr#next에서 호출됩니다.
//AbstractList$Itr#checkForComodificationfinal void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
} 현재 실행 중인 환경이 단일 스레드인 경우 추가, 수정, 삭제 등 목록에서 어떤 작업이 수행되더라도 예기치 않은ModCount는 항상 modCount와 동일합니다. 환경은 다중 스레드이므로 한 스레드가 반복 순회 중에 다른 스레드가 이를 추가하거나 수정하는 동안 JDK는 이를 허용하지 않습니다. 이 때 ConcurrentModificationException 예외가 발생합니다. 여기에 modCount 변수가 있습니다.
ArrayList#add 메소드로 돌아가서 목록 용량이 부족할 경우, 용량을 확장하기 위해 성장 메소드가 호출됩니다.
//ArrayList#growprivate void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; //扩容策略扩得太小if (newCapacity - MAX_ARRAY_SIZE > 0) //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUEnewCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}ArrayList는 지정된 인덱스 위치에서 요소 get 메소드를 가져옵니다.
public E get(int index) {
rangeCheck(index); //检查索引是否越界return elementData(index);
}ArrayList는 배열을 기반으로 구현되므로 이 방법은 비교적 간단합니다. 범위를 벗어났는지 여부만 판단하면 됩니다. 그렇지 않으면 배열 첨자에 따라 요소를 색인화하고 반환하면 됩니다. 제거 메소드는 지정된 위치의 요소를 삭제합니다.
//ArrayList#removepublic E remove(int index) {
rangeCheck(index); //检查索引是否越界modCount++; //记录modCount，上面已提及E oldValue = elementData(index); //取出指定索引元素int numMoved = size - index - 1; //移动的元素个数if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //将最后一个数组元素置为null，方便GCreturn oldValue;
} 코드는 비교적 간단하며, 지정된 요소를 삭제할 때 배열 관행에 따른 ArrayList의 효율성 문제도 반영합니다. Arrays.copyOf 및 System.arraycopy 메서드에 대한 자세한 내용은 "System.arraycopy(src, srcPos, dest, destPos, length)와 Arrays.copyOf(original, newLength)의 차이점"을 참조하세요.
위 내용은 ArrayList의 일반적인 메소드에 대한 자세한 소스 코드 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
