java源码学习之List集合（一）

明天开始中秋节公司开始放假了。由于资金问题这个中秋节公司不发月饼了，没有福利。唉，毕竟是实习生，没有就没有吧。话说成都这边招实习生的公司好少啊，很多大一点的互联网公司在成都都不招，小的公司又喜欢从培训机构出来的可以直接上手的。感觉在学校学的计算机原理数据结构与算法一类的知识在面试中根本体现不出优势啊现在。之前遇到和我一起笔试的一个人，一道排序算法题我写了递归加一个快速排序算法别人直接一个调用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的实现之一是数组的实现方式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的查找一个元素的方法，通过遍历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扩容的一个方法，此方法最后将elementData复制到一个新的数组中并把值赋值给elementData。新数组的长度为newCapacity。数组的复制是一种效率很低的方法，所以我们要尽量避免这种情况。方法也保证了扩容后的容量不会小于当前数组的容量也不会大于数组的最大容量。由于数组实现的list大部分的增删查改操作都和数组类似，此处就不再赘述，只说下添加元素到默认位置和指定位置

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }<pre name="code" class="java">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> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

可以看出这是一个双向链表，每个节点Node包含了一个指向前一个节点的prev，指向下一个节点的next以及一个元素item。

我们最常使用的就是无参数的构造方法。LinkedList的无参构造方法没有具体的实现。另一个经常使用的方法是添加元素的add方法。

public boolean add(E e) { linkLast(e); return true; }<pre name="code" class="java">void linkLast(E e) { final Node<E> l = last; final Node<E> 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<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> 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）。如果node（index）之前没有节点，说明新添加的节点的位置是链表的第一个位置，就将first指向新节点。如果node（index）之前存在节点，就将节点的next指向新添加的节点。