LinkedList源码分析
LinkedList原理： 源码对应的jdk版本均为jdk11
先看LinkedList的构造方法：
有两个构造方法：1、无参数 2、参数为集合
//默认创建一个LinkedLiseList<Integer> link = new LinkedList<>();
//创建一个将其他类型集合的数据化为己用的LinkedList
List<Integer> link1 = new LinkedList<Integer>(new HashSet<Integer>());
看下LinkedList的属性：
transient int size = 0; /**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
LinkedList主要由若干个阶段链接而成，有两个终端节点，一个在起始位置，另一个在终点位置，并且还有一个属性size记录整个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;
}
}
可以看到Linked内部维护了一个双向链表。item为当前节点的值，next为指向下一个节点，prev变量指向前一个节点
LinkedList 无参构造函数：
/** * Constructs an empty list.
*/
public LinkedList() {
}
LinkedList无参构造函数什么操作都没有，因为其类的定义属性已经包含了LinkedList初始化时需要的一切。LinkedList的重点在于节点的构成和节点之间的操作
LinkedList的有参构造函数 -- 入参类型为集合类
public LinkedList(Collection<? extends E> c) { this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
我们主要分析下addAll()的源码部分，addAll(size, c)这部分;
1）我们调用LinkedList的有参构造函数，会调用addAll方法，addAll(size,c)
2)首先检查传入的index是否越界，把集合C转换为object[]
3）令pred指针移到链表的末尾，然后遍历Object[]数组，在链表末尾追加相应的元素
4）全部增加完成后将last指针移到链表末尾，linkedList的size增加相应的数组长度
然后分下我们常用的LinkedList中的方法
get()源码分析：
public E get(int index) { checkElementIndex(index);
return node(index).item;
}
1)检查传入的index，是否越界
2）根据node方法取出index对应的节点，并取出其值(item)
接下来我们看下node()方法：
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;
}
}
1）首先根据index与size/2进行比较
2）如果index < size/2说明节点在LinkedList的前半段，从第一个节点遍历会更容易找
3）如果index >= size/2，那么从后往前找，这样会更加省时和容易找
所以如果这个节点越靠近中间，那么get()方法遍历的时间也越长，效率越低。而且随着LinkedList的节点数量越来越多，get()的执行性能也回迅速下降。所以在使用LinkedList时可以使用getFirst()、getLast()方法，直接调用类中的first和last变量
add(E e)源码分析:
插入一个元素，默认为在最后追加一个元素 public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
1)把我们传入的值，构造为一个Node对象，prev指针LinkedList的最后一个元素，next为空,然后吧LinkedList的last指针指向当前节点
2）判断LinkedList的最后一个Node是否为空，如果为为空的话，说明此时添加的为第一个节点，就是first指针指向当前元素
3）如果l最后一个元素不为空，就把之前的last指针的next指针指向当前节点。然后LinkdeList的size + 1
add(int index , E e)源码分析：
根据索引位置插入一个元素
public void add(int index, E element) { checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
1)检查数组是否越界，如果index的值等于LinkedList的size值，则在LinkedList默认进行添加，使用linkLast()之前分析过
2）如果index的值小于LinkedList的size值，首先根据node()方法找到之前index上的元素，就是用linkBefore()进行添加
linkBefore（）：
void linkBefore(E e, Node<E> succ) { // assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
1）找到对应index上的元素，然后根据传入的元素值构建一个新的Node，Node的前一个指针指向之前元素的prev，后一个指针指向之前元素，把之前元素的前一个指针指向新的Node
2）判断之前元素是否为第一个元素，如果为第一个元素，就把LinkedList的first节点指向新节点
3）如果不为第一个元素，之前元素的next指针指向新的Node。增加LinkedList的size +1
在ArrayList中插入数据可能有的数组扩容和数据元素移动造成的开销，在LinkedList都不需要，所以相比ArrayList，LinkedList的插入效率比较高。除了add()之外，比较常用的添加方法还有addFirst()和addLast()。
remove(Object o)源码分析：
LinkedList 移除一个对象
public boolean remove(Object o) { if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
1)如果object对象为null的话，就遍历LinkedList，找到值为null的节点，并通过unlink()方法来删除这个节点
2）如果object对象不为null的话，使用equals方法来比较是否相等，如果相等通过unlink()方法删除这个节点
unlink() 源码分析：
E unlink(Node<E> x) { // assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
1）如果unlink的元素前一个为null的话，说明它为第一个元素，则移动first指针到该元素的下一个。
2）如果不是第一个元素的话，在将该节点x的前节点的后指针指向x的后节点，把x的前节点置为null等待GC回收
3）如果X为最后一个节点的话，就把last的指针指向，x的前一个节点
4）如果不是最后一个元素的话，将x的后节点的前指针指向x的前节点，把x的后节点置为null等待GC回收
remove(int index)：
public E remove(int index) { checkElementIndex(index);
return unlink(node(index));
}
1）检查数组是否越界，如果没有越界，通过node()方法找到对应索引位置的Node
2）根据unlink来移除该节点
以上是 LinkedList源码分析 的全部内容， 来源链接： utcz.com/z/515619.html
