关于java-se:Java-LinkedList-简单源码分析节选

35次阅读

共计 7782 个字符，预计需要花费 20 分钟才能阅读完成。

写在最后面

这个我的项目是从 20 年末就立好的 flag，通过几年的学习，回过头再去看很多知识点又有新的了解。所以趁着找实习的筹备，联合以前的学习储备，创立一个次要针对应届生和初学者的 Java 开源常识我的项目，专一 Java 后端面试题 + 解析 + 重点常识详解 + 精选文章的开源我的项目，心愿它能随同你我始终提高！

阐明：此我的项目内容参考了诸多博主（已注明出处），材料，N 本书籍，以及联合本人了解，从新绘图，从新组织语言等等所制。集体之力菲薄，或有不足之处，在劫难逃，但更新 / 欠缺会始终进行。大家的每一个 Star 都是对我的激励！心愿大家能喜爱。

注：所有波及图片未应用网络图床，文章等均开源提供给大家。

我的项目名: Java-Ideal-Interview

Github 地址：Java-Ideal-Interview – Github

Gitee 地址：Java-Ideal-Interview – Gitee（码云）

继续更新中，在线浏览将会在前期提供，若认为 Gitee 或 Github 浏览不便，可克隆到本地配合 Typora 等编辑器舒服浏览

若 Github 克隆速度过慢，可抉择应用国内 Gitee 仓库

  • LinkedList 源码剖析

    • 1. LinkedList 概述

      • 1.1 List 是什么？
      • 1.2 LinkedList 是什么？

    • 2. 源码剖析

      • 2.1 类申明
      • 2.2 成员
      • 2.3 外部公有类 Node 类
      • 2.4 构造方法

      • 2.5 增加办法

        • 2.5.1 add(E e)
        • 2.5.2 add(int index, E element)
        • 2.5.3 addLast(E e)
        • 2.5.4 addFirst(E e)
        • 2.5.5 addAll(Collection c)

      • 2.6 获取办法

        • 2.6.1 get(int index)
        • 2.6.2 获取头结点办法
        • 2.6.3 获取尾节点办法

        • 2.6.4 依据对象失去索引

          • 2.6.4.1 从头到尾找
          • 2.6.4.1 从尾到头找
        • 2.6.5 contains(Object o)

      • 2.7 删除办法

        • 2.7.1 remove(int index)
        • 2.7.2 remove(Object o)
        • 2.7.3 删除头结点

LinkedList 源码剖析

1. LinkedList 概述

1.1 List 是什么？

List 在 Collection 中充当着一个什么样的身份呢？——有序的 collection(也称为序列)

实现这个接口的用户以对列表中每个元素的插入地位进行准确地管制。用户能够依据元素的整数索引（在列表中的地位）拜访元素，并搜寻列表中的元素。与 set 不同，列表通常容许反复的元素。

1.2 LinkedList 是什么？

LinkedList 的实质就是一个 双向链表，然而它也能够被当做堆栈、队列或双端队列进行操作。

其特点为：查问慢，增删快，线程不平安，效率高。

2. 源码剖析

2.1 类申明

先来看一下类的申明，有一个继承（抽象类）和四个接口关系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 源码具体内容...}
  • Deque<E> 它实现了 Deque 接口，使得 LinkedList 类也具备队列的个性
  • Cloneable：实现它就能够进行克隆（clone()）
  • java.io.Serializable：实现它意味着反对序列化，满足了序列化传输的条件

2.2 成员

// 汇合的长度
transient int size = 0;

// 双向链表头部节点
transient Node<E> first;

// 双向链表尾部节点
transient Node<E> last;

2.3 外部公有类 Node 类

从源码刚开始就提到了 transient Node<E> first; 等内容，这里就波及到一个外部公有的类，即 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;
    }
}

2.4 构造方法

/**
 * 无参结构
 */
public LinkedList() {}

