Java中的集合包含多种数据结构，如链表、队列、哈希表等。从类的继承结构来说，可以分为两大类，一类是继承自Collection接口，这类集合包含List、Set和Queue等集合类。另一类是继承自Map接口，这主要包含了哈希表相关的集合类。

 

 

 

 

常用的实现List接口的主要有ArrayList、Vector、LinkedList 三个，通过查看jdk底层源码实现，进行简单的要点总结：

ArrayList是List使用中最常用的实现类，它的查询速度快，效率高，但增删慢，线程不安全。

ArrayList底层实现采用的数据结构是数组，并且数组默认大小为10，所以下面两种方式是等同的：

  1. List list = new ArrayList();  //没有指定数组大小，使用默认值（默认大小是10）
  3. List list = new ArrayList(10);  // 指定数组大小为10，传如的参数便是数组的大小，传入为10时，跟默认值相同，所以是等同的

要想清楚的理解上面两中方式，从ArrayList类的构造器就会豁然开朗：

注：不同的jdk版本实现代码有所不同, 现以jdk1.8为例（个人感觉  jdk1.6的底层实现写法更好理解，jdk1.8就比1.6较难懂一些）

  1. // 无参构造器
    public     ArrayList() {
  2. this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;   // DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个默认大小的空实例
  3. }
  5. // 有参构造器，参数为列表的初始容量（由于是通过数组实现的，所以可以理解成数组的大小）
  6. public ArrayList(int initialCapacity) {
  7. 　　if (initialCapacity > 0) {
  8. 　　　　this.elementData = new Object[initialCapacity];
  9. 　　} else if (initialCapacity == 0) {
  10. 　　　　this.elementData = EMPTY_ELEMENTDATA;
  11. 　　} else {
  12. 　　　　throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
  13. 　　}
  14. }

 

jdk1.8的扩容算法：newCapacity = oldCapacity + ( oldCapacity >> 1 ) ;   // oldCapacity >> 2  移位运算，此处相当于oldCapacity除以2，但是 >> 这种写法更加高效

jdk1.6的扩容算法：newCapacity = ( oldCapacity * 3 ) / 2 +1 ;

参数介绍：newCapacity 是扩容后的容量大小，oldCapacity 是扩容前的大小

查看jdk源码，移位运算需要学习下，换句话说，就是需要学习下二进制，比如：反码、补码，二进制与十进制、十六进制的相互转换。与机器交流的都是0110等，所以挺重要的。

 

Vector的底层也是通过数组实现的，默认大小也是10。主要特点：查询快，增删慢  ， 线程安全，但是效率低

创建对象与ArrayList类似，但有一点不同，它可以设置扩容是容量增长大小。

根据Vector的三个构造器就可以很明了的理解 new Vector(); 与 new Vector(10);与 new Vector(10,0); 三个是等同的，很明了就不赘述了。

  1. 1.无参构造器
    public Vector() {
  2.         this(10);
  3.     }
  5. 2.传一个参数（容量大小） 容量大小即底层数组大小
  6. public Vector(int initialCapacity) {
  7.         this(initialCapacity, 0);
  8.     }

  9. 3.传两个参数（容量大小，容量修正） 容量修正即扩容时的增加量
  10. public Vector(int initialCapacity, int capacityIncrement) {
  11.         super();
  12.         if (initialCapacity < 0)
  13.             throw new IllegalArgumentException("Illegal Capacity: "+
  14.                                                initialCapacity);
  15.         this.elementData = new Object[initialCapacity];
  16.         this.capacityIncrement = capacityIncrement;
  17.     }

 

jdk1.8的扩容算法：newCapacity = oldCapacity + ( ( capacityIncrement > 0 ) ? capacityIncrement : oldCapacity );

jdk1.6的扩容算法：newCapacity = ( capacityIncrement > 0 ) ? ( oldCapacity + capacityIncrement ) : (  oldCapacity  * 2 );

参数介绍：capacityIncrement 是容量修正（即容量新增大小），没有设置，默认为0    ，newCapacity 是扩容后的容量大小，oldCapacity 是扩容前的大小

一观察，就会发现1.6与1.8的写法变化不大，但是仔细一分析，就会发现jdk1.6中有使用乘法运算，即 oldCapacity  * 2。 在jdk1.8中换成了加法运算，这是因为乘法的效率是低于加法的，这应该算法的优化。

 

LinkedList底层是一个双向链表，它增删快，效率高，但是查询慢，线程不安全

构造器只有如下两种;

  1. 1.无参构造
  2. public LinkedList() {
  3.     }
  5. 2.有参构造
  6. public LinkedList(Collection<? extends E> c) {
  7.         this();
  8.         addAll(c);
  9.     }

 

由于它的底层实现是链表，所以没有容量大小的定义，只有上个节点，当前节点，下个节点，每个节点都有一个上级节点和一个下级节点。

1.头部新增

实现代码如下：

  1. private void linkFirst(E e) {
  2.         final Node<E> f = first;
  3.         final Node<E> newNode = new Node<>(null, e, f);
  4.         first = newNode;
  5.         if (f == null)
  6.             last = newNode;
  7.         else
  8.             f.prev = newNode;
  9.         size++;
  10.         modCount++;
  11.     }

先获取头部节点元素，判断是否为null，若为null，说明原链表中没有元素，则把 first 和 last 都赋为当前新增节点。

　　　　　　　　　　　　　　　　　　若不为null，说明原链表中有元素，则把first赋为当前新增节点，把原头部节点f的上级节点修改为当前新增节点的下级节点

2.尾部新增

  1. void linkLast(E e) {
  2.         final Node<E> l = last;
  3.         final Node<E> newNode = new Node<>(l, e, null);
  4.         last = newNode;
  5.         if (l == null)
  6.             first = newNode;
  7.         else
  8.             l.next = newNode;
  9.         size++;
  10.         modCount++;
  11.     }

与头部新增元素类似，不再赘述。

删除元素有三种方式，删除第一元素，删除最后一个元素，删除中间部分的某个元素。   现介绍最后一个，最后一个搞懂了，前两个就懂了。

实现代码：

  1. E unlink(Node<E> x) {
  2.         // assert x != null;
  3.         final E element = x.item;
  4.         final Node<E> next = x.next;
  5.         final Node<E> prev = x.prev;
  7.         if (prev == null) {
  8.             first = next;
  9.         } else {
  10.             prev.next = next;
  11.             x.prev = null;
  12.         }
  14.         if (next == null) {
  15.             last = prev;
  16.         } else {
  17.             next.prev = prev;
  18.             x.next = null;
  19.         }
  21.         x.item = null;
  22.         size--;
  23.         modCount++;
  24.         return element;
  25.     }

原理：要删除元素的当前节点x，将当前节点x的上级节点的下级节点设为当前节点x的下级节点，将当前节点x的下级节点的上级节点设为当前节点x的上级节点。

　　   中间考虑上级节点或下级节点为空的情况，也就是头部删除与尾部删除。

 

版权声明：本文为kanglijun原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/kanglijun/p/10999247.html