ArayListとLinkdListのデータ構造の違い(jdk 1.8)

8293 ワード

JavaSE

まず、この二つのデータ構造を確認します.ソースコードの中でどのように定義され、実現されましたか?
ArayListソース解析:「ArayListソース分析(JDK 8ベース)」を参照.
Linked Listソース解析:「Linked Listソース分析(JDK 8ベース)」を参照してください.
いくつかのよくある方法の実現方法を抜粋しました.
ArayList
メンバー変数

//  AbstractList    ，     ArrayList       ，     
//protected transient int modCount = 0;

//        
private static final int DEFAULT_CAPACITY = 10;
//        
private static final Object[] EMPTY_ELEMENTDATA = {};
//      ，            ，            
//   EMPTY_ELEMENTDATA，                   。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//           ，          
transient Object[] elementData;
//       
private int size;
//       
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

作成方法

//    
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
//    ，elementData     1，size 0,      add   ,elementData       10

// int       
//initialCapacity           
public ArrayList(int initialCapacity) {
    //            0，            
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //    0，    
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}

方法
add(E e)
(以下は私が整理したものです.呼出方法を一つの中に書きました.)
1)配列がすでに使用されていることを確保し、1を加えた後、次のデータ2を十分記憶する.修正回数modCountは増分1を識別し、現在の配列が使用されている場合、1を加算した後、現在の配列の長さを従来の容量の1.5倍(配列のコピー)3)とする.新規データがローカルに保存されていることを確保した後、新しい要素をsizeの位置に追加します.

public boolean add(E e) {
    int minCapacity = size + 1;
    //            ，           this.size +1   1，              elementData       10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //    （modCount）  1
    modCount++;
    //            
    //           （size） 1           
    //                1.5 
    if (minCapacity - elementData.length > 0){
        int arg1 = this.elementData.length;
        int arg2 = arg1 + (arg1 >> 1);
        if (arg2 - arg0 < 0) {
            arg2 = arg0;
        }
        if (arg2 - 2147483639 > 0) {
            arg2 = hugeCapacity(arg0);
        }
        this.elementData = Arrays.copyOf(this.elementData, arg2);
    }

    elementData[size++] = e;
    return true;
}

get
指定された位置の要素を返します.

public E get(int index) {
    rangeCheck(index);
    //    modCount，        
    checkForComodification();
    return ArrayList.this.elementData(offset + index);
}

セット
setの位置が現在の配列の長さより小さく、かつ0より大きいことを確認し、指定された位置(index)要素を取得し、次にoldValueに保存し、設定が必要な要素を指定された位置(index)に置いて、元の位置の要素oldValueを使用者に返す.

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

remove
インデックスで削除
1.インデックスが境界を越えていると判断し、修正回数を増やしてから、
2.索引の要素を見つけてoldValueに保存する(戻りやすい);
3.索引の後の要素を前の方に移動し、最後の索引を空にして、GCの回収に便利です.

    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;
    }

オブジェクトごとに削除
1.すべてのオブジェクトを巡回して、オブジェクトがある索引の位置indexを取得します.
2.fastRemoveを呼び出す方法:まずindexの後ろの要素を前に移動して、最後の要素を空にします.

    public void 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;
    }

Linked List
ArayListとは異なるクラスとインターフェースを継承または実現することで、AbstractSequentialListを継承し、Dequeインターフェースを実現することができます.双方向のキューです.
メンバー変数

//    
transient int size = 0;
//     
transient Node first;
//      
transient Node last;

その内部にはもう一つのheader属性があり、開始位置、first、lastがheaderを指すので、双方向のチェーン構造が形成されている.
作成方法

//    
public LinkedList() {}

方法
add(E e)
追加の要素をチェーンの一番後ろに置いて、チェーンの長さを1を加えて、修正の回数を1を加えます.

public boolean add(E e) {
    linkLast(e);
    return true;
}
    //         
    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

add(int index,E element)
位置指定(インデックスindex)を配列チェーンに要素を追加します.
1.indexが現在の長さチェーンのsizeより小さいかどうかを確認し、0より大きい必要があります.
2.indexがsizeに等しい場合、直接チェーンの一番後ろに要素を追加して、add(E e)メソッドを呼び出すのに相当します.indexインデックスを先に見つけて、indexの位置の前に新しい要素を追加します.
get
1.インデックスが境界を越えると判断する
2.チェーンの要素を巡回します.最初から巡回するかそれとも最後から巡回するかを判断します.インデックスの位置を現在のチェーンの長さの半分と比較します.インデックスの位置が現在のチェーンの長さの半分以下であれば、最初からやり直します.さもなければ、最後から巡回します.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
    //          （ null）  。
    //      
    Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

セット
インデックスが境界線を越えていることを確認し、index位置のノードコンテンツを新しいコンテンツelementに置き換え、古い値を返します.

public E set(int index, E element) {
    checkElementIndex(index);
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

remove
removeメソッドで呼び出すremoveFirst()

public E remove() {return removeFirst();}

removeFirst
第1のノードを削除して、第1のノードを空にして、次のノードを第1のノードに変えて、チェーンテーブルの長さを1減らして、修正回数を1加えて、削除した第1のノードを返します.

    public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

締め括りをつける
上からこれらの2つのデータ構造の実現方法とデータに対する操作方法の違いを示した.
1.ArayListは動的配列に基づくデータ構造であり、データは同じアドレス値にある.Linked Listは、リストを実現するデータ構造に基づいており、各データにはそれぞれのノードアドレス(Node)があります.
2.データ操作
2.1クエリ
ソースコードの中で、ArayListのget(int index)メソッドは直接配列のインデックスクエリを位置指定します.Linked Listのget(int index)は、インデックスを現在のチェーンの長さの半分と比較し、インデックスは現在のチェーンの長さの半分より小さいです.だから、ArayListの速度はLinked Listより優れています.
(ArayListはRandomAccessインターフェースを実現し、二分検索法を用いて、ランダムアクセスポリシーを使用する)
2.2追加(同理削除)
ArayListは要素を追加するために、拡張が必要かどうかを判断する必要があります(初期容量は10)、必要ならば、元の容量の1.5倍の拡張容量、拡張方式は配列のコピーで、ある程度のオーバーヘッドがあります.さらに、配列中の要素の変位に対して、add(E e)方法は最後まで挿入され、シフトは不要である.add(int index,E e)メソッドは、指定されたインデックスに挿入する方法であり、位置が前に近づくほど、シフト要素が多くなり、オーバヘッドが大きいほど、逆に挿入位置が後に近づくほど、オーバーヘッドが小さくなります.
Linked Listは、ヘッダと末尾のノードをマークするので、追加的に、ヘッダと末尾に要素を追加する方法が提供され、その中間にデータオーバーヘッドを挿入するのは固定されている.
2.3変更/更新
ArayListは、対応する配列のインデックスを見つけて更新するだけである.
Linked Listは、すべてのノードを巡回し、対応するインデックス修正後、ポインタを新しいデータに向けたインデックスを修正する必要があります.
2.4選択
集合の中の要素を頻繁に読み取る必要がある場合は、ArayListを使用するのが効率的であるが、挿入と削除の操作が多い場合は、LinkdListを使用するのが効率的である.

【データ構造---21】スタックでキューの操作を行う