ArrayList

LinkedList

构造方法

  1.     //集合元素数量
  2.     transient int size = 0;
  3.     //链表头节点
  4.     transient Node<E> first;
  5.     //链表尾节点
  6.     transient Node<E> last;
  7.     //啥都不干
  8.     public LinkedList() {
  9.     }
  10.     //调用public boolean addAll(Collection<? extends E> c)  将集合c所有元素插入链表中
  11.     public LinkedList(Collection<? extends E> c) {
  12.         this();
  13.         addAll(c);
  14.     }

节点Node结构

  1.   private static class Node<E> {
  2.         E item;//元素值
  3.         Node<E> next;//后置节点
  4.         Node<E> prev;//前置节点
  6.         Node(Node<E> prev, E element, Node<E> next) {
  7.             this.item = element;
  8.             this.next = next;
  9.             this.prev = prev;
  10.         }
  11.     }

addAll()

  1. //addAll ,在尾部批量增加
  2. public boolean addAll(Collection<? extends E> c) {
  3.     return addAll(size, c);//以size为插入下标，插入集合c中所有元素
  4. }
  5. //以index为插入下标，插入集合c中所有元素
  6. public boolean addAll(int index, Collection<? extends E> c) {
  7.     checkPositionIndex(index);//检查越界 [0,size] 闭区间
  9.     Object[] a = c.toArray();//拿到目标集合数组
  10.     int numNew = a.length;//新增元素的数量
  11.     if (numNew == 0)//如果新增元素数量为0，则不增加，并返回false
  12.         return false;
  14.     Node<E> pred, succ;  //index节点的前置节点，后置节点
  15.     if (index == size) { //在链表尾部追加数据
  16.         succ = null;  //size节点（队尾）的后置节点一定是null
  17.         pred = last;//前置节点是队尾
  18.     } else {
  19.         succ = node(index);//取出index节点，作为后置节点
  20.         pred = succ.prev; //前置节点是，index节点的前一个节点
  21.     }
  22.     //链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。
  23.     //对比ArrayList是通过System.arraycopy完成批量增加的
  24.     for (Object o : a) {//遍历要添加的节点
  25.         @SuppressWarnings("unchecked") E e = (E) o;
  26.         Node<E> newNode = new Node<>(pred, e, null);//以前置节点 和 元素值e，构建new一个新节点，
  27.         if (pred == null) //如果前置节点是空，说明是头结点
  28.             first = newNode;
  29.         else//否则 前置节点的后置节点设置为新节点
  30.             pred.next = newNode;
  31.         pred = newNode;//步进，当前的节点为前置节点了，为下次添加节点做准备
  32.     }
  34.     if (succ == null) {//循环结束后，判断，如果后置节点是null。 说明此时是在队尾append的。
  35.         last = pred; //则设置尾节点
  36.     } else {
  37.         pred.next = succ; // 否则是在队中插入的节点 ，更新前置节点 后置节点
  38.         succ.prev = pred; //更新后置节点的前置节点
  39.     }
  41.     size += numNew;  // 修改数量size
  42.     modCount++;  //修改modCount
  43.     return true;
  44. }
  45. //根据index 查询出Node，
  46. Node<E> node(int index) {
  47.     // assert isElementIndex(index);
  48. //通过下标获取某个node 的时候，（增、查 ），会根据index处于前半段还是后半段 
  49.     //进行一个折半，以提升查询效率
  50.     if (index < (size >> 1)) {
  51.         Node<E> x = first;
  52.         for (int i = 0; i < index; i++)
  53.             x = x.next;
  54.         return x;
  55.     } else {
  56.         Node<E> x = last;
  57.         for (int i = size - 1; i > index; i--)
  58.             x = x.prev;
  59.         return x;
  60.     }
  61. }
  63. private void checkPositionIndex(int index) {
  64.     if (!isPositionIndex(index))
  65.         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  66. }
  67. private boolean isPositionIndex(int index) {
  68.     return index >= 0 && index <= size;  //插入时的检查，下标可以是size [0,size]
  69. }

