LinkedList 源码分析 - 初始化 & 节点查询

2022 年 5 月 18 日
本文字数：1202 字
阅读完需：约 4 分钟

LinkedList 源码分析-初始化

LinkedList 底层是链表结构，适用于集合元素先入先出和先入后出的场景。

初始化

LinkedList 底层数据结构是一个双向链表，双向链表的特点：

链表每个节点我们叫做 Node
Node 有前节点(prev)，代表前一个节点的位置
Node 有后节点(next)，代表后一个节点的位置
first 是双向链表的头节点，它的前一个节点指向 null
last 是双向链表的尾节点，它的后一个节点指向 null
当链表中没有数据时，first 和 last 是同一个节点，前后都指向 null
链表中的每个节点都可以向前或者向后查询
双向链表按理说是没有内存大小限制的，当然也限于机器的配置

Node 的组成部分，源码：

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{    transient int size = 0;
    /**     * Pointer to first node.     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node<E> first;
    /**     * Pointer to last node.     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node<E> last;        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;        }    }            ......}

复制代码

E item;表示节点值
Node<E> next;表示下一个节点
Node<E> prev表示前一个节点
Node(Node<E> prev, E element, Node<E> next) 初始化参数：前一个节点、本身节点值、后一个节点

查询

链表查询是比较慢的，需要一个一个循环遍历查找，源码：

    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;        }    }

复制代码

if (index < (size >> 1))如果 index 处于队列的前半部分，从头开始找
for (int i = 0; i < index; i++)直到 for 循环到 index 的前一个 node 停止
for (int i = size - 1; i > index; i--)如果 index 处于队列的后半部分，从尾开始找,直到 for 循环到 index 的后一个 node 停止

LinkedList 的查询采取了简单二分法，先看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，如果在后半部分，则从后开始查找。此举可以将查询的平均次数减半。

发布于: 刚刚阅读数: 2

zarmnosaj

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

发布

暂无评论

创作场景

LinkedList 源码分析 - 初始化 & 节点查询

LinkedList 源码分析-初始化

初始化

查询

zarmnosaj

评论