第一章 LinkedList源码分析

目标：

理解LinkedList的底层数据结构 深入源码掌握LinkedList查询慢              ，新增快的原因

一              、LinkedList的简介

List接口的链接列表实现              。实现所有可选的列表操作
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，并且允许所有元素（包括null)
 
  
 
  
 
  
 
  
 
  
 
  
 
  。除了实现List接口外













，LinkedList类为在列表的开头及结尾get
 
  
 
  
 
  
 
  
 
  
 
  
 
  、remove和insert元素提供了统一的命名方法













。这些操作允许将链接列表用作堆栈













、队列或双端队列  
  
  
  
  
  
  
。

特点：

有序性：存入和取出的顺序是一致的 元素可以重复 含有带索引的方法 独有特点：数据结构是链表  
  
  
  
  
  
  
，可以作为栈  
  
  
  
  
  
  
、队列或双端队列！

LinkedList是一个双向的链表结构 
  
  
  
  
  
  
 ，双向链表的长相


 


 


 


 


 


 


 ，如下图！

二 
  
  
  
  
  
  
 、LinkedList原理分析

2.1LinkedList的数据结构

LinkedList是一个双向链表！

底层数据结构的源码：

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; //节点类【内部类】 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; } } //... }

LinkedList是双向链表 
 
 
 
 
 
 
，在代码中是一个Node类 
  
  
  
  
  
  
 。 内部并没有数组的结构


 


 


 


 


 


 


 。双向链表肯定存在一个头节点和一个尾节点 
 
 
 
 
 
 
。node节点类  
   
   
   
   
   
   
 ，是以内部类的形式存在与LinkedList中的  
   
   
   
   
   
   
 。Node类都有两个成员变量

 

 

 

 

 

 

 。

prev：当前节点上一个节点

 

 

 

 

 

 

 ，头节点的上一个节点是null next：当前节点下一个节点
 

 

 

 

 

 

 
，尾节点的下一个节点是null

链表数据结构的特点：查询慢              ，增删快！

链表数据结构基本构成
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，是一个node类 每个node类中













，有上一个节点【prev】和下一个节点【next】 链表一定存在至少两个节点                     ，first和last节点 如果LinkedList没有数据
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，first和last都是为null

2.2LinkedList默认容量&最大容量

没有默认容量




















，也没有最大容量

2.3LinkedList扩容机制

无需扩容机制              ，只要你的内存足够大
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，可以无限制扩容下去
 

 

 

 

 

 

 
。前提是不考虑查询的效率              。

2.4为什么LinkedList查询慢













，增删快？

LinkedList的数据结构的特点  
  
  
  
  
  
  
，链表的数据结构就是这样的特点！

链表是一种查询慢的结构【相对于数组来说】 链表是一种增删快的结构【相对于数组来说】

2.5LinkedList源码刨析-为什么增删快？

新增add

//向LinkedList添加一个元素 public boolean add(E e) { //连接到链表的末尾 linkLast(e); return true; } //连接到最后一个节点上去 void linkLast(E e) { //将全局末尾节点赋值给1 final Node<E> l = last; //创建一个新节点：（上一个节点 
  
  
  
  
  
  
 ，当前插入元素


 


 


 


 


 


 


 ，null） final Node<E> newNode = new Node<>(l, e, null); //将当前节点作为末尾节点 last = newNode; //判断l节点是否为null if (l == null) //即是尾节点也是头节点 first = newNode; else //之前的末尾节点 
 
 
 
 
 
 
，下一个节点是末尾节点 l.next = newNode; size++;//当前集合的元素数量+1 modCount++;//操作集合数+1  
   
   
   
   
   
   
 ，modCount属性是修改计数器 } //----------------------------------------------------------------- //向链表的中部添加 //参数1

 

 

 

 

 

 

 ，添加的索引位置
 

 

 

 

 

 

 
