Java 개선 장(32)------목록 요약-java지도 시간-php.cn

집

Java

java지도 시간

Java 개선 장(32)------목록 요약

黄舟

Feb 11, 2017 am 10:21 AM

이전에 LZ는 ArrayList, LinkedList, Vector, Stack 등 List 인터페이스에 대한 대부분의 지식을 완전히 소개했습니다. 이러한 지식 포인트를 통해 List 인터페이스에 대한 더 깊은 이해를 가질 수 있습니다. 귀납법을 통해 요약된 지식만이 당신의 지식이다. 따라서 아래에서 LZ는 List 인터페이스를 요약합니다. 추천도서:

Java 개선 장(21)---- - ArrayList

> Java 개선 장(29)------벡터

Java 개선(Sanyi) -----스택

1. List 인터페이스 개요

List 인터페이스는 순서가 지정된 Collection, 즉 시퀀스가 됩니다. 이 인터페이스는 목록의 각 요소 삽입 위치를 정밀하게 제어할 수 있으며, 사용자는 정수 인덱스(목록의 위치)를 기준으로 요소에 액세스하고 목록의 요소를 검색할 수 있습니다. 다음 그림은 List 인터페이스의 프레임워크 다이어그램입니다.

프레임워크 다이어그램을 보면 List의 클래스와 인터페이스를 명확하게 이해할 수 있습니다.

Collection의 루트 인터페이스 계층. 컬렉션의 요소라고도 하는 개체 집합을 나타냅니다. Collection의 경우 직접적인 구현을 제공하지 않으며 모든 구현은 해당 하위 클래스의 책임입니다.

AbstractCollection:

이 인터페이스 작업을 구현할 필요성을 최소화하기 위해 Collection 인터페이스의 백본 구현을 제공합니다. 불변 컬렉션을 구현하려면 간단히 이 클래스를 확장하고 반복자와 크기 메서드의 구현을 제공하면 됩니다. 그러나 수정 가능한 컬렉션을 구현하려면 이 클래스의 add 메서드를 재정의해야 하며(그렇지 않으면 UnsupportedOperationException이 발생함) 반복자 메서드에서 반환된 반복자도 해당 제거 메서드를 구현해야 합니다.

tererator:

iterator.

목록: 컬렉션에서 인터페이스를 상속합니다. 순서가 지정된 대기열을 나타냅니다.

AbstractList: "랜덤 액세스" 데이터 저장소 구현을 최소화하기 위한 목록 인터페이스의 백본 구현(예: 배열로)가 이 인터페이스가 작동하는 데 필요합니다.

큐: 큐. 큐에 대한 기본 삽입, 검색 및 검사 작업을 제공합니다.

Deque: 양쪽 끝에서 요소 삽입 및 제거를 지원하는 선형 컬렉션입니다. 대부분의 Deque 구현에는 포함할 수 있는 요소 수에 대한 고정된 제한이 없지만 이 인터페이스는 용량이 제한된 deque와 고정된 크기 제한 없이 deque를 모두 지원합니다.

목록. 어떤 의미에서 이 클래스는 목록의 목록 반복자에 "임의 액세스" 메서드를 구현하는 것과 동일합니다.

> 목록 인터페이스. 모든 선택적 목록 작업을 구현합니다.

~ 모든 선택적 목록 작업을 구현하고 null을 포함한 모든 요소를 허용합니다. List 인터페이스 구현 외에도 이 클래스는 목록을 저장하기 위해 내부적으로 사용되는 배열의 크기를 조작하는 메서드도 제공합니다.

벡터:

는 확장 가능한 객체 배열을 구현합니다. 배열과 마찬가지로 정수 인덱스를 사용하여 액세스할 수 있는 구성 요소를 포함합니다.

스택:

LIFO(후입선출) 객체 스택. 벡터를 스택으로 처리할 수 있는 5가지 작업으로 Vector 클래스를 확장합니다.

열거:

이 인터페이스를 구현하는 객체인 열거는 일련의 요소를 생성합니다. 한 번. nextElement 메소드를 연속적으로 호출하면 일련의 연속 요소가 반환됩니다.

2. 사용 시나리오

지식을 배우는 근본적인 목적은 그것을 활용하는 것입니다. 각 지식 포인트에는 사용 범위가 있습니다. 컬렉션의 경우에도 마찬가지입니다. Java의 컬렉션 제품군은 매우 크며 각 구성원은 가장 적합한 사용 시나리오를 가지고 있습니다. 처음 List를 접했을 때 LZ는 "스택", "큐", "연결된 목록"과 같은 작업이 포함된 경우에는 List를 우선적으로 사용하라고 말했습니다.

어떤 List인지는 다음과 같이 구분됩니다.

1. 링크드리스트.

2. 요소에 빠르게 액세스해야 하는 경우 ArrayList를 사용해야 합니다.

3. "단일 스레드 환경" 또는 "다중 스레드 환경이지만 목록은 하나의 스레드로만 작동"하는 경우 비동기 사용을 고려해야 합니다. "멀티 스레드 환경이고 동시에 여러 스레드에서 목록을 작동할 수 있는 경우" 동기화된 클래스(예: Vector)를 사용하는 것이 좋습니다.

2.1 ArrayList, LinkedList 성능 분석

또한 사용 시나리오와 차이점에 대해서도 배웠습니다.

아아앙 실행 결과:

插入 100000元素ArrayList花费 3900 毫秒
插入 100000元素LinkedList花费 15 毫秒
插入 100000元素Vector花费 3933 毫秒
--------------------------------------
读取100000元素ArrayList花费 0 毫秒
读取100000元素LinkedList花费 8877 毫秒
读取100000元素Vector花费 16 毫秒
--------------------------------------
删除100000元素ArrayList花费 4618 毫秒
删除100000元素LinkedList花费 16 毫秒
删除100000元素Vector花费 4759 毫秒

从上面的运行结果我们可以清晰的看出ArrayList、LinkedList、Vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, E element),delete、get方法各位如有兴趣可以研究研究。

首先我们先看三者之间的源码：

ArrayList

public void add(int index, E element) {
        rangeCheckForAdd(index);   //检查是否index是否合法

        ensureCapacityInternal(size + 1);  //扩容操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);    //数组拷贝
        elementData[index] = element;   //插入
        size++;
    }

rangeCheckForAdd、ensureCapacityInternal两个方法没有什么影响，真正产生影响的是System.arraycopy方法，该方法是个JNI函数，是在JVM中实现的。声明如下：

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

目前LZ无法看到源码，具体的实现不是很清楚，不过System.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着ArrayList的add(int index, E element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。

LinkedList

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)     //插入位置在末尾
            linkLast(element);
        else                   
            linkBefore(element, node(index));
    }

该方法比较简单，插入位置在末尾则调用linkLast方法，否则调用linkBefore方法，其实linkLast、linkBefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：

Node<E> node(int index) {
        if (index < (size >> 1)) {    //如果index 小于 size/2 则从头开始查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {   //如果index 大于 size/2 则从尾部开始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

所以linkedList的插入动作比ArrayList动作快就在于两个方面。1：linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index

Vector

Vector的实现机制和ArrayList一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：

public void add(int index, E element) {
        insertElementAt(element, index);
    }
    
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

上面是针对ArrayList、LinkedList、Vector三者之间的add（int index,E element)方法的解释，解释了LinkedList的插入动作要比ArrayList、Vector的插入动作效率为什么要高出这么多！至于delete、get两个方法LZ就不多解释了。

同时LZ在写上面那个例子时发现了一个非常有趣的现象，就是linkedList在某些时候执行add方法时比ArrayList方法会更慢！至于在什么情况？为什么会慢LZ下篇博客解释，当然不知道这个情况各位是否也遇到过？？