add()

  1. //在尾部插入一个节点： add
  2. public boolean add(E e) {
  3.     linkLast(e);
  4.     return true;
  5. }
  7. //生成新节点 并插入到 链表尾部， 更新 last/first 节点。
  8. void linkLast(E e) { 
  9.     final Node<E> l = last; //记录原尾部节点
  10.     final Node<E> newNode = new Node<>(l, e, null);//以原尾部节点为新节点的前置节点
  11.     last = newNode;//更新尾部节点
  12.     if (l == null)//若原链表为空链表，需要额外更新头结点
  13.         first = newNode;
  14.     else//否则更新原尾节点的后置节点为现在的尾节点（新节点）
  15.         l.next = newNode;
  16.     size++;//修改size
  17.     modCount++;//修改modCount
  18. }

add(int index,E element)

  1.   //在指定下标，index处，插入一个节点
  2.     public void add(int index, E element) {
  3.         checkPositionIndex(index);//检查下标是否越界[0,size]
  4.         if (index == size)//在尾节点后插入
  5.             linkLast(element);
  6.         else//在中间插入
  7.             linkBefore(element, node(index));
  8.     }
  9.     //在succ节点前，插入一个新节点e
  10.     void linkBefore(E e, Node<E> succ) {
  11.         // assert succ != null;
  12.         //保存后置节点的前置节点
  13.         final Node<E> pred = succ.prev;
  14.         //以前置和后置节点和元素值e 构建一个新节点
  15.         final Node<E> newNode = new Node<>(pred, e, succ);
  16.         //新节点new是原节点succ的前置节点
  17.         succ.prev = newNode;
  18.         if (pred == null)//如果之前的前置节点是空，说明succ是原头结点。所以新节点是现在的头结点
  19.             first = newNode;
  20.         else//否则构建前置节点的后置节点为new
  21.             pred.next = newNode;
  22.         size++;//修改数量
  23.         modCount++;//修改modCount
  24.     }

remove(int index)

unlink(Node x)

  1.  //将节点x，从链表中删除
  2.     E unlink(Node<E> x) {
  3.         // assert x != null;
  4.         final E element = x.item;//记录元素值，供返回
  5.         final Node<E> next = x.next;//保存当前节点的后置节点
  6.         final Node<E> prev = x.prev;//前置节点
  8.         if (prev == null) {//前置节点为null，
  9.             first = next;//则首节点为next
  10.         } else {//否则 更新前置节点的后置节点
  11.             prev.next = next;
  12.             x.prev = null;//记得将要删除节点的前置节点置null
  13.         }
  14.         //如果后置节点为null，说明是尾节点
  15.         if (next == null) {
  16.             last = prev;
  17.         } else {//否则更新 后置节点的前置节点
  18.             next.prev = prev;
  19.             x.next = null;//记得删除节点的后置节点为null
  20.         }
  21.         //将删除节点的元素值置null，以便GC
  22.         x.item = null;
  23.         size--;//修改size
  24.         modCount++;//修改modCount
  25.         return element;//返回删除的元素值
  26.     }

CopyOnWriteArrayList

CopyOnWriteArrayList是ArrayList的线程安全版本，从他的名字可以推测，CopyOnWriteArrayList是在有写操作的时候会copy一份数据，然后写完再设置成新的数据。
CopyOnWriteArrayList适用于读多写少的并发场景，CopyOnWriteArraySet是线程安全版本的Set实现，它的内部通过一个CopyOnWriteArrayList来代理读写等操作，使得CopyOnWriteArraySet表现出了和CopyOnWriteArrayList一致的并发行为，他们的区别在于数据结构模型的不同，set不允许多个相同的元素插入容器中。

成员属性

  1.      /** The lock protecting all mutators */
  2.     final transient ReentrantLock lock = new ReentrantLock();
  4.     /** The array, accessed only via getArray/setArray. */
  5.     private transient volatile Object[] array;

