多线程与高并发集合中咱们了解了集合，但是只了解了存在哪些集合，以及BlockingQueue的使用，今天来完善下ArrayList和LinkedList底层是如何实现的。
多线程和高并发_集合了解ArrayList和LinkedList之前咱们先看下他们的类图
publicstaticvoidmain (字符串[ ] args ) ) listobjectarraylist=new ArrayList )； linkedlistobjectlinkedlist=new linked list (； Arraylist.add(1； Arraylist.get(1； Arraylist.remove(1； 链接列表. add (1； 链接列表. get (1； 链接列表. add first (1； 链接列表. add last (1； linkedList.removeFirst (； linkedList.removeLast (； } 优缺点
ArrayList :下面实现了Object数组。 我们知道数组的大小是固定的，并且是规则分布的。 线程不安全、查询快、添加删除慢，扩展需要重新申请空间并复制对象。 LinkedList :基础是使用双向链表结构实现的，链表只保留对对象的引用，而不需要保留大小。 线程不安全、删除快、查询慢，不需要扩展操作。 源代码ArrayList成员//默认数组空间大小privatestaticfinalintdefault _ capacity=10； //数组中的元素数private int size； //修改次数protectedtransientintmodcount=0； //数组容器传递对象[ ] element data； 保证add(e )方法//元素publicbooleanadd )//数组容器适合元素ensurecapacityinternal(size1)； //将数组元素个数的下标添加到元素elementData[size ]=e； 返回真； } ensurecapacityinternal (int min capacity )方法privatevoidensurecapacityinternal (int min capacity ) /若要首先添加元素，请使用数组大小if (eeef ) (minCapacity=math.max ) default_capacity，mincapacity //确保序列容量ensureexplicitcapacity (mincapacity )； } ensurecapacityinternal (int min capacity )方法privatevoidensureexplicitcapacity (int min capacity ) /修改次数1 modCount； //在原始容器中安装if (mincapacity-element data.length0)//扩展grow (mincapacity )； ) grow(mincapacity )方法//由此可见，添加元素时可能涉及扩展，扩展时需要申请内存，数组元素privatevoidgrow(intmincapacity )//移动求出数组中的最大容量intoldcapacity=elecation如果新容量为10，则新数组的长度为15，实际上增加了50%容量的intewcapacity=old capacity (old capacity ) 新容量-最大容量(if )新容量=最大容量； if(newcapacity-MAX_ARRAY_SIZE0) /最大容量max_array_size和Integer.MAX_VALUE之间的new capacity=huge capacity (malacity ) } get (索引)方法检查公共eget (索引)//下标语言检查(索引)； //直接返回与下标对应的元素returnelementdata(index )的}remove(intindex )方法
插入排序
//删除元素public E remove(int index) {//检查下标 rangeCheck(index);//修改数据 modCount++; //先获取到对应下标的元素 E oldValue = elementData(index);//找到删除元素后面的元素 int numMoved = size - index - 1; //从这里可以看出，删除的时候很慢，需要移动数组元素，最好O1，最坏O(n-1) //如果后面有元素 if (numMoved > 0) //把后面的元素向前移一位<类似插入排序的思想，有不了解插入排序的伙伴可以百度下或者博主前面文章有插入排序> System.arraycopy(elementData, index+1, elementData, index,numMoved); //删除最后一位的引用，help gc elementData[--size] = null;//返回删除后的元素 return oldValue;} iterator()方法 //获取迭代器public Iterator<E> iterator() { return new Itr();}//ArrayList.Itr实现了Iterater接口private class Itr implements Iterator<E> {//下一个元素下标 int cursor; //返回元素的下标 int lastRet = -1; //为了判断防止多线程操作 int expectedModCount = modCount; Itr() {}//判断是否有下一个元素，用当前遍历到的元素与元素的个数进行比较 public boolean hasNext() { return cursor != size; }//获取当前元素 完全由cursor和lastRet成员控制 @SuppressWarnings("unchecked") public E next() { //判断modCount和expectedModCount是否一致，不一致说明存在别的线程更新list，这里明确的告诉了我们，ArrayList不支持多线程 checkForComodification(); //获取到初始位置，默认从第一个元素开始遍历 int i = cursor; //判断是否下标越界 if (i >= size) throw new NoSuchElementException(); //获取到容器数组 Object[] elementData = ArrayList.this.elementData; //当前游标不能大于等于数组长度，这种情况也是只有多想称情况才能出现 if (i >= elementData.length) throw new ConcurrentModificationException(); //对下一个元素的下标+1操作 cursor = i + 1; //返回元素并且把原来的游标赋值给lastRet return (E) elementData[lastRet = i]; }//迭代器中删除元素 public void remove() { //验证最后一次返回的元素，从这里可以看出，咱们删除元素之前最好显示的调用next()方法 if (lastRet < 0) throw new IllegalStateException(); //检查是否有多线程参与 checkForComodification(); try { //调用ArrayList删除方法 ArrayList.this.remove(lastRet); //删除元素后把游标放到删除的元素位置 cursor = lastRet; //？？？？？这里不明白为什么要设置成-1，lastRet对next方法无影响 lastRet = -1; //重置expectedModCount expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }} LinkedList大家有兴趣的可以看看ArrayDeque源码，底层使用数组实现。咱们今天就不过赘述了
成员LinkedList设计巧妙的地方是维护了元素的个数，记录了头尾节点
//记录元素个数transient int size = 0;//头节点transient Node<E> first;//尾节点transient Node<E> last;//记录修改的次数protected transient int modCount = 0;//节点对象 双向链表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; }} addFirst(E e) //向链表头部插入元素public void addFirst(E e) { linkFirst(e);} linkFirst(e) private void linkFirst(E e) {//获取到头节点 final Node<E> f = first; //创建一个新节点，pre=null、next=f final Node<E> newNode = new Node<>(null, e, f); //把最新添加的Node节点设置为头节点 first = newNode; //这里就比较有意思了，它把一个链表切分成两份，减少根据索引查找的时间复杂度 //如果头节点为null if (f == null) //尾节点也设置成新增加的Node节点，从这里可以看出，删除的时候一样也会有类似的操作，咱们继续向下看 //这样头尾节点就能连接起来了 last = newNode; else //头节点不为null正常添加元素，把old first的prev引用设置为newNode f.prev = newNode; //元素个数+1 size++; //修改次数+1 modCount++;} addLast(E e) //向尾部添加元素public void addLast(E e) { linkLast(e);} linkLast(e) void linkLast(E e) {//得到尾节点 final Node<E> l = last; //创建新节点 final Node<E> newNode = new Node<>(l, e, null); //把新节点设置为尾节点 last = newNode; //如果原来的尾节点为null if (l == null) //把新节点也设置为头节点 first = newNode; else //不为null正常增加新节点到尾节点 l.next = newNode; //元素+1 size++; //修改次数+1 modCount++;} removeFirst() //删除头部元素public E removeFirst() { final Node<E> f = first; //如果头节点为null，那么尾节点一定为null if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);} unlinkFirst(Node f) private E unlinkFirst(Node<E> f) { //得到当前元素，用于返回 final E element = f.item; //找到下一节点 final Node<E> next = f.next; //解开引用 help GC f.item = null; f.next = null; //下一个节点升级为头节点 first = next; if (next == null) //如果下一个节点为null，说明first = last last = null; else //断开引用 next.prev = null; //元素-1 size--; //修改+1 modCount++; //返回删除的元素 return element;} unlinkFirst(Node f) //删除尾节点public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l);} unlinkFirst(Node f) private E unlinkLast(Node<E> l) {//获取当前元素 final E element = l.item; //得到前置节点 final Node<E> prev = l.prev; //解引用 l.item = null; l.prev = null; //前置节点升级为尾节点 last = prev; if (prev == null) //如果前置节点为null，头节点一定为null first = null; else //断开引用 prev.next = null; //元素个数-1 size--; //修改次数+1 modCount++; //返回删除的元素 return element;}getLast()和pollLast()有兴趣的自己看下吧，这两个方法上面都有了解
好了，今天的分享就到这里了，对文章敢兴趣的加加关注啦～～～