ArrayList 源码阅读和LinkedList源码阅读 比较笔记

基于jdk 1.8 ArrayList 源码 和 LinkedList 源码

ArrayList 的底层结构是数组的存储结构 LinkedList是基于链表的存储结构 他们都是线程不安全的集合

构造方法的比较

ArrayList的源码

// 这种构造在initialCapacity 大于0 的时候回直接初始化,说明底层的存储结构是数组，查询根据下标进行索引很快 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; //private static final Object[] EMPTY_ELEMENTDATA = {} } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //没有指定容器的大小，默认为空数组，懒加载模式 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; } public ArrayList(Collection<? extends E> c) { 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; } }

LinkedList 的源码

//成员变量 头结点 transient Node<E> first; //成员变量 尾结点 transient Node<E> last; public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c);//将别的集合的内容添加到当前的list中 } //线程不安全 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //说明底层的结构是链表的形式 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index);//检查 index 的合法性 Object[] a = c.toArray();//先转换成数组 int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index);//使用循环 找到对应下标的节点 pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode;// transient Node<E> first;成员变量 else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //关于节点的类 可以看出LinkedList是一个双向的链表 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; } }

小结：

ArraList 底层的存储结构是数组，当没有指定容器的大小的时候，默认的数组是一个空的数组。类似于懒加载的模式，只有在用到的时候才会去初始化数组容器。如果创建List的时候指定容器的大小那么就会创建指定打下的数组，如果传进一个集合，那么数组的大小就是集合内元素数量的大小。可以确认的是这种结构通过下标获取元素的速度是最快的，但是对于数组的扩容和插入就比较慢LinkedList 通过构造方法可以知道，底层是使用双向链表的存储结构来存储数据的，List对象的内部保存了头尾结点。这种结构存储数据会发现获取指定的下标的速度相对于ArrayList【O（1）】是比较慢的，每次寻找基本需要遍历一次，但是相对而言，插入的速度是比较快的，只需要更改一下引用的地址就好了。也没有扩容的限制

增删方法的比较

ArrayList 的源码

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) { //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // private static final int DEFAULT_CAPACITY = 10; } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);//扩容，elementData已经不够存放了 } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组的大小是原数组的1.5倍，即扩大0.5倍，正常的情况下 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);//创建一个新数组并复制内容 } //说明数组length最大是Integer.MAX_VALUE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //指定位置插入值 public void add(int index, E element) { rangeCheckForAdd(index);//index 的范围检查，检查是否正常 ensureCapacityInternal(size + 1); // Increments modCount!! //需要移动数组的内容 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } 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; } //直接根据下标索引 public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); }

LinkedList的源码

public boolean add(E e) { 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++; } //基于链表的形式会发现增加和删除都是比较快的操作 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } // 通过索引获取基本是遍历获取了 public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } //------------下面是一些关于队列的操作方法------ //返回第一个元素，不移除 public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //也是返回第一个元素，不移除，但是链表为空时，会抛异常 public E element() { return getFirst(); } public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } // 弹出第一个元素，并移除 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //添加 还有很多就不一一介绍了，后面可能会有相关的的博客会详细说 public boolean offer(E e) { return add(e); }

小结

ArrayList 每次扩容是上次容量的1.5倍，最大是int的最大值。list根据下标来查找数据是比较快的，但是增加和删除数据是比较慢的，所以如果是数据只是用于频繁的读话，用ArrayList是比较好的选择。还有创建数组的时候如果大概知道需要存放的数量最好先赋值，这样能减少频繁扩容的操作。在使用对指定的下标的数据进行操作的时候，最好先确认容器内元素的数量，不然是会抛异常的，并且这是线程不安全的集合。Vertor虽然是线程安全，但是基本都是方法级别上（指的是在方法上加synchronized）。（后面会继续出线程安全的集合操作的源码阅读，比如CopyOnWriteArrayList）最后一点可以存储nullLinkedList 本质上来说是容量是没有上限的，因为是双向链表，所以可以一直添加下去，并且对于添加的和删除的操作相对list来说是很快的，只需要修改一下引用就好。但是对于查询就是灾难了，如果链表比较长，而又是遍历的去查找…，最后linkedList 也是线程不安全的list 也可以存储null，linkedList还是一个队列