add()

  1.    public boolean add(E e) {
  2.         final ReentrantLock lock = this.lock;
  3.         lock.lock(); //上锁，只允许一个线程进入
  4.         try {
  5.             Object[] elements = getArray(); // 获得当前数组对象
  6.             int len = elements.length;
  7.             Object[] newElements = Arrays.copyOf(elements, len + 1);//拷贝到一个新的数组中
  8.             newElements[len] = e;//插入数据元素
  9.             setArray(newElements);//将新的数组对象设置回去
  10.             return true;
  11.         } finally {
  12.             lock.unlock();//释放锁
  13.         }
  14.     }

add(int index, E element)

  1.   public void add(int index, E element) {
  2.         final ReentrantLock lock = this.lock;
  3.         lock.lock();
  4.         try {
  5.             Object[] elements = getArray();
  6.             int len = elements.length;
  7.             if (index > len || index < 0)
  8.                 throw new IndexOutOfBoundsException("Index: "+index+
  9.                                                     ", Size: "+len);
  10.             Object[] newElements;
  11.             int numMoved = len - index;
  12.             if (numMoved == 0)
  13.                 newElements = Arrays.copyOf(elements, len + 1);
  14.             else {
  15.                 newElements = new Object[len + 1];
  16.                 System.arraycopy(elements, 0, newElements, 0, index);
  17.                 System.arraycopy(elements, index, newElements, index + 1,
  18.                                  numMoved);
  19.             }
  20.             newElements[index] = element;
  21.             setArray(newElements);
  22.         } finally {
  23.             lock.unlock();
  24.         }
  25.     }

ConcurrentSkipList

多线程并发存取数据并且保证数据有序。

ConcurrentSkipListMap的数据结构：
image.png
图示

  2. public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> implements 
  3.     ConcurrentNavigableMap<K,V>,Cloneable,java.io.Serializable {
  4.    /**  Special value used to identify base-level header*/
  5.    private static final Object BASE_HEADER = new Object();//该值用于标记数据节点的头结点
  7.     /** The topmost head index of the skiplist.*/
  8.     private transient volatile HeadIndex<K,V> head;//最高级别索引的索引头
  9.     ......
  10.     /** Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes. 
  11.      The list is headed by a dummy node accessible as head.node. The value field is declared only as Object because it 
  12.      takes special non-V values for marker and header nodes. */
  13.     static final class Node<K,V> {//保存键值对的数据节点，并且是有序的单链表。
  14.         final K key;
  15.         volatile Object value;
  16.         volatile Node<K,V> next;//后继数据节点
  17.         ......
  18.     }
  20.     /** Index nodes represent the levels of the skip list. 
  21.         Note that even though both Nodes and Indexes have forward-pointing fields, they have different types and are handled 
  22.         in different ways, that can't nicely be captured by placing field in a shared abstract class.
  23.      */
  24.     static class Index<K,V> {//索引节点
  25.         final Node<K,V> node;//索引节点关联的数据节点
  26.         final Index<K,V> down;//下一级别索引节点（关联的数据节点相同）
  27.         volatile Index<K,V> right;//当前索引级别中，后继索引节点
  28.              ......
  29.     }
  30.     /**  Nodes heading each level keep track of their level.*/
  31.     static final class HeadIndex<K,V> extends Index<K,V> {//索引头
  32.         final int level;//索引级别
  33.         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
  34.             super(node, down, right);
  35.             this.level = level;
  36.         }
  37.     }
  38. ......
  39. }

