惯例，笑话开头。
阅读本文你可以掌握，LinkedList 相关知识点和细节。
| 目录 |
|---|
| 数据结构基础 |
| LinkedList源码解析 |
| 面试知识 |
数据结构基础
链表的特点
1，链表查询数据，需要遍历整个链表，即便是做了优化，判断当前index，确定从前边遍历或者从后边遍历，时间复杂度仍是O(n)。
2，链表插入和删除的，首先需要找到当前插入的点，也需要遍历链表，然后把节点指针相连，所以时间复杂度也是O(n);但是为什么都说链表更适合插入和删除呢，因为链表查找的时间要比移动数据快很多。
3 ，内存利用率高，不会浪费内存（数组需要提前分配内存，链表则不需要，而且没有大小限制，内存也可以不连续）
单链表和双链表
单链表
缺点：每个节点只有一个next指针，只能一种遍历方式，
优点：单链表存储一个节点，就比较节省内存，当节点N无线大的时候，节省的内存还是挺可观的。
双链表
优点：每个节点有两个指针，可以从前边或者从后边遍历，利用二分查找，所以理论上双链表遍历效率是比单链表快的，
缺点：但是相对单链表来说占用内存相对较大
LinkedList源码解析
Node 节点代码
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;
}
}
成员属性
| 属性 | |
|---|---|
| size | 链表长度 |
| first | 头节点 |
| last | 尾节点 |
| modCount | failFast机制 |
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
为什么定义两个节点？
如果只有一个头节点，添加数据就需要从头结点遍历拿到最后一个节点，这样时间复杂度O(n)，数据量庞大的时候效果非常明显，定义一个last节点，添加单个数据的时间复杂度就变成了O(1).
void linkBefore(E e) {
Node newNode = new Node(e, null);
Node next = first;
if (next ==null){
first =newNode;
}else{
//遍历找到最后一个节点
for (int i = 0; i < size; i++){
next = next.next;
}
next.next =newNode;
}
size++;
}
这种写法 每次添加数据的时候需要找到最后一个节点，时间复杂度O(n)；
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
定义一个last节点，添加就变成了O(1)级别
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
第二种，把当前数据转换成数组，然后遍历数组，创建Node节点添加到链表中。
为什么使用双链表？
单链表遍历只能一个方向遍历，时间复杂度O(n),使用双链表可以两个方向遍历，时间复杂度O(n/2),当N足够大其实也是O(n)，但是这样实际减少了遍历消耗。
*/
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
面试知识
LinkdeList 面试大部分是对比ArrayList 来的。
1，为什么实现不是单链表
答 ：空间换时间，消耗了一定空间，遍历的时候速度相对来说加快一倍。
2，为什么定义两个节点？
答：优化了添加的时间复杂度，一个节点需要遍历找到最后的节点，定义一个尾节点，使得添加时间复杂度从O(n)降低为O(1);
3，什么时候使用Arraylist 什么时候使用lindekList？
答：如果需要频繁移除或者中间插入这种，arraylist都需要调用arraycopy比较消耗性能，这种时候需要考虑linkedlist，如果只是遍历就用arraylist 查询级别O(1)；linkedlist查询虽然做了优化，(二分查找) 但是数据足够大还是o(n)级别。
