第一章 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效率比较高。
标签：分析,index,LinkedList,ArrayList,Node,链表,源码,节点 From： https://www.cnblogs.com/niuxiwei/p/16879335.html实际场景下，如果需要多线程访问安全的数组，使用CopyOnWriteArrayList。