ArayListとLinkdListの底辺実現と比較


よくある面接問題:
ArayListとLinkdListの違い
  • ArayListは、動的配列に基づくデータ構造を実現するものであり、リンクベースのデータ構造
  • は、ランダムアクセスgetおよびsetに対して、ArayListはLinked Listより優れています.ArayListはランダムに位置決めできるので、LinkdListはポインタを移動してノードに一歩ずつ移動します.(例として、ArayListの底辺は動的配列であり、対象としてLinkdListはチェーンであり、多くの対象と関連しているので、検索すると配列が速くなります.Linkedに対しては多くのオブジェクトと繋がっています.検索する時、彼らを全部調べてください.この時は性能と時間から、linkedListはArayList 18792に及ばないです.)
  • は、操作addとremoveの追加と削除に対して、LindeListが有利であり、ポインタを修正するだけでよい.一方、ArayListはデータを移動して、削除されたオブジェクトの空間をカバーする.
    ArayListの底辺実現
    public class ArrayList extends AbstractList
    ArayListの父類はAbstractList類で、具体的な父類とインターフェースの関係は、HashMapの詳細解の中に集合類の関係図があります.
    まず、ArayListのデータ構造を見てみます.
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;
    ArayListのデータ構造
    ArayListは2つの重要な属性:elementaとsizeを含む.
  • size
  • ArayListに含まれる要素の個数.
  • element Data
  • (1)Object配列(つまり、ArayListの最下層は配列)ですので、ArayListは基本データを入れられません.
    (2)tranientを使って修正します.tranientで具体的な変数を宣言すると、オブジェクトが格納されているときの値は維持されません.つまり、tranientキーワードでマークされているメンバー変数は、プログレッシブプロセスに参加しません.しかし、実際の転送過程では、行列の要素が得られます.これはどのように実現されますか?なぜですか?tranientで修飾しますか?まずアラーリストの構造関数が拡大されている原理を見てみます.
    ArayListの容量
    ArayListは2つのコンストラクション、public ArayList()とpublic ArayList(int initial Capacity)があります.
        /**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
        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);
            }
        }
    
        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    上記のソースコードの通りです.
    ArayList()のデフォルトcapacityは10であり、ArayList(int initial Capacity)のcapacityはinitial Capacityである.
    PS:sizeは配列中の記憶要素の個数であり、capacityは配列の容量である.
    ArayListのAdd
        /**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return true (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    ArayListは要素を添加する時、まずensureCapacityInternal(size+1)の操作を行います.すなわちcapacityとsize+1の大きさを判断します.capacity>1)、つまり1.5倍の配列に拡大して、元の元素を新しい配列にコピーします.コードは以下の通りです.
        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);
        }
    elementData    transient  
    前にこの疑問を残しました.今はやっと解けます.
    上で知っていますが、capacityはsize以上で、ほとんどの場合はsizeより大きいです.したがって、直接的にelement Data配列を導入すると、要素の空間が浪費されます.特にcapacity-sizeが非常に大きい場合、このような浪費は非常に不採算です.では、elementeDataはシリアルナンバーには含まれません.時又に送るにはどうやって読みますか?ArayListは、writeObject(java.io.Object Output Stream s)とreadObject(java.io.Object Input Stream)の方法を実現した.この二つの方法の役割は具体的には何がWriteObjectとreadObjectですか?カスタマイズ可能なプログレッシブプロセス.
    /**
         * Save the state of the ArrayList instance to a stream (that
         * is, serialize it).
         *
         * @serialData The length of the array backing the ArrayList
         *             instance is emitted (int), followed by all of its elements
         *             (each an Object) in the proper order.
         */
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out size as capacity for behavioural compatibility with clone()
            s.writeInt(size);
    
            // Write out all elements in the proper order.
            for (int i=0; iArrayList instance from a stream (that is,
         * deserialize it).
         */
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            elementData = EMPTY_ELEMENTDATA;
    
            // Read in size, and any hidden stuff
            s.defaultReadObject();
    
            // Read in capacity
            s.readInt(); // ignored
    
            if (size > 0) {
                // be like clone(), allocate array based upon size not capacity
                ensureCapacityInternal(size);
    
                Object[] a = elementData;
                // Read in all elements in the proper order.
                for (int i=0; i
    ArayListのremove操作
            public E remove(int index) {
                rangeCheck(index);
                checkForComodification();
                E result = parent.remove(parentOffset + index);
                this.modCount = parent.modCount;
                this.size--;
                return result;
            }
    上のソースコードのように、ArayListのソースコードは、sizeの値を変更するだけで、自動的にcapacityの値を変更することはありませんが、ARrayListはtrimToSizeを提供しています.
        public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }
    他の方法はArayListの話をするのがおっくうです.
     
    Linked List
    public class LinkedList
        extends AbstractSequentialList
        implements List, Deque, Cloneable, java.io.Serializable
    その父の関係は具体的にはやはり私がHashMapで詳しく説明している中に集合類の関係図があります.
     
    Linked Listのデータ構造
        transient int size = 0;
    
        transient Node first;
    
        transient Node last;
    上のソースコードのように、Linked Listの下の実装は双方向のチェーンです.
    Linked ListのAdd操作
    Linked Listは、3つの要素を追加する方法を提供する.
    public void addFirst(E e);
    
    public void addLast(E e);
    
    public boolean add(E e);
      ,add            :
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    Linked Listは下付きで元素を取得します.
        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    
        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;
            }
        }
    他には特に何もありません.