/**
 * 带参结构，创立一个蕴含汇合 c 的 LinkedList
 */
public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

2.5 增加办法

2.5.1 add(E e)

public boolean add(E e) {linkLast(e);
    return true;
}

间接跳转到 linkLast 办法中

/**
 * 链接使 e 作为最初一个元素
 */
void linkLast(E e) {
    // 拿到以后的尾部节点 last
    final Node<E> l = last;
    // new 一个节点进去，通过带参结构赋值，达到增加到尾部的成果
    final Node<E> newNode = new Node<>(l, e, null);
    // 此时不论这个链表只有一个还是多个元素它都是尾部节点
    last = newNode;
    // 依据判断做出不同的操作
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

不同状况的探讨

  • 以后链表为空，增加进来的 node 节点天然就是 first，也是 last，也正因为这一点，在滴啊参构造函数赋值的时候，就曾经确定了其 prev 和 next 都为 null
  • 以后链表不为空，那么增加进来的 node 节点就是 last，node 的 prev 指向以前的最初一个元素（旧的 last），node 的 next，天然也是 null

2.5.2 add(int index, E element)

/**
 * 在指定 index 地位增加元素
 */
public void add(int index, E element) {// 跳转，查看索引是否处于 [0-size] 之间
    checkPositionIndex(index);
    // 指定下标在尾部，间接调用 linkLast 放在尾部
    if (index == size)
        linkLast(element);
    else
        // 增加在链表两头
        linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}
  • 调用 linkBefore(element, node(index))办法中，须要调用 node(int index) 通过传入的 index 来定位到要插入的地位，这个是比拟耗时间的
/**
 * 在一个非空节点前插入一个元素
 */
void linkBefore(E e, Node<E> succ) {
    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++;
}

其实这里和后面 add 到开端是没什么区别的，只是多了一个定位插入地位的过程。

2.5.3 addLast(E e)

不解释了，和 add(E e) 是一样的，将元素增加到链表尾部

public void addLast(E e) {linkLast(e);
}

2.5.4 addFirst(E e)

/**
 * 将元素增加到链表头部
 */
private void linkFirst(E e) {
    // 拿到以后链表的头部节点
    final Node<E> f = first;
    // 以头节点做为后继节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        // 将头节点的前驱指针指向新节点，也就是指向前一个元素
        f.prev = newNode;
    size++;
    modCount++;
}

如果有了 add(E e) 的了解，就会发现这些都是一回事，这里先拿到的是头部节点，而后再带参构造函数赋值的时候，以头节点做为后继节点

  • 如果链表为空，则头尾部节点就都是这个新节点 newNode
  • 如果不为空，则将头节点的前驱指针指向新节点，也就是指向前一个元素

2.5.5 addAll(Collection c)

/**
 * 将汇合插入到链表尾部
 */
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}

来间接跳转到逻辑办法中去，addAll(int index, Collection c)

/**
 * 将汇合从指定地位开始插入
 */
public boolean addAll(int index, Collection<? extends E> c) {// 跳转，查看索引是否处于 [0-size] 之间
    checkPositionIndex(index);
    
    // 把汇合转成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    
    // 获取插入地位的前驱和后驱节点
    Node<E> pred, succ;
    // 如果插入地位为尾部。前驱结点天然是尾部节点，后继没有了就是 null
    if (index == size) {
        succ = null;
        pred = last;
    // 插入地位非尾部，则先通过 node 办法失去后继节点，再拿到前驱结点
    } else {succ = node(index);
        pred = succ.prev;
    }
    
    // 遍历插入数据
    for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
        // 创立新节点
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果插在头部
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    // 如果插入在尾部，重置一下 last 节点
    if (succ == null) {last = pred;} else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

2.6 获取办法

2.6.1 get(int index)

/**
 *  依据指定索引返回元素
 */
public E get(int index) {
    // 查看 index 范畴是否在 size 之内
    checkElementIndex(index);
    // 通过 node 办法找到对应的节点而后返回它的值
    return node(index).item;
}


Node<E> node(int 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;
    }
}

