JAvaソース学習のリスト集合(一)

明日から中秋節に会社が休みになります.資金問題でこの中秋節会社は月餅を出さないので、福祉がありません.ああ、実習生だから、なければないでしょう.成都の方は実习生を募集する会社が少ないですね.多くの大きいインターネット会社は成都では募集していません.小さい会社は训练机関から出てくるのが好きです.学校で学んだコンピューターの原理データの構造とアルゴリズムのような知識は面接では優位性を体現できないような気がします.前に私と一緒に筆記試験をした人に出会って、1つのソートアルゴリズムの問題は私が再帰的に1つの高速ソートアルゴリズムをプラスして他の人が直接sort方法を呼び出すことを書いてokに行きました.

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

Listの実装の1つは配列の実装方式ArryListであり,この実装方式も配列と同様に挿入削除効率が低くクエリーデータ効率が高い.まず構造方法であり,初期配列の容量を指定してもよいし,指定しなくてもよい.次に、Object配列を作成します.

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

これはlistの1つの要素を検索する方法で、ArryList要素を遍歴して検索する要素とequalsを比較することで、結果がtrueであれば配列の下付きを返します.検索された要素がnullの場合.すると、最初の配列の空の位置の下付きラベルが検索されます.

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

これはArryList拡張の1つの方法であり、この方法は最後にelementDataを新しい配列にコピーし、elementDataに値を付与する.新しい配列の長さはnewCapacityです.配列のレプリケーションは効率の低い方法なので、できるだけ避ける必要があります.方法はまた、拡張後の容量が現在の配列の容量よりも小さくなく、配列の最大容量よりも大きくないことを保証する.配列実装のlistの大部分の削除変更操作は配列と類似しているため、ここでは後述せず、デフォルトの位置と指定された位置に要素を追加する

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
  
 
               1   ，      length          。              ，        。                 。  arrycopy            。               1                                         。                     。 ArryList                ，                    。             。 
   
  
 
  
          ，       ，   。LinkedList                   ，            ，             。LinkedList             。       List e=new LinkedList();         。            Node
 
  
    private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  
これは   チェーンテーブルであり、 ノードノードNodeは のノードを すprev、 のノードを すnext、および  itemを むことがわかる.
 たちが もよく うのはパラメータのない    です.LinkedListの パラメトリック    は   には  されていない.もう1つのよく われる  は、  を  するadd  です.
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     linkLast  ，         boolean true。   linkLast last        l，            e，  prev           last，   last      newNode。  l  ，  last  ，    ，           ，  first   newNode。  l   ，last                 ，           l next  newNode            。 
   
  
 
  
public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
  
void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
  
ノードを  する  を  した  、  の にチェーンテーブルのサイズが しい  は、  したチェーンテーブルの  にノードを  する  を び し、 しくない  はlinkBefore  を び します.  するノードの  の のノードnode(index)を つけ、node(index)すなわちsuccのprevで    の のノードを つけ、 しく  したノードのprevをnode(index)の のノードに、 しいノードのnextをnode(index)に けるのが  です.ノード(index)の にノードがない  、 しく  したノードの  がチェーンテーブルの  の  であることを すと、firstは しいノードを します.ノード(index)の にノードが  する  は、ノードのnextを しく  したノードに します.