一, ArrayList 分析
1. 类和构造方法
- public class ArrayList<E> extends AbstractList<E> // 可以看到其父类是 AbstractList
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- {
- private static final long serialVersionUID = 8683452581122892189L;
- private static final int DEFAULT_CAPACITY = 10; // 默认数组长度
- // 用于空实例的共享空数组实例.
- private static final Object[] EMPTY_ELEMENTDATA = {}; // 底层是 Object 类型的数组
- // 共享空数组实例用于默认大小的空实例. 我们将其与 EMPTY_ELEMENTDATA 区别开来, 以便知道当添加第一个元素时膨胀多少.
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- // 存储 ArrayList 元素的数组缓冲区.
- //ArrayList 的容量是这个数组缓冲区的长度.
- // 当添加第一个元素时, 任何带有 elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将被扩展为 DEFAULT_CAPACITY.
- transient Object[] elementData; // 非私有以简化嵌套类访问
- private int size; // 数组内数据元素的个数
- public ArrayList(int initialCapacity) {
- // 我们在声明实例的时候可以指定容量大小, 若为 0 的话, 则使用 ELEMENTDATA 作为默认数组.
- if (initialCapacity> 0) {
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- }
- }
- public ArrayList() { // 若不指定容量大小, 则使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 作为默认数组
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- public ArrayList(Collection<? extends E> c) { // 也可以接收 Clooection 类型的变量, 把里面的元素拷贝到数组里面
- elementData = c.toArray();
- if ((size = elementData.length) != 0) {
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- } else {
- // replace with empty array.
- this.elementData = EMPTY_ELEMENTDATA;
- }
- }
- }
2.add() 方法
- public boolean add(E e) { // 在存入数据前, 先确保内部容量
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 默认容量 10 和当前容量取 max
- }
- ensureExplicitCapacity(minCapacity); // 校验当前容量是否符合要求容量
- }
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity); // 如果要求容量大于数组容量, 就扩容
- }
- 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); // 把旧数据拷贝到新数组里面
- }
二, Vector 分析 (线程安全的)
1. 类和构造方法
- public class Vector<E>
- extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- {
- protected Object[] elementData;
- protected int elementCount;
- protected int capacityIncrement;
- private static final long serialVersionUID = -2767605614048989439L;
- public Vector(int initialCapacity, int capacityIncrement) {
- super();
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- this.elementData = new Object[initialCapacity];
- this.capacityIncrement = capacityIncrement;
- }
- public Vector(int initialCapacity) {
- this(initialCapacity, 0);
- }
- public Vector() {
- this(10);
- }
- public Vector(Collection<? extends E> c) {
- elementData = c.toArray();
- elementCount = elementData.length;
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
- }
- }
2.add() 方法
- public synchronized boolean add(E e) {
- modCount++;
- ensureCapacityHelper(elementCount + 1); // 先校验容量
- elementData[elementCount++] = e;
- return true;
- }
- private void ensureCapacityHelper(int minCapacity) {
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity); // 扩容
- }
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + ((capacityIncrement> 0) ?
- capacityIncrement : oldCapacity);
- if (newCapacity - minCapacity <0)
- newCapacity = minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE> 0)
- newCapacity = hugeCapacity(minCapacity);
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity <0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity> MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
三, LinkedList
1. 类和构造方法
- public class LinkedList<E>
- extends AbstractSequentialList<E>
- implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- {
- transient int size = 0;
- transient Node<E> first; // 头结点
- transient Node<E> last; // 尾结点
- public LinkedList() {
- }
- public LinkedList(Collection<? extends E> c) {
- this();
- addAll(c);
- }
- 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;
- }
- }
- }
2.add() 方法
- public boolean add(E e) {//add 方法就是在链表的尾部加上一个结点
- linkLast(e);
- return true;
- }
- 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++;
- }
3.get() 方法
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
- private void checkElementIndex(int index) {
- if (!isElementIndex(index))
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
- Node<E> node(int index) {
- // assert isElementIndex(index);
- // 若索引在链表的前半部分, 就从前往后取; 否则从后往前取
- if (index <(size>> 1)) {
- Node<E> x = first;
- for (int i = 0; i <index; i++)
- x = x.next;
- return x;
- } else {
- Node<E> x = last;
- for (int i = size - 1; i> index; i--)
- x = x.prev;
- return x;
- }
- }
来源: http://www.bubuko.com/infodetail-2893258.html