doGet()

  1.   private V doGet(Object okey) {
  2.         Comparable<? super K> key = comparable(okey);
  3.         // Loop needed here and elsewhere in case value field goes null just as it is about to be returned, in which case we
  4.         // lost a race with a deletion, so must retry.
  5.         // 这里采用循环的方式来查找数据节点，是为了防止返回刚好被删除的数据节点，一旦出现这样的情况，需要重试。
  6.         for (;;) {
  7.             Node<K,V> n = findNode(key);//根据key查找数据节点
  8.             if (n == null)
  9.                 return null;
  10.             Object v = n.value;
  11.             if (v != null)
  12.                 return (V)v;
  13.         }
  14.   }
  17.     private Node<K,V> findNode(Comparable<? super K> key) {
  18.            for (;;) {
  19.                Node<K,V> b = findPredecessor(key);//根据key查找前驱数据节点
  20.                Node<K,V> n = b.next;
  21.                for (;;) {
  22.                    if (n == null)
  23.                        return null;
  24.                    Node<K,V> f = n.next;
  25.                    //1、b的后继节点两次读取不一致，重试
  26.                    if (n != b.next)  // inconsistent read 
  27.                        break;
  28.                    Object v = n.value;
  29.               //2、数据节点的值为null，表示该数据节点标记为已删除，移除该数据节点并重试。
  30.                 if (v == null) {                // n is deleted
  31.                     n.helpDelete(b, f);
  32.                     break;
  33.                 }
  34.                 //3、b节点被标记为删除，重试
  35.                 if (v == n || b.value == null)  // b is deleted
  36.                     break;
  37.                 int c = key.compareTo(n.key);
  38.                 if (c == 0)//找到返回
  39.                     return n;
  40.                 if (c < 0)//给定key小于当前可以，不存在
  41.                     return null;
  42.                 b = n;//否则继续查找
  43.                 n = f;
  44.             }
  45.         }
  46.     }
  48.    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
  49.            if (key == null)
  50.                throw new NullPointerException(); // don't postpone errors
  51.            for (;;) {
  52.                for (Index<K,V> q = head, r = q.right, d;;) {
  53.                    if (r != null) {
  54.                        Node<K,V> n = r.node;
  55.                        K k = n.key;
  56.                        if (n.value == null) {
  57.                            if (!q.unlink(r))
  58.                                break;           // restart
  59.                            r = q.right;         // reread r
  60.                            continue;
  61.                        }
  62.                        if (cpr(cmp, key, k) > 0) {
  63.                            q = r;
  64.                            r = r.right;
  65.                            continue;
  66.                        }
  67.                    }
  68.                     //执行到这里有两种情况：
  69.                 //1、当前级别的索引查找结束
  70.                 //2、给定key小于等于当前key
  71.                    if ((d = q.down) == null)
  72.                        return q.node;
  73.                    q = d;
  74.                    r = d.right;
  75.                }
  76.            }
  77.        }

doPut()

  1. private V doPut(K kkey, V value, boolean onlyIfAbsent) {
  2.     Comparable<? super K> key = comparable(kkey);
  3.     for (;;) {
  4.         // 找到key的前继节点
  5.         Node<K,V> b = findPredecessor(key);
  6.         // 设置n为“key的前继节点的后继节点”，即n应该是“插入节点”的“后继节点”
  7.         Node<K,V> n = b.next;
  8.         for (;;) {
  9.             if (n != null) {
  10.                 Node<K,V> f = n.next;
  11.                 // 如果两次获得的b.next不是相同的Node，就跳转到”外层for循环“，重新获得b和n后再遍历。
  12.                 if (n != b.next)
  13.                     break;
  14.                 // v是“n的值”
  15.                 Object v = n.value;
  16.                 // 当n的值为null(意味着其它线程删除了n)；此时删除b的下一个节点，然后跳转到”外层for循环“，重新获得b和n后再遍历。
  17.                 if (v == null) {               // n is deleted
  18.                     n.helpDelete(b, f);
  19.                     break;
  20.                 }
  21.                 // 如果其它线程删除了b；则跳转到”外层for循环“，重新获得b和n后再遍历。
  22.                 if (v == n || b.value == null) // b is deleted
  23.                     break;
  24.                 // 比较key和n.key
  25.                 int c = key.compareTo(n.key);
  26.                 if (c > 0) {
  27.                     b = n;
  28.                     n = f;
  29.                     continue;
  30.                 }
  31.                 if (c == 0) {
  32.                     if (onlyIfAbsent || n.casValue(v, value))
  33.                         return (V)v;
  34.                     else
  35.                         break; // restart if lost race to replace value
  36.                 }
  37.                 // else c < 0; fall through
  38.             }
  40.             // 新建节点(对应是“要插入的键值对”)
  41.             Node<K,V> z = new Node<K,V>(kkey, value, n);
  42.             // 设置“b的后继节点”为z
  43.             if (!b.casNext(n, z))
  44.                 break;         // 多线程情况下，break才可能发生(其它线程对b进行了操作)
  45.             // 随机获取一个level
  46.             // 然后在“第1层”到“第level层”的链表中都插入新建节点
  47.             int level = randomLevel();
  48.             if (level > 0)
  49.                 insertIndex(z, level);
  50.             return null;
  51.         }
  52.     }
  53. }