，添加元素 public void add(int index, E element) { //检查索引位是否符合要求 checkPositionIndex(index); //判断当前索引位是否存储元素个数 if (index == size)//true,最后一个元素 linkLast(element); else //连接到指定节点的后面【链表中部插入】 linkBefore(element, node(index)); } //根据索引查询链表中节点！ Node<E> node(int index) { //判断索引是否小于 已经存储元素个数的1/2 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; } } //将当前元素添加到指定节点之前 void linkBefore(E e, Node<E> succ) { //取出当前节点的前一个节点 final Node<E> pred = succ.prev; //创建当前元素的节点：上一个节点              ，当前元素
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，下一个节点 final Node<E> newNode = new Node<>(pred, e, succ); //为指定节点上一个节点重赋新值 succ.prev = newNode; //判断当前节点的上一个节点是否为null if (pred == null) first = newNode;//当前节点作为头部节点 else pred.next = newNode;//将新插入节点作为上一个节点的下一个节点 size++;//新增元素+1 modCount++;//操作次数+1 }

remove删除指定索引元素

//删除指定索引位置元素 public E remove(int index) { //检查元素索引 checkElementIndex(index); //删除元素节点 //node(index) 根据索引查到要删除的节点 //unlink()删除节点 return unlink(node(index)); } //根据索引查询链表中节点！ Node<E> node(int index) { //判断索引是否小于 已经存储元素个数的1/2 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; } } //删除一个指定节点 E unlink(Node<E> x) { //获取当前节点的元素 final E element = x.item; //获取当前节点的上一个节点 final Node<E> next = x.next; //获取当前节点的下一个节点 final Node<E> prev = x.prev; //判断上一个节点是否为null if (prev == null) { //如果为null,说明当前节点为头部节点 first = next; } else { //上一个节点 的下一个节点改为下下节点 prev.next = next; //将当前节点的上一个节点置空 x.prev = null; } //判断下一个节点是否为null if (next == null) { //如果为null













，说明当前节点为尾部节点 last = prev; } else { //下一个节点的上节点                     ，改为上上节点 next.prev = prev; //当前节点的上节点置空 x.next = null; } //删除当前节点内的元素 x.item = null; size--;//集合中的元素个数-1 modCount++;//当前集合操作数+1
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，modCount计数器




















，记录当前集合操作数次数 return element;//返回删除的元素 }

2.6LinkedList源码刨析-为什么查询慢？

查询快和慢是一个相对概念！相对于数组来说

//根据索引查询一个元素 public E get(int index) { //检查索引是否存在 checkElementIndex(index); //node(index)获取索引对应节点              ，获取节点中的数据item return node(index).item; } //根据索引获取对应节点对象 Node<E> node(int 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; } } //查看ArrayList里的数组获取元素的方式 public E get(int index) { rangeCheck(index);//检查范围 return elementData(index);//获取元素 } E elementData(int index) { return (E) elementData[index];//一次性操作 }

第二章 经典面试题

1


 


 


 


 


 


 


 、ArrayList的JDK1.8之前与之后的实现区别？

JDK1.6：ArrayList像饿汉模式
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，直接创建一个初始化容量为10的数组
 

 
 

 
 

 
 

 
 

 
 

 
 

 。缺点就是占用空间较大













。 JDK1.7&JDK1.8：ArrayList像懒汉式













，一开始创建一个长度为0的数组  
  
  
  
  
  
  
，当添加第一个元素时再创建一个初始容量为10的数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

2 
 
 
 
 
 
 
、List和Map区别？

Map集合

双列集合：一次存一对 key是不允许重复的 
  
  
  
  
  
  
 ，value可以重复 一个key只能对应一个值value Map集合三兄弟：HashMap【无序集合】  
   
   
   
   
   
   
 、LinkedHashMap【有序集合】

 

 

 

 

 

 

 、TreeMap【有序集合
 

 

 

 

 

 

 
、自带排序能力】

List集合

单列集合：一次存一个 有序集合 元素重复 带索引 List集合主要有两个实现类：ArrayList和LinkedList

3              、Array和ArrayList有何区别？什么时候更适合用Arry?

区别：

Array可以容纳基本类型和对象


 


 


 


 


 


 


 ，而ArrayList只能容纳对象【底层是一个对象数组】 Array指定大小的固定不变 
 
 
 
 
 
 
，而ArrayList大小是动态的  
   
   
   
   
   
   
 ，可自动扩容                     。 Array没有ArrayList方法多
 
 
 
 
 
 
 
 
 
 
 
 
 
 。
 

 
 

 
 

 
 

 
 

 
 

 
 

 、

尽管ArrayList明显是更好的选择

 

 

 

 

 

 

 ，但也有些时候Array比较好用
 

 

 

 

 

 

 
，比如下面的三种情况




















。

1













、如果列表的大小已经指定              ，大部分情况是存储和遍历它们 基本数据类型使用Array更合适

4                     、ArrayList与LinkedList区别？

ArrayList

优点：ArrayList是实现了基于动态数组的数据结构
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，因为地址连续













，一旦数据存储好了                     ，查询操作效率会比较高（在内存里是连着放的）              。查询快
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，增删相对慢
 
  
 
  
 
  
 
  
 
  
 
  
 
  。 缺点：因为地址连续




















，ArrayList要移动数据              ，所以插入和删除操作效率比较低













。

LinkedList

优点：LinkedList基于链表的数据结构
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，地址是任意的













，所以在开辟内存空间的时候不需要等一个连续的地址  
  
  
  
  
  
  
。对于新增和删除操作add和remove  
  
  
  
  
  
  
，LinkedList比较占优势 
  
  
  
  
  
  
 。LinkedList使用于要头尾操作或插入指定位置的场景


 


 


 


 


 


 


 。 缺点：因为LinkedList要移动指针 
  
  
  
  
  
  
 ，所以查询操作性能比较低 
 
 
 
 
 
 
。查询慢


 


 


 


 


 


 


 ，增删快  
   
   
   
   
   
   
 。

适用场景分析：

当需要对数据进行随机访问的情况下 
 
 
 
 
 
 
，选用ArrayList

 

 

 

 

 

 

 。 当需要对数据进行多次增加删除修改时  
   
   
   
   
   
   
 ，采用LinkedList
 

 

 

 

 

 

 
。 当然

 

 

 

 

 

 

 ，绝大数业务的场景下
 

 

 

 

 

 

 
，使用ArrayList就够了              。主要是              ，注意：最好避免ArrayList扩容
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，以及非顺序的插入
 

 
 

 
 

 
 

 
 

 
 

 
 

 。

ArrayList是如何扩容的？

如果通过无参构造的话













，初始数组容量为0                     ，当真正对数组进行添加时
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，才真正分配容量













。每次按照1.5倍（位运算）的比率通过copyOf的方式扩容                     。

重点是1.5倍扩容




















，这是和HashMap 2倍扩容不同的地方
 
 
 
 
 
 
 
 
 
 
 
 
 
 。

5
 
 
 
 
 
 
 
 
 
 
 
 
 
 、ArrayList集合加入10万条数据              ，应该怎么提高效率？

ArrayList的默认初始容量为10
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，要插入大量数据的时候需要不断扩容













，而扩容是非常影响性能的




















。因此  
  
  
  
  
  
  
，现在明确了10万条数据了 
  
  
  
  
  
  
 ，我们可以直接在初始化的时候就设置ArrayList的容量！

这样就可以提高效率了~

6




















、ArrayList和Vector区别？

ArrayList和Vector都是用数组实现的


 


 


 


 


 


 


 ，主要有这么三个区别：

1              、Vector是多线程安全的 
 
 
 
 
 
 
，线程安全就是说多线程访问同一代码  
   
   
   
   
   
   
 ，不会产生不确定的结果

 

 

 

 

 

 

 ，而ArrayList不是              。这个可以从源码中看出
 

 

 

 

 

 

 
，Vector类中的方法很多有synchronized进行修饰              ，这样导致了Vector在效率上无法与ArrayList相比
 
  
 
  
 
  
 
  
 
  
 
  
 
  。

Vector是一种老的动态数组
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，是线程同步的













，效率很低                     ，一般不赞成使用













。

2
 
  
 
  
 
  
 
  
 
  
 
  
 
  、两个都是采用的线性连续空间存储元素
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，但是当空间不足的时候




















，两个类的增加方式是不同  
  
  
  
  
  
  
。 3













、Vector可以设置增长因子              ，而ArrayList不可以
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，ArrayList集合没有增长因子 
  
  
  
  
  
  
 。

适用场景分析：

1  
  
  
  
  
  
  
、Vector是线程同步的













，所以它也是线程安全的  
  
  
  
  
  
  
，而ArrayList是线程无需同步的 
  
  
  
  
  
  
 ，是不安全的


 


 


 


 


 


 


 。如果不考虑到线程的安全因素


 


 


 


 


 


 


 ，一般用ArrayList效率比较高 
 
 
 
 
 
 
。

实际场景下 
 
 
 
 
 
 
，如果需要多线程访问安全的数组  
   
   
   
   
   
   
 ，使用CopyOnWriteArrayList  
   
   
   
   
   
   
 。