소스 코드 읽 기-Array List 의 내 면 세계 로 들 어가 기

17633 단어 자바
세상 사람들 은 모두 Array List 가 좋다 고 말한다.
그녀 는 사람의 마음 을 잘 이해 하고 생각 이 유연 하 며 생각 이 치밀 하 다.이 글 은 우리 로 하여 금 그녀의 내 면 세 계 를 깊이 이해 하 게 한다.
전편 에 서 는 원본 코드 를 읽 는 방법 을 총 결 했 는데,이 편 에 서 는 Array List 의 원본 코드 를 읽 기 시작 했다.마찬가지 로 YSOCean 의 양질 의 글 JDK 1.8 소스 코드(5)인 자바 util.Array List 류 를 참고 하 세 요.
본문 목록
  • Array List 의 사용
  • Array List 의 정의
  • Array List 의 필드 속성(5 개)
  • Array List 의 구조 함수(3 개)
  • ArrayList 의 주요 기능
  • 증가
  • 삭제(색인 에 따라 삭제,직접 삭제)
  • 검색(색인 에 따라 찾기,요소 에 따라 찾기)
  • Array List 를 사용 하 는 옮 겨 다 니 는 방법
  • ArrayList 류 의 기타 방법(trimToSize 방법)
  • ArrayList 사용
    원본 코드 를 읽 기 전에 우 리 는 Array List 가 무엇 을 하 는 지 알 아야 한다.만약 그것 을 사용 하 는 것 에 정통 하 다 면 우 리 는 그것 의 원본 코드 를 더욱 잘 이해 할 수 있 을 것 이다.그래서 마지막 에 저 는 Array List 를 사용 하 는 사용 을 붙 여서 이해 하기 편 합 니 다.
    ArrayList 의 정의
    Array List 는 배열 로 이 루어 진 집합 으로 무 작위 접근 을 지원 하 며 요소 가 질서 가 있 고 중복 할 수 있 습 니 다.(퍼 텐 셜 익 스 텐션
  • 은 RandomAccess 인 터 페 이 스 를 실 현 했 습 니 다.이것 은 태그 인터페이스 입 니 다.일반 태그 인 터 페 이 스 는 List 실현 에 사용 되 며 빠 른(보통 고정 시간)무 작위 접근 을 지원 한 다 는 것 을 나타 냅 니 다.이 인터페이스의 주요 목적 은 유 니 버 설 알고리즘 이 무 작위 나 순서 로 목록 에 접근 할 때 좋 은 성능 을 제공 할 수 있 도록 하 는 것 이다.
  • 은 Cloneable 인 터 페 이 스 를 실현 했다.Cloneable 은 RandomAccess 인터페이스 와 마찬가지 로 태그 인터페이스 이기 도 하 다.인터페이스 에 어떠한 방법 체 와 상수 의 성명 도 없다.즉,대상 을 복제 하려 면 Cloneable 인 터 페 이 스 를 실현 해 야 한 다 는 것 은 복 제 될 수 있다 는 것 을 나타 낸다.
  • 은 Serializable 인터페이스 도 태그 인터페이스 로 직렬 화 될 수 있 음 을 나타 낸다.
  • 은 List 인 터 페 이 스 를 실현 했다.이 인 터 페 이 스 는 List 류 집합 의 상층 인터페이스 로 이 인 터 페 이 스 를 실현 하 는 유형 이 모두 실현 해 야 하 는 방법 을 정의 했다.
  • ArrayList 의 필드 속성(5 개)
  • 집합의 기본 크기:private static final int DEFAULTCAPACITY = 10;
  • 빈 배열 인 스 턴 스:private static final Object[]EMPTYELEMENTDATA = {};
  • 이것 도 빈 배열 인 스 턴 스 와 EMPTYELEMENTDATA 빈 배열 에 비해 배열 이 처음으로 요 소 를 추가 할 때 배열 이 얼마나 팽창 하 는 지 알 아 보 는 데 사 용 됩 니 다:private static final Object[]DEFAULTCAPACITYEMPTY_ELEMENTDATA = {};
  • ArrayList 집합 요 소 를 저장 합 니 다.집합 길 이 는 바로 이 배열 의 길이 입 니 다.transient Object[]element Data;
  • 1,해당 element Data==DEFAULTCAPACITYEMPTY_ELEMENTDATA 시 ArrayList
  • 이 삭 제 됩 니 다.
  • 2、첫 번 째 요 소 를 추가 할 때 element Data 길 이 는 DEFAULT 로 확 장 됩 니 다.CAPACITY=10

  • 은 집합 길 이 를 나타 낸다.private int size;

  • ArrayList 의 구조 함수(3 개)
  • 이 무 참 구조 함 수 는 하 나 를 만 들 것 입 니 다. DEFAULTCAPACITY_EMPTY_ELEMENTDATA 가 설명 한 배열 은 10 이 아니 라 초기 용량 이 0 이 라 고 생각 합 니 다.
    public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
     
  • 집합 크기 를 초기 화하 여 ArrayList 집합 을 만 듭 니 다.0 보다 많 을 때 주어진 만큼 큰 배열 을 만 듭 니 다.0 과 같 을 때 빈 배열 만 들 기;0 보다 작 을 때 이상 을 던 집 니 다.
    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);
            }
        }
     
  • 기 존 집합 을 Array List 집합 으로 복사 합 니 다.
    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;
            }
        }
     

  • ArrayList 의 주요 기능(추가 삭제 및 수정)
    늘다
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        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);
        }
  • 소스 코드 프로 세 스:
  • 요 소 를 추가 하기 전에 우 리 는 먼저 ensureCapacity Internal 방법 을 사용 하여 집합 크기 를 확인 하고 집합 이 가득 차 면 확장 작업 을 해 야 한다.
  • (ensureCapacity 내부 방법)ensureExplicitCapacity 방법 호출
  • (ensureExplicitCapacity 방법)우선 수정 횟수 modCount 에
  • 을 추가 합 니 다.
  • minCapacity 가 현재 ArrayList 내부 배열 의 길이 보다 큰 지 판단 합 니 다.크 면 grow 방법 으로 내부 배열 element Data 확장
  • (grow 방법 확장)

  • 첨가 원소
  • 복귀 true
  • 실제 사례 절차
  • ① 통과 Array List()는 빈 집합 을 구성 합 니 다.초기 길 이 는 0 이 고 첫 번 째 요 소 를 추가 하면 길이 가 10 인 배열 을 만 들 고 이 요 소 를 배열 의 첫 번 째 위치 에 할당 합 니 다.
  • ②,두 번 째 요 소 를 추가 하고 집합 이 비어 있 지 않 으 며 집합 길이 의 size+1 은 배열 의 길이 10 보다 작 기 때문에 배열 의 두 번 째 위치 에 요 소 를 직접 추가 하여 확장 할 필요 가 없다.
  • ③、11 번 째 요 소 를 추가 합 니 다.이때 size+1=11 이 고 배열 의 길 이 는 10 입 니 다.이때 길이 가 10+10*0.5=15 인 배열(1.5 배 확장)을 만 든 다음 에 원래 배열 요 소 를 참조 하여 새 배열 로 복사 합 니 다.11 번 째 로 추 가 된 요 소 를 새 배열 아래 10 으로 표시 합 니 다.
  • ④ 번 Integer.MAX_VALUE-8=2147483639,그리고 21474836339%1.5=1431655759 1431655759+1 크기 의 배열 은 이렇게 한 요 소 를 추가 할 때마다 한 범위 만 확대 한다.

  • ⑤ Integer.MAX_VALUE-요 소 를 7 번 추가 할 때 크기 를 Integer.MAX_VALUE 의 배열 은 요 소 를 추가 하고 있 습 니 다.
    ⑥、제 Integer.MAX_VALUE+원소 1 회 추가 시 던 지기 OutOf Memory 오류 이상.
  • 주의:집합 에 null 을 추가 할 수 있 습 니 다.배열 에 null 값 이 존재 할 수 있 기 때 문 입 니 다.

  • //ArrayList    Add  
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        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);
        }
    
         /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        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);
        }

    삭제 하 다.
  • 색인 에 따라 요 소 를 삭제 합 니 다.
  • 우선 주어진 색인 의 범 위 를 판단 하고 0 보다 작 거나 집합 크기 를 초과 하면 이상
  • 을 던 집 니 다.
  • 빠 른 삭제 방법 을 호출 하여 true
  • 으로 돌아 갑 니 다.
  • 지정 한 요 소 를 직접 삭제 합 니 다(처음 나타 난 요 소 를 삭제 한 다음 arraycopy 를 사용 하여 배열 자체 복사)
  • 이 비어 있 으 면 옮 겨 다 니 며 첫 번 째 빈 요 소 를 찾 아 빠르게 삭제 하고 true
  • 으로 돌아 갑 니 다.
  • 비어 있 지 않 으 면 옮 겨 다 니 며 equals 방법 으로 동일 여 부 를 판단 하고 첫 번 째 로 나타 난 것 을 찾 아 빠르게 삭제 하고 true
  • 으로 돌아 갑 니 다.
  • 위 에 두 개 를 실행 하지 않 으 면 false
  • 으로 돌아 갑 니 다.
  • 전에 둘 다 빠 른 삭제 방법 을 사 용 했 습 니 다:fastRemove(int index)
  • index 를 계산 한 후의 배열 의 길이 numMoved
  • array copy 방법 을 통 해 오래된 배열 index+1 이후 길이 가 numMoved 인 요 소 를 오래된 배열 index 에서 시작 하 는 위치 로 복사 하고 마지막 요 소 를 null 로 설정 하면 쓰레기 회수 에 편리 합 니 다
  • //ArrayList    remove  
        /**
         * Removes the element at the specified position in this list.
         * Shifts any subsequent elements to the left (subtracts one from their
         * indices).
         *
         * @param index the index of the element to be removed
         * @return the element that was removed from the list
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        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;
        }
    
        /**
         * Removes the first occurrence of the specified element from this list,
         * if it is present.  If the list does not contain the element, it is
         * unchanged.  More formally, removes the element with the lowest index
         * i such that
         * (o==null ? get(i)==null : o.equals(get(i)))
         * (if such an element exists).  Returns true if this list
         * contained the specified element (or equivalently, if this list
         * changed as a result of the call).
         *
         * @param o element to be removed from this list, if present
         * @return true if this list contained the specified element
         */
        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 remove method that skips bounds checking and does not
         * return the value removed.
         */
        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
        }

    조사 하 다.
  • 색인 에 따라 요 소 를 찾 습 니 다.
  • 판단 색인 범위
  • 색인 의 값
  • 을 되 돌려 줍 니 다.
  • 원소 에 따라 색인 찾기
  • 대상 이 비어 있 으 면 옮 겨 다 니 며 첫 번 째 빈 대상 을 찾 아 색인
  • 을 되 돌려 줍 니 다.
  • 대상 이 비어 있 지 않 으 면 옮 겨 다 니 며 첫 번 째 값 을 찾 은 대상 의 값 을 찾 아 색인
  • 을 되 돌려 줍 니 다.
  • 을 찾 지 못 했 습 니 다.-1
  •     /**
         * Returns the element at the specified position in this list.
         *
         * @param  index index of the element to return
         * @return the element at the specified position in this list
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
    
        /**
         * Checks if the given index is in range.  If not, throws an appropriate
         * runtime exception.  This method does *not* check if the index is
         * negative: It is always used immediately prior to an array access,
         * which throws an ArrayIndexOutOfBoundsException if index is negative.
         */
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
     
        /**
         * Returns the index of the first occurrence of the specified element
         * in this list, or -1 if this list does not contain the element.
         * More formally, returns the lowest index i such that
         * (o==null ? get(i)==null : o.equals(get(i))),
         * or -1 if there is no such index.
         */
        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;
        }

    고치다.
  • 판단 색인 범위
  • 지정 색인 index 의 요 소 를 element
  • 으로 대체 합 니 다.
  • 원 배열 의 수 정 된 요 소 를 되 돌려 줍 니 다.
  •    /**
         * Replaces the element at the specified position in this list with
         * the specified element.
         *
         * @param index index of the element to replace
         * @param element element to be stored at the specified position
         * @return the element previously at the specified position
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

    Array List 를 옮 겨 다 니 는 방법 사용 하기
  • 사용 용
  • 교체 기 iterator
  • 교체 기의 변종 foreach
  • 교체 기 ListIterator
  • ArrayList list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    
    //  for
    for(String str : list){
        System.out.print(str + " ");
    }
    
    //     
    Iterator it = list.iterator();
    while(it.hasNext()){
        String str = it.next();
        System.out.print(str+" ");
    }
    
    //  foreach
    for(String str : list){
        System.out.print(str + " ");
    }
    
    //    ListIterator
    ListIterator listIt = list.listIterator();
    
    //    
    while(listIt.hasNext()){
        System.out.print(listIt.next()+" ");//a b c
    }
    //     ,             ,             ,           
    while(listIt.hasPrevious()){
        System.out.print(listIt.previous()+" ");//c b a
    }
    
    

    기타 방법
    trimToSize 방법:이 방법 은 남 은 메모 리 를 회수 하 는 데 사 용 됩 니 다.즉,집합 이 불필요 한 요 소 를 추가 하지 않 는 다 는 것 을 확인 한 후에 trimToSize()방법 을 사용 하면 집합 을 실현 하 는 배열 의 크기 를 집합 요소 의 크기 로 조정 할 것 이다.메모:이 방법 은 배열 요 소 를 복사 하 는 데 시간 이 걸 리 기 때문에 요 소 를 추가 하지 않 을 지 확인 한 후에 호출 해 야 합 니 다.
        /**
         * Trims the capacity of this ArrayList instance to be the
         * list's current size.  An application can use this operation to minimize
         * the storage of an ArrayList instance.
         */
        public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

     
    //ArrayList   
    public static void main(String[] args) {
    		//             list,list    String     
            ArrayList list = new ArrayList();
    
            //      list   
            list.add("Item1");
            list.add("Item2");
            list.add(2, "Item3"); //        “Item3”      list  3   。
            list.add("Item4");
    
            //           
            System.out.println("The arraylist contains the following elements: "
                    + list);
    
            //        
            int pos = list.indexOf("Item2");
            System.out.println("The index of Item2 is: " + pos);
    
            //           
            boolean check = list.isEmpty();
            System.out.println("Checking if the arraylist is empty: " + check);
    
            //        
            int size = list.size();
            System.out.println("The size of the list is: " + size);
    
            //               
            boolean element = list.contains("Item5");
            System.out
                    .println("Checking if the arraylist contains the object Item5: "
                            + element);
    
            //           
            String item = list.get(0);
            System.out.println("The item is the index 0 is: " + item);
    
            //   arraylist    
    
            //  1   :                
            System.out
                    .println("Retrieving items with loop using index and size list");
            for (int i = 0; i < list.size(); i++) {
                System.out.println("Index: " + i + " - Item: " + list.get(i));
            }
    
            //  2   :  foreach  
            System.out.println("Retrieving items using foreach loop");
            for (String str : list) {
                System.out.println("Item is: " + str);
            }
    
            //      :     
            // hasNext():   true           
            // next():        
            System.out.println("Retrieving items using iterator");
            for (Iterator it = list.iterator(); it.hasNext();) {
                System.out.println("Item is: " + it.next());
            }
    
            //     
            list.set(1, "NewItem");
            System.out.println("The arraylist after the replacement is: " + list);
    
            //     
            //    0       
            list.remove(0);
    
            //          "Item3"  
            list.remove("Item3");
    
            System.out.println("The final contents of the arraylist are: " + list);
    
            //    ArrayList   Array
            String[] simpleArray = list.toArray(new String[list.size()]);
            System.out.println("The array created after the conversion of our arraylist is: "
                            + Arrays.toString(simpleArray));
        }

    좋은 웹페이지 즐겨찾기