jdk 版本:1.8
LinkedList 增加元素有两个办法:add(E e) 和 add(int index,E e)。
add(E e)
/**
* Appends the specified element to the end of this list.
* 在列表最初增加指定元素
*/
public boolean add(E e) {linkLast(e);
return true;
}
add(E e) 是间接在队尾增加元素。再看一下 linkLast(E e) 办法,源码如下。
void linkLast(E e) {
// 找到链表的最初一个节点,赋值给 l,final Node<E> l = last;
// 创立节点,这个节点的上一个节点就是下面 last 节点
final Node<E> newNode = new Node<>(l, e, null);
// 将新的节点赋值给最初节点
last = newNode;
if (l == null)
// 如果没有最初节点,示意增加链表为空,赋值给首节点。first = newNode;
else
// 有最初一个节点,将最初节点的 next 指针指向新建的节点
l.next = newNode;
size++;
modCount++;
}
- LinkedList 会记录链表的最初一个节点 last,
- 首先创立新的节点,新节点的 pre 就是队列的最初一个节点 last,新节点的 next 为 null,
- 如果 last 为空示意这个链表为空,新节点就是首节点 first。
-
如果 last 不为空示意链表不为空,将 last 节点的 next 指针指向新节点。
add(int index,E e)
add(int index,E e) 是依据元素插入到指定地位上,index 示意链表的地位
/** * Inserts the specified element at the specified position in this list. * 插入指定的元素到列表指定地位上 */ public void add(int index, E element) { // 查看地位是否越界 checkPositionIndex(index); // 如果插入的下标等于链表的大小,间接就是增加到队尾,if (index == size) linkLast(element); else linkBefore(element, node(index)); }
- 首先查看 index 是否超过链表大小,即 index 是否会大于链表的 size。
- 如果 index 等于链表的大小,增加元素就是在链表队尾增加元素,和 add(E e) 操作统一。
-
如果不等会 size 大小就调用 linkBefore 办法,首先在该办法的第二个参数应用了 node 办法。node 办法源码如下:
Node<E> node(int index) { //size >>1 示意 size 右移,示意 size 的一半 // 如果 index 小于 size 一半,从首节点往后遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; // 如果 index 大于 size 一半,从最初一个节点往前遍历 } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
node 办法通过链表的地位找到链表的元素。这里用到了一个 size 的右移运算,size>>1 示意 size/2。首先判断 index 是在链表的前一半还是后一半,因为 linkedList 是双链表,能够往前和往后进行遍历。如果在前半部分就从首节点往后遍历,如果在后半局部就从最初一个节点往前遍历, 这样最多遍历 size 的一半,防止遍历整个链表。
找到 index 对应的元素后执行 linkedBefore 办法/** * Inserts element e before non-null Node succ. * 往 succ 节点后面插入元素 */ void linkBefore(E e, Node<E> succ) { //succ 的前一个节点 final Node<E> pred = succ.prev; // 创立新节点,新节点的 pre 就是 succ 的 pre 节点,新节点的 next 就是 succ 节点 final Node<E> newNode = new Node<>(pred, e, succ); //succ.pre 指向新节点 succ.prev = newNode; // 如果 succ 前节点为空,示意 succ 就是首节点,新节点即为首节点 if (pred == null) first = newNode; else //succ 的上一节点的 next 指向新节点 pred.next = newNode; size++; modCount++; }
- 新建节点,节点 pre 就是 succ 的 pre,节点的 next 就是 succ。
- 将 succ.pre 指向新节点。
- succ 的 pre 为 null,succ 即为首节点,将 first 赋值给首节点
- succ 的 pre 不为空,则把 succ 的上一节点的 next 指向新节点
总结
- LinkedList,只有两种增加形式,一种是在列表最初增加 (linkLast),一种是在列表某个元素后面增加 (linkBefore)。
- LinkLast,首先创立一个新节点,节点 pre 指向最初一个节点,最初一个节点的 next 指向新节点。
-
LinkBefore,首先依据 index 下标获取到元素的地位,新建新节点,新节点的 pre 就是元素的 pre,新节点的 next 就是该元素。元素的 pre 的 next 指向新元素。
为何 Linked 要用双链表而不是单链表
LinkedList 为何是双链表,链表次要毛病是查问速度很慢,增加或者删除都要找到要增加和删除的节点,而应用双链表,每次遍历循环前,都会判断一下索引是在链表的前半部分还是后半局部。如果是前半部分的话,从首部遍历到两头。如果是后半局部,从尾部遍历到两头。