LinkedList源码研究
文章目录
接着上一篇，研究完ArrarList之后，理所应当看看LinkedList
什么是LinkedList呢，
它是通过 双向链表实现的列表，具有双向链表的优缺点
相比较ArrarList，增删效率要高，随机访问效率要低
LinkedList
首先看一下里面定义的参数
transient int size = 0;//节点数量
transient Node<E> first;//头节点
transient Node<E> last;//尾节点经典的双向链表数据结构 它包含一个非常重要的私有内部静态类: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;
}
}然后看一下它的构造方法，也就是我们创建它的源码
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}无参构造
public LinkedList() {
}没啥说的，空构造而已
有参构造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}继续往里点
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}让我们点进addAll()方法，写的十分优美
public boolean addAll(int index, Collection<? extends E> c) {
//检查长度是否越界
checkPositionIndex(index);
Object[] a = c.toArray();//形态转换，方便后期操作
int numNew = a.length;//获取参数个数
if (numNew == 0)//如果数量为0
return false;//返回false
Node<E> pred, succ;//注意，此时前后节点的设计，对后期批量插入十分关键，是美的前提
if (index == size) {
succ = null;//当在链表最后插入时，last变为前节点，后继节点为空
pred = last;
} else {
succ = node(index);//在当前节点的前面插入整个数组
pred = succ.prev;
}
//每个节点有三个特征，pred, element, succ.注意三个元素的变化
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);//新建节点，并指向pred
if (pred == null)
first = newNode;
else
//对pred节点，让其指向newNode.至此，newNode与前节点的双边指向关系建立.此时后节点还没出现
pred.next = newNode;
//令newNodeo为即将插入节点的前节点，在一个循环中，newNode将建立与后节点的双边指向关系
pred = newNode;
}
//如此循环结束后，只剩最后一个节点的双边指向关系没有建立
if (succ == null) {
last = pred;
} else {//建立最后一个节点的指向
pred.next = succ;
succ.prev = pred;
}
size += numNew;//节点数增加
modCount++;//链表修改次数增加
return true;
}这个方法做了什么呢，首先检查长度是否越界，然后将参数转化为数组，通过尾插法添加进链表 至此，一个双向链表被创建了出来
然后再让我们研究下LinkedList的添加与删除 先看添加吧，因为LinkedList本质是双向链表，是可以当做队列或栈使用的。 其添加不光有add()方法，也有push()方法
push()方法
看到这个方法名想起来什么？ 没错，就是栈 LinkedList是有push()和pop()方法的，所以它能当栈来使用
public void push(E e) {
addFirst(e);
}可以看到，push()方法，其实就是通过头插法，将数据插到链表头部的位置，点进去
public void addFirst(E e) {
linkFirst(e);
}再点进去
private void linkFirst(E e) {
final Node<E> f = first;//创建节点f，将头节点赋给它
final Node<E> newNode = new Node<>(null, e, f);//创建新节点newNode，放在f的前面
first = newNode;//将头节点设为新节点newNode
if (f == null)//如果f为空，即插入前链表为空链表
last = newNode;//将尾节点设为新节点newNode
else
f.prev = newNode;//将f的上一个节点设为新节点newNode
size++;//节点数量+1
modCount++;//操作次数+1
}至此，插入成功。 显而易见，push()方法是头插法插入元素（将新节点放在原来头节点的前面）
add()方法
public boolean add(E e) {
linkLast(e);
return true;
}看名字就能看到，这个肯定是尾插法插入元素，让我们点进去
void linkLast(E e) {
final Node<E> l = last;//创建节点l=尾节点
final Node<E> newNode = new Node<>(l, e, null);//创建新节点，并将节点放在尾节点的后面
last = newNode;//设置尾节点为新节点
if (l == null)//如果l为空，即原链表为空链表
first = newNode;//设置头节点为新节点
else
l.next = newNode;//将l节点指向新节点
size++;//节点数量+1
modCount++;//操作次数+1
}至此，插入数据成功，果然是尾插法。 那么，push和add有什么不同呢？ add 是加在list尾部，是将LinkedList当作链表来使用。 push 施加在list头部， 等同于addFirst，是将LinkedList当作栈来使用。 验证：
顺便一提，LinkedList的取出操作只有pop和get。并且如果一个LinkedList中既有add的添加，又有push的添加，那么pop操作会先取栈元素，再取队列元素。
好了，再让我们看一下get()与set()方法
get()方法
本质上还是遍历链表中的数据，通过下标取数据
public E get(int index) {
checkElementIndex(index);//检查是否越界
return node(index).item;
}让我们点进去node方法，看看里面
Node<E> node(int index) {
// assert isElementIndex(index);
//下标和长度的一半比较，用以确定从头还是尾遍历
if (index < (size >> 1)) {//size >> 1 移位运算，意味size的一半
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;
}
}就是做了一个从头还是从尾遍历的判断，然后取值，嗐
set()方法
public E set(int index, E element) {
checkElementIndex(index);//检查下标是否越界
Node<E> x = node(index);//根据下标取值
E oldVal = x.item;//旧数据
x.item = element;//更新数据
return oldVal;//返回旧数据
}没啥难得，看注释就好 有兴趣的同学可以看看remove方法的源码，remove有三个哦
腾讯云开发者
