3.Java SDK源码分析系列笔记-LinkedList
目录[*]1. 是什么
[*]2. 如何使用
[*]3. 原理分析
[*]3.1. uml
[*]3.2. 构造方法
[*]3.2.1. 队列的节点Node
[*]3.3. add方法
[*]3.3.1. 插入到链表尾部
[*]3.3.2. 构造新节点【prev指向尾节点，next为null】
[*]3.3.3. 更新尾节点
[*]3.3.4. 更新size
[*]3.4. addLast方法
[*]3.5. addFirst方法
[*]3.5.1. 头部插入节点
[*]3.5.2. 构造新节点【prev指向null，next指向头节点】
[*]3.5.3. 更新头节点
[*]3.5.4. 更新size
[*]3.6. remove方法【根据下标删除】
[*]3.6.1. 遍历找到这个位置的元素
[*]3.6.2. 更新该节点前后节点的指针
[*]3.7. remove方法【按照元素删除】
[*]3.7.1. 遍历找到这个元素
[*]3.7.2. 更新该节点前后节点的指针
[*]3.8. remove方法【无参】
[*]3.8.1. 删除头部节点
[*]3.8.2. 把原来头节点的next节点更新为头节点
[*]3.9. removeLast方法
[*]3.9.1. 把原来尾节点的prev节点更新为尾节点
1. 是什么
底层由双向链表实现的顺序表
有序、可以重复
2. 如何使用
public class LinkedListTest
{
public static void main(String[] args)
{
LinkedList<String> list = new LinkedList<>();
list.add("1");
list.add("2");
list.addFirst("3");
list.addLast("4");
System.out.println(list);
list.remove(0);
list.remove("2");
list.remove();
list.removeFirst();
list.removeLast();
}
}3. 原理分析
3.1. uml
可以看出LinkedList是个List、双端队列、可序列化、可克隆
3.2. 构造方法
由头节点、尾节点、长度构成
public class LinkedList<E>
extends AbstractSequentialList<E>//提供了List的骨架实现
implements List<E>/*List接口*/, Deque<E>/*双端队列*/, Cloneable, java.io.Serializable
{
//属性
transient int size = 0;//长度
transient Node<E> first;//头节点
transient Node<E> last;//尾节点
//构造方法
public LinkedList() {
}
}3.2.1. 队列的节点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;
}
}结构如下图：
3.3. add方法
[*]O（1）
public boolean add(E e) {
//调用linkLast方法
linkLast(e);
return true;
}3.3.1. 插入到链表尾部
[*]linkLast
void linkLast(E e) {
//保存尾节点
final Node<E> l = last;
//构造新的节点，prev指向last节点
final Node<E> newNode = new Node<>(l, e, null);
//把尾节点更新为新的节点
last = newNode;
//如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点
if (l == null)
first = newNode;
else
//否则更新尾节点的next为新的节点
l.next = newNode;
size++;
modCount++;
}3.3.2. 构造新节点【prev指向尾节点，next为null】
//保存尾节点
final Node<E> l = last;
//构造新的节点，prev指向last节点
final Node<E> newNode = new Node<>(l, e, null);3.3.3. 更新尾节点
//如果原来的尾节点为空，那么是第一个节点。此时更新first为新节点
if (l == null)
first = newNode;
else
//否则更新尾节点的next为新的节点
l.next = newNode;3.3.4. 更新size
size++;3.4. addLast方法
[*]O（1）
public void addLast(E e) {
//调用linkLast
linkLast(e);
}
[*]linkLast
参考add方法
3.5. addFirst方法
[*]O（1）
public void addFirst(E e) {
//简单的调用linkFirst
linkFirst(e);
}3.5.1. 头部插入节点
[*]linkFirst
private void linkFirst(E e) {
//先保存原头节点
final Node<E> f = first;
//新建节点，next指向原头节点
final Node<E> newNode = new Node<>(null, e, f);
//更新头节点为新的节点
first = newNode;
//如果原头节点为空，那么是第一个元素，更新last节点为新的节点
if (f == null)
last = newNode;
else
//否则更新原头节点的prev为新的节点
f.prev = newNode;
size++;
modCount++;
}3.5.2. 构造新节点【prev指向null，next指向头节点】
//先保存原头节点
final Node<E> f = first;
//新建节点，next指向原头节点
final Node<E> newNode = new Node<>(null, e, f);3.5.3. 更新头节点
//如果原头节点为空，那么是第一个元素，更新last节点为新的节点
if (f == null)
last = newNode;
else
//否则更新原头节点的prev为新的节点
f.prev = newNode;3.5.4. 更新size
size++;3.6. remove方法【根据下标删除】
[*]O（N）
[*]修改这个元素的前后元素的next和prev指针
public E remove(int index) {
//检查是否越界
checkElementIndex(index);
//根据下标找到相应的节点，并把这个节点删除
return unlink(node(index));
}
3.6.1. 遍历找到这个位置的元素
[*]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;
}
}3.6.2. 更新该节点前后节点的指针
E unlink(Node<E> x) {
// assert x != null;
//首先保存当前节点的prev，next，和item值
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//更新prev
if (prev == null) {
//前一个节点为空（说明当前节点是头节点），那么把first指向当前节点的下一个节点即可
first = next;
} else {
//前一个节点的next指向当前节点的下一个节点
prev.next = next;
//help gc
x.prev = null;
}
//更新next
if (next == null) {
//后一个节点为空（说明当前节点是尾节点），那么把last指向当前节点的上一个节点即可
last = prev;
} else {
//后一个节点的prev指向当前节点的上一个节点
next.prev = prev;
//help gc
x.next = null;
}
//help gc
x.item = null;
size--;//更新size
modCount++;
return element;
}3.7. remove方法【按照元素删除】
[*]O（N）
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;
}
}
//equals
} else {
//遍历找到node
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}3.7.1. 遍历找到这个元素
for (Node<E> x = first; x != null; x = x.next)
{
//...
}3.7.2. 更新该节点前后节点的指针
3.8. remove方法【无参】
[*]O（1）
public E remove() {
//简单调用removeFirst
return removeFirst();
}3.8.1. 删除头部节点
[*]removeFirst
public E removeFirst() {
//头节点
final Node<E> f = first;
if (f == null)
//为null直接抛出异常
throw new NoSuchElementException();
//调用unlinkFirst从链表删除头节点
return unlinkFirst(f);
}3.8.2. 把原来头节点的next节点更新为头节点
[*]unlinkFirst
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//保存item，next
final E element = f.item;
final Node<E> next = f.next;
// help GC
f.item = null;
f.next = null;
//first直接指向头节点的next
first = next;
//如果头节点的next为空，说明链表中只有一个节点
if (next == null)
//更新last指向null
last = null;
else
//否则更新头节点的next节点的prev指针
next.prev = null;
size--;
modCount++;
return element;
}3.9. removeLast方法
[*]O（1）
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}3.9.1. 把原来尾节点的prev节点更新为尾节点
[*]unlinkLast
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//保存尾节点的item值和prev
final E element = l.item;
final Node<E> prev = l.prev;
// help GC
l.item = null;
l.prev = null;
//更新last为原尾节点的prev
last = prev;
//只有一个元素
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]