2.6.2 获取头结点办法

public E getFirst() {
    final Node<E> f = first;
    // 为空抛异样
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E element() {
    // 为空抛异样
    return getFirst();}

public E peek() {
    final Node<E> f = first;
    // 为空返回 null
    return (f == null) ? null : f.item;
}

public E peekFirst() {
    final Node<E> f = first;
    / 为空返回 null
    return (f == null) ? null : f.item;
}

2.6.3 获取尾节点办法

public E getLast() {
    final Node<E> l = last;
    // 为空返回 null
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

public E peekLast() {
    final Node<E> l = last;
    // 为空返回 null
    return (l == null) ? null : l.item;
}

2.6.4 依据对象失去索引

2.6.4.1 从头到尾找
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        // 从 first 遍历 -> next
        for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 从 first 遍历 -> next
        for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
2.6.4.1 从尾到头找
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        // 从 last 遍历 -> prev
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        // 从 last 遍历 -> prev
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

2.6.5 contains(Object o)

/**
 *  查看对象 o 是否存在于此链表中
 */
public boolean contains(Object o) {return indexOf(o) != -1;
}

2.7 删除办法

2.7.1 remove(int index)

/**
 *  删除指定下标元素
 */
public E remove(int index) {
    // 查看 index 范畴
    checkElementIndex(index);
    // 先用 node 找到节点，而后将节点删除
    return unlink(node(index));
}

2.7.2 remove(Object o)

/**
 *  删除指定元素
 */
public boolean remove(Object o) {
    // 如果为 null
    if (o == null) {
        // 从 first 开始遍历
        for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {
                // 从链表中移除找到的元素
                unlink(x);
                return true;
            }
        }
    } else {
        // 从 first 开始遍历
        for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {
                // 从链表中移除找到的元素
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

其中调用了 unlink(Node<E> x) 办法，来看一下

E unlink(Node<E> x) {
    final E element = x.item;
    // 失去后继节点
    final Node<E> next = x.next;
    // 失去前驱节点
    final Node<E> prev = x.prev;

    // 如果删除的节点是头节点
    if (prev == null) {
        // 令头节点指向该节点的后继节点
        first = next;
    } else {
        // 不是头结点的话，将前驱节点的后继节点指向后继节点
        prev.next = next;
        x.prev = null;
    }

    // 如果删除的节点是尾节点
    if (next == null) {
        // 令尾节点指向该节点的前驱节点
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

2.7.3 删除头结点

几个办法套娃，最初都是调用的 unlinkFirst() 办法

public E pop() {return removeFirst();
}

public E remove() {return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 取出头结点中的值，用于办法返回
    final E element = f.item;
    // 取出头结点的下一个节点的援用并赋予变量 next
    final Node<E> next = f.next;
    // 将头结点的 item 以及 next 属性设为 null，帮忙垃圾回收
    f.item = null;
    f.next = null; // help GC
    // 将 next 赋予 first（将原先节点下一个节点变为头结点）first = next;
    // 判断 next 是否为空，如果为空，则阐明原先汇合中只有一个元素，须要将 last 设置为 null
    if (next == null)
        last = null;
    else
        // 如果 next 不为空，则将 next 的 prev 设置为 null（因为 prev 指向原先的头结点，头节点的 prev 值必定为 null）next.prev = null;
    size--;
    modCount++;
    return element;
}

2.7.4 删除尾结点

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

// 与下面 unlinkFirst 同理
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

正文完
java-se
发表至： java-se
2021-02-21
 0
关于java-se:JAVASEBasic基础数据运算符分支循环结构数组
关于java-se:注解和反射
关于java-se:Java-HashMap源码分析含散列表红黑树扰动函数等重点问题分析
关于java-se:Java-LinkedList-简单源码分析节选