Java 용기 ArrayList 지식 요약

ArrayList
바 텀 실현 은 배열 로 요소 에 접근 하 는 효율 이 높다(조회 가 빠 르 고 삽입,수정,삭제 요소 가 느리다).
LinkedList 에 비해 효율 은 높 지만 스 레 드 는 안전 하지 않 습 니 다.
Array List 배열 은 null 을 포함 한 모든 요 소 를 액세스 할 수 있 는 가 변 배열 입 니 다.

모든 ArrayList 인 스 턴 스 는 하나의 용량 을 가지 고 있 습 니 다.이 용량 은 목록 요 소 를 저장 하 는 배열 의 크기

를 말 합 니 다.

Array List 에 요소 가 계속 증가 함 에 따라 그 용량 은 자동 으로 증가한다

대량의 요 소 를 추가 하기 전에 응용 프로그램 도 ensureCapacity 작업 을 사용 하여 ArrayList 인 스 턴 스 의 용량 을 증가 시 킬 수 있 습 니 다.그러면 증가 식 재분배 의 수량 을 줄 일 수 있 습 니 다.

그래서 만약 에 우리 가 삽 입 된 요소 의 많 고 적 음 을 명 확 히 한다 면 초기 용량 치 를 지정 하여 너무 많은 확장 작업 을 해서 시간 과 효율 을 낭비 하지 않도록 하 는 것 이 좋 습 니 다

소스 코드 분석

바 텀 사용 배열 구현

transient Object[] elementData;

구조 방법

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
 
//        
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
  }
 
//               
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);
    }
  }
 
 
//       Collection     ，      Connection             
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
      // c.toArray might (incorrectly) not return Object[] (see 6260652)
      if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
      // replace with empty array.
      this.elementData = EMPTY_ELEMENTDATA;
    }
  }
 

기억

//             element  ，            
public E set(int index, E element) {
    rangeCheck(index); //       ，  ：IndexOutOfBoundsException
 
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
  }
 
//             
public boolean add(E e) {
    ensureCapacityInternal(size + 1); //     
    elementData[size++] = e;
    return true;
  }
 
//             
public void add(int index, E element) {
    rangeCheckForAdd(index);
 
    ensureCapacityInternal(size + 1); // Increments modCount!!
 
    // src:   ,srcPro:         
    // dest:    ，destPost:         ，length:          
       //                          
    System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
    //  element  index     
    elementData[index] = element;
    size++;
  }
 
//         Connection    ，      Connection        
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray(); //        
 
    int numNew = a.length;
    ensureCapacityInternal(size + numNew); // Increments modCount
 
    // Increments modCount!!
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
  }
 
//           Connection    ，      Connection        
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;
  }
 

읽 기

//              
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;
  }
 
private void fastRemove(int index) {
    modCount++;
    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
  }
 

배열 확장
배열 에 요 소 를 추가 할 때마다 요 소 를 추가 한 후의 요소 의 개수 가 현재 배열 의 길 이 를 초과 하 는 지 확인 해 야 합 니 다.초과 하면 배열 은 확장 하여 데 이 터 를 추가 하 는 수 요 를 만족 시 킬 것 입 니 다.

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA )   
      ? 0 : DEFAULT_CAPACITY;
 
    if (minCapacity > minExpand) {
      ensureExplicitCapacity(minCapacity);
    }
  }
 
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) {
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
 
    ensureExplicitCapacity(minCapacity);
  }
 
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
 
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
  }
 
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);
  }
 
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
      MAX_ARRAY_SIZE;
  }
 

손 글씨 배열 목록

public class MyArrayList /*implements List<E>*/{
 private transient Object[] elementData;
 private int size; //    
 
 public MyArrayList(){
  this(10);
 }
 
 public MyArrayList(int initialCapacity) {
  if (initialCapacity<0) {
   try {
    throw new Exception();
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
  elementData = new Object[initialCapacity];
 }
 
 public int size() {
  return size;
 }
 
 public boolean isEmpty(){
  return size == 0;
 }
 //  index    
 public void remove(int index) throws Exception {
  rangeCheck(index);
  int numMoved = size-index-1;
  if (numMoved > 0) {
   System.arraycopy(elementData, index+1, elementData, index, numMoved);
  }
  elementData[--size] = null;
 }
 //    
 public boolean remove(Object obj) throws Exception {
  for (int i = 0; i < size; i++) {
   if (get(i).equals(obj)) {
    remove(i);
   }
   return true;
  }
  return true;
 }
 //    
 public Object set(int index , Object obj ) throws Exception{
  rangeCheck(index);
  Object oldValue = elementData[index];
  elementData[index] = obj;
  return oldValue;
 }
 //         
 public void add(int index,Object obj) throws Exception {
  rangeCheck(index);
  ensureCapacity();
  System.arraycopy(elementData, index, elementData, index+1, size-index);
  elementData[index] = obj;
  size ++;
 }
 public void add(Object object) {
  ensureCapacity();
  /*elementData[size] = object;
  size ++;*/
  elementData[size++] = object; //   ，   
 }
 
 public Object get(int index) throws Exception {
  rangeCheck(index);
  return elementData[index];
 }
 public void rangeCheck(int index) throws Exception {
  if (index<0 || index >=size) {
   throw new Exception();
  }
 }
 //  
 public void ensureCapacity() {
  //         
  if (size==elementData.length) {
   //elementData = new Object[size*2+1];              
   Object[] newArray = new Object[size*2+1];
   //        
   /*for (int i = 0; i < newArray.length; i++) {
    newArray[i] = elementData[i];
   }*/
   System.arraycopy(elementData, 0, newArray, 0, elementData.length);
   elementData = newArray;
  }
 }
 //   
 public static void main(String[] args) {
  MyArrayList myArrayList = new MyArrayList(3);
  myArrayList.add("111");
  myArrayList.add("222");
  myArrayList.add("333");
  myArrayList.add("444");
  myArrayList.add("555");
  
  try {
   myArrayList.remove(2);
   myArrayList.add(3, "  ");
   myArrayList.set(1, "  ");
  } catch (Exception e1) {
   // TODO Auto-generated catch block
   e1.printStackTrace();
  }
  System.out.println(myArrayList.size());
  for (int i = 0; i < myArrayList.size(); i++) {
   try {
    System.out.println(myArrayList.get(i));
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }
}