LinkedList 底层基于链表实现,增删不需要移动数据,所以效率很高。但是查询和修改数据的效率低,不能像数组那样根据下标快速的定位到数据,需要一个一个遍历数据。
数据结构LinkedList 是基于链表实现的结构,主要核心是 Node 节点,源码如下:
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
结构如下图所示:
这是一个双链表的的结构,有 prev 前置指针和next 后置指针。
还有首节点first、尾结点last、长度size:
transient int size = 0; transient Node添加数据first; transient Node last;
LinkedList添加元素有两个方法:add(E e) 和 **add(int index,E e)**。
-
add(E e) 是在链表的尾部添加数据
-
add(int index,E e) 在指定链表位置添加数据
add 方法调用了 linkLast 方法:
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast 表示在链表最后添加指定元素:
void linkLast(E e) {
// 记录原尾部节点
final Node l = last;
// 创建新节点,新节点的前置节点为原尾部节点
final Node newNode = new Node<>(l, e, null);
// 更新尾部节点
last = newNode;
if (l == null)
// 尾部节点为空,更新头部节点
first = newNode;
else
// 尾部不为空,原尾部后置节点就是新节点
l.next = newNode;
// size 和 modCount 自增
size++;
modCount++;
}
-
记录原尾部节点 l
-
创建新的节点,前置指向原尾部节点。
-
如果 l 为空,更新头部节点
-
更新尾部节点
-
如果 l 不为空,l 的后置指针指向新节点
如果原尾部节点为空,直接创建一个节点,这个节点是last和first节点。 如果原尾部节点不为空,创建新节点,新节点的前置指向原来的last,原来的last的next指向新节点。
add(int index,E e)这个方法是添加元素到链表的指定位置,链表的下标和数组一样,也是从0开始算起:
先看一下 add(int index, E element) 方法
public void add(int index, E element) {
// 检查下标是否越界
checkPositionIndex(index);
if (index == size)
// 下标等于size,直接添加到链表尾部
linkLast(element);
else
//
linkBefore(element, node(index));
}
checkPositionIndex 判断下标是否越界,index >= 0 && index <= size index 是否在 0 ~ size范围之内。
如果index等于 size,和 add(E e) 操作一样,都是添加在链表尾部。 如果index小于 size,调用 linkBefore 方法,往链表中间插入节点。首先看 node 方法:
Nodenode(int index) { // assert isElementIndex(index); // size >> 1 表示 size 右移一位,就是 size/2 size的一半 // index 小于 size 的一半,从首节点往后遍历 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; // index 大于 size 的一半,从最后一个节点往前遍历 } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
node() 方法就是找到 index 对应的 node 节点。
比如一个长度为5的链表:
node(1) 从 first 节点(第0个节点)往后遍历一个,也就是1对应的节点。 node(3) 从 last 节点(第4个节点)往前遍历一个,也就是3对应的节点。
通过下标找到节点,链表一般是需要遍历一遍,这里最多需要遍历一半的链表,主要是利用了双链表的特性,既可以从前往后遍历,又可以从后往前遍历。
size>>1 表示size/2,判断 index 是在链表的前半部分还是后半部分,如果在前半部分就从首节点往后遍历,如果在后半部分就从最后一个节点往前遍历,,这样最多遍历size的一半,避免遍历整个链表。找到index下的节点之后,再看 linkedBefore 方法:
void linkBefore(E e, Nodesucc) { // assert succ != null; // 记录前置节点 pred final Node pred = succ.prev; // 创建新节点,新节点的pre指向 pred,next指向succ节点 final Node newNode = new Node<>(pred, e, succ); // succ pre指向新节点 succ.prev = newNode; // 如果pred为空,表示succ就是首节点,新节点赋为首节点 if (pred == null) first = newNode; else // pred的next 指向新节点 pred.next = newNode; size++; modCount++; }
-
记录succ节点的前置节点 pred。
-
新建节点,pre指向pred,next指向succ。
-
succ的pre 指向新节点。
-
如果pred 为null,表示首节点是succ,将节点赋值给first节点。
-
如果pred 不为null,pred的next指向新节点。
比如一个长度为5的链表,在下标为1的位置添加数据:
获取数据获取数据主要有get、getFirst、getLast。
get 方法主要是通过 node 方法下标的节点,获取节点的 item 数据。
getFirst 方法获取首节点的item。
getLast 方法获取尾结点的item。
删除数据 remove(Object o)从列表中删除第一个匹配的元素
public boolean remove(Object o) {
// 判断是否为null
if (o == null) {
// 遍历node
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 遍历node
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
删除指定元素,需要判断元素是否为null。
-
如果为null,就使用x.item == null语句判断。
-
如果不为null,就使用o.equals(x.item)语句判断。
然后再调用unlink方法:
E unlink(Nodex) { // assert x != null; // 记录节点element、next和prev final E element = x.item; final Node next = x.next; final Node prev = x.prev; // prev为null,next 赋为首节点 if (prev == null) { first = next; } else { // prev的next指向next节点 prev.next = next; // x节点prev置为null x.prev = null; } // next为null,prev赋为尾节点 if (next == null) { last = prev; } else { // next的prev指向prev next.prev = prev; // x节点next置为null x.next = null; } // x.item置为null x.item = null; // 长度自减 size--; modCount++; return element; }
如图,要删除1数据的节点:
remove(int index)删除指定下标的数据:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
首先通过 node找到对应下标的节点,再调用unlink删除数据即可。



