Java 改善の章 (32)-----リストの概要-＆＃＆チュートリアル-php.cn

分前回の LZ では、ArrayList、LinkedList、Vector、Stack など、List インターフェイスに関するほとんどの知識を完全に紹介しました。これらの知識ポイントを通じて List インターフェイスを深く理解することができます。帰納法によって要約された知識だけがあなたの知識です。そこで以下では、LZ が List インターフェースの概要を説明します。推奨読書:

Java の改善の章 (Two One)-----ArrayList

Java の改善の章 (Two Two)----- LinkedList V a java改善の章(29日) ----- Vector

javaの増加の章(9月) ----- stack

、リストインターフェースの概要

List インターフェースは順序付けられたコレクション、つまりシーケンスになります。このインターフェイスは、リスト内の各要素の挿入位置を正確に制御でき、ユーザーは整数インデックス (リスト内の位置) に基づいて要素にアクセスし、リスト内の要素を検索できます。次の図は、List インターフェースのフレーム図です。

上記のフレーム図をわかりやすくするために、そのさまざまなクラスとインターフェイスは次のとおりです。

Collection: Collection階層内のルートインターフェース。これはオブジェクトのセットを表し、コレクションの要素とも呼ばれます。 Collection の場合、直接実装は提供されず、すべての実装はそのサブクラスの責任になります。

AbstractCollection: このインターフェイスの実装に必要な作業を最小限に抑えるために、Collection インターフェイスのバックボーン実装を提供します。不変コレクションを実装するには、このクラスを拡張し、イテレータおよびサイズメソッドの実装を提供するだけで済みます。ただし、変更可能なコレクションを実装するには、このクラスの add メソッドをオーバーライドする必要があります (オーバーライドしないと、UnsupportedOperationException がスローされます)。また、イテレーターメソッドによって返されるイテレーターも、その Remove メソッドを実装する必要があります。

テレータ: イテレータ。

ListIterator: プログラマがリストをどちらかの方向に走査し、反復中にリストを変更し、リスト内の反復子の現在位置を取得できるようにするシリーズリスト反復子。

List: Collectionのインターフェースを継承します。これは順序付けられたキューを表します。

AbstractList: 「ランダムアクセス」データストア (配列など) によってサポートされるこのインターフェイスの実装に必要な作業を最小限に抑えるための List インターフェイスのバックボーン実装。

キュー: キュー。キューの基本的な挿入、取得、および検査操作を提供します。

collectionコレクションの線形コレクションのDequeで、両端に挿入および削除されます。ほとんどの Deque 実装には、含めることができる要素の数に固定制限はありませんが、このインターフェイスは、容量制限のある Deque と固定サイズ制限のない Deque の両方をサポートします。

AbstractSequentialList:

List インターフェイスのバックボーン実装を提供し、リンクリストなどの「シーケンシャルアクセス」データストアによってサポートされるこのインターフェイスの実装に必要な労力を最小限に抑えます。ある意味、このクラスは、リストのリスト反復子に「ランダムアクセス」メソッドを実装するのと同じです。

LinkedList:

List インターフェースのリンクされたリスト実装。すべてのオプションのリスト操作を実装します。

ArrayList:

List インターフェースの可変サイズ配列の実装。すべてのオプションのリスト操作を実装し、null を含むすべての要素を許可します。このクラスは、List インターフェイスの実装に加えて、リストを格納するために内部で使用される配列のサイズを操作するメソッドも提供します。

Vector:

は拡張可能なオブジェクト配列を実装します。配列と同様に、整数インデックスを使用してアクセスできるコンポーネントが含まれています。

スタック:

後入れ先出し (LIFO) オブジェクトスタック。これは、ベクトルをスタックとして扱えるようにする 5 つの操作を備えたクラス Vector を拡張します。

Enumeration:

Enumeration は、このインターフェイスを実装するオブジェクトであり、一連の要素を一度に 1 つずつ生成します。 nextElement メソッドを継続的に呼び出すと、連続した要素のシーケンスが返されます。

2. 使用シナリオ

知識を学ぶ基本的な目的は、それを使用することです。

各ナレッジポイントには使用範囲があります。同じことがコレクションにも当てはまります。Java のコレクションファミリは非常に大きく、各メンバーには最適な使用シナリオがあります。私が初めて List に触れたとき、LZ は、「スタック」、「キュー」、「リンクリスト」などの操作が関係する場合は、List の使用を優先してくださいと言いました。どのListなのかというと、以下のように分かれています:

1. 要素を素早く挿入、削除する必要がある場合は、LinkedListを使用する必要があります。、 2 では、要素に素早くアクセスする必要があるため、ArrayList を使用する必要があります。 3 については、「シングルスレッド環境」または「マルチスレッド環境だが、List は 1 つのスレッドによってのみ操作される」場合は、非同期クラスのスレッド操作の使用を検討する必要があります。同期クラスの使用を検討してください。ベクターなど）。 R2.1ArrayList、LinkedList のパフォーマンス分析

List の中で最も一般的なのは LinkedList と ArrayList であると同時に、それらの使用シーンと違いについても理解します。

public class ListTest {
    private static final int COUNT = 100000;
    
    private static ArrayList arrayList = new ArrayList<>();
    private static LinkedList linkedList = new LinkedList<>();
    private static Vector vector = new Vector<>();
    
    public static void insertToList(List list){
        long startTime = System.currentTimeMillis();

        for(int i = 0 ; i < COUNT ; i++){
            list.add(0,i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("插入 " + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void deleteFromList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.remove(0);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("删除" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void readList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.get(i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("读取" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }

    private static String getName(List list) {
        String name = "";
        if(list instanceof ArrayList){
            name = "ArrayList";
        }
        else if(list instanceof LinkedList){
            name = "LinkedList";
        }
        else if(list instanceof Vector){
            name = "Vector";
        }
        return name;
    }
    
    public static void main(String[] args) {
        insertToList(arrayList);
        insertToList(linkedList);
        insertToList(vector);
        
        System.out.println("--------------------------------------");
        
        readList(arrayList);
        readList(linkedList);
        readList(vector);
        
        System.out.println("--------------------------------------");
        
        deleteFromList(arrayList);
        deleteFromList(linkedList);
        deleteFromList(vector);
    }
}

ログイン後にコピー

実行結果:

插入 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 < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

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下篇博客解释，当然不知道这个情况各位是否也遇到过？？