LinkedList
底层基于链表实现,增删不需要移动数据,所以效率很高。但是查询和修改数据的效率低,不能像数组那样根据下标快速的定位到数据,需要一个一个遍历数据。
基本结构
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;
}
}
结构如下图所示:
这是一个双链表的结构,有 prev
前置指针和next
后置指针。
还有首节点first
、尾节点last
、长度size
:
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
添加数据
LinkedList添加元素有两个方法:add(E e) 和 add(int index,E e)。
- add(E e) 是在链表的尾部添加数据
- add(int index,E e) 在指定链表位置添加数据
add(E e)
add
方法调用了 linkLast
方法:
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast
表示在链表最后添加指定元素:
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 自增
size++;
modCount++;
}
- 记录原尾部节点 l
- 创建新的节点,前置指向原尾部节点。
- 如果 l 为空,更新头部节点
- 更新尾部节点
- 如果 l 不为空,l 的后置指针指向新节点
如果原尾部节点为空,直接创建一个节点,这个节点是last
和first
节点。
如果原尾部节点不为空,创建新节点,新节点的前置指向原来的last,原来的last的next指向新节点。
add
在链尾添加数据,添加前后指针。以及更新为last
节点。
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
方法:
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1 表示 size 右移一位,就是 size/2 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()
方法就是找到 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, Node<E> succ) {
// assert succ != null;
// 记录前置节点 pred
final Node<E> pred = succ.prev;
// 创建新节点,新节点的pre指向 pred,next指向succ节点
final Node<E> 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<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 遍历node
for (Node<E> 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(Node<E> x) {
// assert x != null;
// 记录节点element、next和prev
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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
删除数据即可。
总结
-
LinkedList
是一个双链表的数据格式,为了支持双链表结构,有头节点,尾节点以及size大小。 -
add(E e)
直接添加在队列尾部,新节点prev 指向尾节点,尾节点指向新节点。 -
add(int index,E e)
如果添加位置等于链表长度,直接在链表尾节点添加数据。否则在链表中间添加数据。- 在链表中间添加数据首先要通过
node
方法获取数据,node
巧妙的判断index
和size
一半长度的关系,小于就从前往后遍历,大于就从后往前遍历。无需遍历整个链表。 - 找到节点之后,记录节点的
prev
节点,在prev
和节点之间创建新的节点。
- 在链表中间添加数据首先要通过
-
remove(Object o)
,遍历找到元素,再调用unlink
方法。记录元素的前置节点prev
和后置节点next
,前置节点next
指向后置节点,后置节点的next指向前置节点,删除其它的前置节点和后置节点的指针。 -
remove(int index)
,先通过node
方法找到下标的数据,找到元素之后,再调用unlink
方法。
本文由mdnice多平台发布
网友评论