关于面试:面试官你给我讲一下LinkedList源码吧网友这不是章口就来吗

一.LinkedList数据结构

1.1 数据结构

LinkedList 底层数据结构是一个双向链表,整体构造如下图所示:

注意事项:
  • 链表每个节点叫做 Node,Node 有 prev 属性,代表前一个节点的地位,next 属性,代表后一个节点的位 置
  • first 是双向链表的头节点,它的前一个节点是 null。
  • last 是双向链表的尾节点,它的后一个节点是 null;
  • 当链表中没有数据时,first 和 last 是同一个节点,前后指向都是 null;
  • 因为是个双向链表,是没有大小限度的。

1.2 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.1 LinkedList类正文解析

  • 应用“双向链表”来实现List与Deque接口。 实现了所有List接口中的办法,并且容许寄存所有元素,包含Null。
  • 所有的操作都可通过双向链表实现。通过从结尾或者结尾遍历汇合,去靠近要操作的那个元素。
  • 是非线程平安的,多线程状况下,举荐应用线程安全类:Collections#synchronizedList
  • 加强 for 循环,或者应用迭代器迭代过程中,如果数组大小被扭转,会疾速失败,抛出异样。

2.2 新增

源码解析:

​ 新增节点时,咱们能够抉择追加到链表头部,还是追加到链表尾部,add 办法默认是从尾部开始追加,addFirst 方

法是从头部开始追加:

增加:
 /**
     * 将元素增加到链表尾部,等于addFirst 
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
从尾部减少:
    /**
     *  从尾部开始追加节点
     */
    void linkLast(E e) {
        // 把尾节点数据暂存
        final Node<E> l = last;
        // 新建新的节点,初始化入参含意: 
        // l 是新节点的前一个节点,以后值是尾节点值 
        // e 示意以后新增节点,以后新增节点后一个节点是 null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将新建节点追加到尾部
        last = newNode;
        //如果链表为空 l 是尾节点,尾节点为空,链表即空,头部和尾部是同一个节点,都是新建的节点
        if (l == null)
            first = newNode;
        else
        //否则把前尾节点的下一个节点,指向以后尾节点。
            l.next = newNode;
        //大小和版本更改
        size++;
        modCount++;
    }
从头部减少:
    /**
     *从头部开始追加节点
     */
    private void linkFirst(E e) {
         // 把头节点数据暂存
        final Node<E> f = first;
        // 新建新的节点,初始化入参含意: 
        // l 是新节点的前一个节点,以后值是尾节点值 
        // f 示意以后新增节点,以后新增节点后一个节点是 null
        final Node<E> newNode = new Node<>(null, e, f);
         // 将新建节点追加到头部
        first = newNode;
        //如果链表为空 f 是头节点,头节点为空,链表即空,头部和尾部是同一个节点,都是新建的节点
        if (f == null)
            last = newNode;
        else
        //上一个头节点的前一个节点指向以后节点
            f.prev = newNode;
        size++;
        modCount++;
    }

注意事项:

  • 头部追加节点和尾部追加节点,只是前者是挪动头节点的 prev 指向,后者是挪动尾节点的 next 指向,两者区别不大。

2.3 删除实现

源码解析:

LinkedList节点删除的形式和追加相似,咱们能够抉择从头部删除,也能够抉择从尾部删除,删除操作会把节点的值,前后指

向节点都置为 null。

从头部删除:
  /**
     * 从头部开始删除节点
     */
    private E unlinkFirst(Node<E> f) {
        //拿出头节点的值,作为办法的返回值
        final E element = f.item;
        // 拿出头节点的下一个节点
        final Node<E> next = f.next;
        //帮忙 GC 回收头节点
        f.item = null;
        f.next = null; 
        //头节点的下一个节点成为头节点
        first = next;
        //如果 next 为空,表明链表为空
        if (next == null)
            last = null;
        else
        //链表不为空,头节点的前一个节点指向 null
            next.prev = null;
        //批改链表大小和版本
        size--;
        modCount++;
        return element;
    }
从尾部删除:
/**
 * 和从头部删除基本一致
 */
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;
}

注意事项:

  • 前后指向节点都置为 null,是为了帮忙 GC 进行回收;
  • 从源码中咱们能够理解到,链表构造的节点新增、删除仅仅把前后节点的指向批改了, 所以LinkedList新增和删除度很快。

2.4 实现查问

查问:
/**
 * 依据链表索引地位查问节点
 */
Node<E> node(int index) {
    //  如果 index 处于队列的前半部分,从头开始找,size >> 1 是 size 除以 2 的意思。
    if (index < (size >> 1)) {
        Node<E> x = first;
   // 直到 for 循环到 index 的前一个 node 进行
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
      // 如果 index 处于队列的后半局部,从尾开始找
        Node<E> x = last;
      // 直到 for 循环到 index 的后一个 node 进行
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
注意事项:

​ LinkedList 并没有采纳从头循环到尾的做法,而是采取了二分法,首先看 index 是在链表的前半部分,还是后半局部。如果是前半部分,就从头开始寻找,反之亦然。通过这种形式,使循环的次数 至多升高了一半,进步了查找的性能。

三.工夫复杂度

get() 获取第几个元素,顺次遍历,复杂度O(n)
add(E) 增加到开端,复杂度O(1)
add(index, E) 增加第几个元素后,须要先查找到第几个元素,间接指针指向操作,复杂度O(n) (这个比拟容易想错)
remove()删除元素,间接指针指向操作,复杂度O(1)

四.线程平安

4.1 线程平安问题

只有当 LinkedList作为共享变量时,才会有线程平安问题,当 LinkedList是办法内的局部变量时,是没有线程平安的问题的。

LinkedList有线程平安问题的起因,是因为 LinkedList本身的 size、modConut 在进行各种操作时,都没有加锁,而且这些变量的类型并非是可见(volatile)的,所以如果多个线程对这些变量进行操作时,可能会有值被笼罩的状况。

类正文中举荐应用 Collections#synchronizedList 来保障线程平安,SynchronizedList 是通过在每个办法下面加上锁来实现,尽管实现了线程平安,然而性能大大降低,具体实现源码:

public boolean add(E e) {
    synchronized (mutex) {return c.add(e);}
}

咱们也能够应用ConcurrentLinkedQueue来保障线程平安,

五.总结

LinkedList的底层是链表构造 ,实用于适宜于常常新增和删除的场景,
欢送关注公众号:前程有光,支付一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java外围知识点总结! 这些材料的内容都是面试时面试官必问的知识点,篇章包含了很多知识点,其中包含了有基础知识、Java汇合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理