首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedList(2)

Java 容器源码分析之 LinkedList(2)

双向链表操作LinkedList 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在 双向链表的两端进行操作,也是基于对头和尾部元素的操作。总的来说,双向链表的操作并不复杂,下面简单地进行解析,大部分操作都是对以下几种操作的封装。
向头部添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//将一个元素加入双向链表的头部
private void linkFirst(E e) {
    final Node<E> f = first;
    //新节点的前驱节点为null,后继节点为原来的头节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) //原来的头节点为空
        //新加入的节点是第一个也是最后一个
        last = newNode;
    else
        //修改原来头节点的前驱指向
        f.prev = newNode;
    //调整链表大小
    size++;
    //修改计数器
    modCount++;
}
向尾部添加元素
1
2
3
4
5
6
7
8
9
10
11
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++;
}
从中间插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//在一个非空节点前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; //获取前驱
    //注意新建节点的前驱与后继
    final Node<E> newNode = new Node<>(pred, e, succ);
    //调整相关节点的前驱与后继关系
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    //修改大小
    size++;
    modCount++;
}
移除头部节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//将头节点从链表移除
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    //引用修改为null,方便GC
    f.item = null;
    f.next = null; // help GC
    //调整头节点
    first = next;
    if (next == null) //移除后链表为空
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
返回列表