https://www.cnblogs.com/java-zzl/p/9767255.html
https://blog.csdn.net/sunxianghuang/article/details/52221913
……….

Vector

线程安全的（synchronized）

成员变量

  1.   protected Object[] elementData;
  2.   protected int elementCount;
  3.   protected int capacityIncrement;

构造方法

  1.     public Vector() {
  2.             this(10);
  3.         }
  5.     public Vector(int initialCapacity) {
  6.         this(initialCapacity, 0);
  7.     }
  9.     public Vector(int initialCapacity, int capacityIncrement) {
  10.             super();
  11.             if (initialCapacity < 0)
  12.                 throw new IllegalArgumentException("Illegal Capacity: "+
  13.                                                    initialCapacity);
  14.             this.elementData = new Object[initialCapacity];
  15.             this.capacityIncrement = capacityIncrement;
  16.         }
  18.     public Vector(Collection<? extends E> c) {
  19.         Object[] a = c.toArray();
  20.         elementCount = a.length;
  21.         if (c.getClass() == ArrayList.class) {
  22.             elementData = a;
  23.         } else {
  24.             elementData = Arrays.copyOf(a, elementCount, Object[].class);
  25.         }
  26.     }

add()

  1.  public synchronized boolean add(E e) {
  2.         modCount++;
  3.         ensureCapacityHelper(elementCount + 1);
  4.         elementData[elementCount++] = e;
  5.         return true;
  6.     }
  8.  private void ensureCapacityHelper(int minCapacity) {
  9.         // overflow-conscious code
  10.         if (minCapacity - elementData.length > 0)
  11.             grow(minCapacity);
  12.     }
  14.   private void grow(int minCapacity) {
  15.         // overflow-conscious code
  16.         int oldCapacity = elementData.length;
  17.         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  18.                                          capacityIncrement : oldCapacity);
  19.         if (newCapacity - minCapacity < 0)
  20.             newCapacity = minCapacity;
  21.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  22.             newCapacity = hugeCapacity(minCapacity);
  23.         elementData = Arrays.copyOf(elementData, newCapacity);
  24.     }
  26.      private static int hugeCapacity(int minCapacity) {
  27.         if (minCapacity < 0) // overflow
  28.             throw new OutOfMemoryError();
  29.         return (minCapacity > MAX_ARRAY_SIZE) ?
  30.             Integer.MAX_VALUE :
  31.             MAX_ARRAY_SIZE;
  32.     }
  34.     public void add(int index, E element) {
  35.         insertElementAt(element, index);
  36.     }
  38.     public synchronized void insertElementAt(E obj, int index) {
  39.         modCount++;
  40.         if (index > elementCount) {
  41.             throw new ArrayIndexOutOfBoundsException(index
  42.                                                      + " > " + elementCount);
  43.         }
  44.         ensureCapacityHelper(elementCount + 1);
  45.         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
  46.         elementData[index] = obj;
  47.         elementCount++;
  48.     }

Stack

image.png
封装vector的方法完成stack的peek,pop,push方法。
https://www.jianshu.com/p/62a989e7448c