关于java:一起探秘不可不知双向链表底层原理

双向链表与数据结构

引言
在上大节中
咱们剖析了ArrayList的底层实现，
晓得了ArrayList底层是基于数组实现的，因而具备查找批改快而插入、删除慢的特点
本章咱们介绍的LinkedList是List接口的另一种实现
它的底层是基于双向链表实现的
因而它具备插入、删除快而查找批改慢的特点

什么是LinkedList

LinkList是一个双向链表（双链表）；它是链表的一种，也是最常见的数据结构，其外部数据呈线性排列，属于线性表构造.

它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点，所以是双向链表.

LinkList特点：

链表: 劣势：不是间断的内存，轻易插入（前、两头、尾部）插入O(1) 劣势：查问慢O(N)

线程不平安的，容许为null，容许反复元素

蓝色示意；可随便插入、删除

查问循环循环链表

总结

双链表的节点既有指向下一个节节点的指针，也有指向上一个结点的指针（双向读）

所谓指针，就是指向其余节点的一个对象的援用（说白了就是定义了两个成员变量）

双向链表线程不平安的，容许为null，容许反复元素

查问O(n)

插入删除O(1)

1.2 双向链表继承关系

LinkedList 是一个继承于AbstractSequentialList的双向链表。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，能将LinkedList当作双端队列（double ended queue）应用。
LinkedList 实现了Cloneable接口，即笼罩了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList反对序列化，能通过序列化去传输。

1.3 双向链表源码深度分析

案例代码

com.llist.LList

package com.llist;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;

public class LList {

    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<String>();
        linkedList.add("100");//尾插,等价于 linkedList.addLast()
        linkedList.add("200");
        linkedList.add("300");
       //*******两头插入linkedList..add(3,"700")*************
        linkedList.add("400");
        linkedList.add("500");
        linkedList.add("600");
        System.out.println(linkedList);
        linkedList.add(3,"700");//两头插入
        System.out.println(linkedList);
        //*******批改***************************************
        linkedList.set(3,"700000000");
        System.out.println(linkedList);
        //*******查问***************************************
        System.out.println(linkedList.getFirst());//头查
        System.out.println(linkedList.getLast());//尾查
//        for(int s=0;s<linkedList.size();s++){
//            System.out.println(linkedList.get(s));//随机插
//        }

        //*******移除***************************************
        LinkedList<String> linkedListRemove = new LinkedList<String>();
        linkedListRemove.add("100");
        linkedListRemove.add("200");
        linkedListRemove.add("300");
        linkedListRemove.remove(1);//指定移除
        linkedListRemove.removeAll(linkedList);//也调用下面的unlink办法；LinkedList.ListItr.remove
    }

}

1.3.1 链表成员变量与外部类

咱们先来定义几个叫法，前面会用到它

    transient int size = 0;//元素个数
    transient Node<E> first;//头结点援用（查问时获取）
    transient Node<E> last;//尾节点援用（查问时获取）



    private static class Node<E> { //链表节点元素，封装了实在数据，同时退出了前后指针
        E item;//元素，这是放入的实在数据
        Node<E> next;//下一个节点，指针也是Node类型
        Node<E> prev;//上一个节点
      
                //结构器，前、值、后，很清晰
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//新元素
            this.next = next;//下个节点
            this.prev = prev;//上个节点
        }
    }

1.3.2 双向链表结构器

无参结构器: 没有做任何事件

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

有参结构器：传入内部汇合的结构器

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

机密就藏在addAll上（重点，画图展现）

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //边界判断

        Object[] a = c.toArray();  //不论你传啥类型，对立转成数组
        int numNew = a.length;  //须要新插入的个数
        if (numNew == 0)
            return false;
      
                //两个指针，这俩示意你要插入点的前后两个节点。咱们称之为前置node和后置node
          //比方你的index=2 ：  【 000  1111（pred） （index）  2222（succ） 33333 …… 】
        Node<E> pred, succ; 
        if (index == size) { //上面就要定位到这俩指针的地位
            succ = null; //如果指定的index和尾部相等，很显然后置是没有的
            pred = last; //前置就是最初一个元素last
        } else {
            succ = node(index);  //否则的话，后置就是以后index地位的node，这个办法上面有具体介绍先不论它
            pred = succ.prev;  //前置就是以后index地位的prev，很好了解
        }

        for (Object o : a) { //开始循环遍历插入元素
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);  //定义个新节点，包装以后元素
            if (pred == null)   //如果前置为空，留神什么时候才为空？只有头插或以后list没有元素的时候
                first = newNode; //阐明是第一次放入元素，将first指向以后元素，竣工
            else
                pred.next = newNode;  //否则的话，前置node的后指针指向以后元素（接上了）
            pred = newNode; //让前置指针后移，指向刚新建的node，为下一次循环做筹备
        } //顺次循环，往上接，接完后，pred就是最初一个插入的元素

          //全副循环接完当前，再来解决新接链条的后指针
        if (succ == null) { //如果后置是nul的话，阐明咱们始终在尾部插入
            last = pred; //将last指向最初一个插入的元素即可，它就是尾巴
        } else {
            pred.next = succ;  //否则的话，最初一个插入的next指向原来插入前的后置
            succ.prev = pred; //后置的前指针指向最初插入的元素，这两步是一对操作缺一不可
        } //到此为止，截断的后半截链条也对接上了。

        size += numNew;  //最初不要遗记，元素数量减少
        modCount++;  //操作计数器减少
        return true;
    }

1.3.3 链表插入（重点）

1）双向链表尾插法

1、add(E e)，

2、addLast；

调用的办法都一样（linkLast）

public boolean add(E e) {
    linkLast(e);//在链表尾部增加
    return true;
}

在链表尾部增加

  /**
     * 在链表尾部增加
     */
    void linkLast(E e) {
        final Node<E> l = last;//取出以后最初一个节点
        final Node<E> newNode = new Node<>(l, e, null); //创立一个新节点，留神其前驱节点为l
        last = newNode;//尾指针指向新节点
        if (l == null)//如果原来的尾巴节点为空，则示意链表为空，则将first节点也赋值为newNode
            first = newNode;
        else
            l.next = newNode; // 否则的话，将原尾巴节点的后指针指向新节点，形成双向环
        size++;// 计数
        modCount++; //计数
    }

论断：默认add就是尾插法，追加到尾部

2）双向链表两头插入

指标：将700插入到400的地位

插入前

插入后的

双向链表两头插入add(int index, E element)

//自定义插入
 linkedList.add(3,"700");

源码如下

    public void add(int index, E element) {
        checkPositionIndex(index);//越界查看

        if (index == size)//如果index就是指向的尾部，天然调尾插即可
            linkLast(element);
        else
            linkBefore(element, node(index));//否则的话，找到index地位的node，插队到它后面去
    }

        /**
     * 那它怎么找的呢？看以下办法（画图展现）
     */
    Node<E> node(int index) {
        // 这里有一个讨巧的设计！很灵便的利用了咱们的first和last

        if (index < (size >> 1)) { // index如果小于链表长度的1/2 （size右移1就是除以2）
            Node<E> x = first;
            for (int i = 0; i < index; i++) //从链表头开始挪动 index 次
                x = x.next; //顺次往后指
            return x;  //循环完后，就找到了index地位的node，返回即可
        } else { //  否则，阐明index在链表的后半截，咱们从链表尾部倒着往前找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) //始终循环，直到index地位
                x = x.prev;
            return x; //抓到后返回，竣工！
        }
    }

    //画图展现
    void linkBefore(E e, Node<E> succ) { //找到之后，也就是这里的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++;//个数加1
        modCount++;//批改次数加1 
    }

1.3.4 双向链表批改办法

非常简单！

找到包装值的node，批改掉外面的属性即可

public E set(int index, E element) {
    checkElementIndex(index);//越界查看
    Node<E> x = node(index);//通过链表索引找到node
    E oldVal = x.item;//获取原始值
    x.item = element;//新值赋值
    return oldVal;//返回老值
}

1.3.5 双向链表查询方法

简略！

get(int index)：依照下标获取元素；通用办法
getFirst()：获取第一个元素；特有办法，间接拿指针就是
getLast()：获取最初一个元素；特有办法，同样间接拿指针

    public E get(int index) {
        checkElementIndex(index);//越界查看
        return node(index).item;//找到原始数组对应index的node
    }

System.out.println(linkedList.getFirst());//头查

System.out.println(linkedList.getLast());//尾查

1.3.6 双向链表删除办法

remove(E e)：移除指定元素；通用办法

removeAll(Collection<?> c) 移除指定汇合的元素; 也调用的unlink办法

两步走：1找，2删

    public boolean remove(Object o) {
        if (o == null) { //如果要移除null元素
            for (Node<E> x = first; x != null; x = x.next) {  //从fist顺着链表往后找
                if (x.item == null) { //发现就干掉
                    unlink(x); //重点！干掉元素调用的其实是unlink办法
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {  //如果不是移除null的话，路子一个样，无非就是==换成equals判断
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 画图展现：将要移除的Node，比方【100】【200】【300】
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;//元素
        final Node<E> next = x.next;//下个节点
        final Node<E> prev = x.prev;//上个节点

        if (prev == null) {
            first = next;//上个为空，阐明以后要移除的就是头节点，将fist指针指向后置，我被移除后它降级为头了
        } else {
            prev.next = next;  //否则，前置的后指针指向后置
            x.prev = null; //以后节点的前指针切断！
        }

        if (next == null) {  
            last = prev;//后置为空阐明以后要移除的是尾节点，我被移除后，我的前置成为尾巴
        } else {
            next.prev = prev; //否则，后置的前指针指向前置节点
            x.next = null; //以后节点的后指针切断！
        }  //到这里前后指针就理清了，该断的断了，该接的接了

        x.item = null;// 把以后元素改成null，交给垃圾回收
        size--;//链表大小减一
        modCount++;//批改次数加一
        return element; //已删除元素
    }

本文由传智教育博学谷 – 狂野架构师教研团队公布，转载请注明出处！

如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源

关于java:一起探秘不可不知双向链表底层原理

双向链表与数据结构

1.2 双向链表继承关系

1.3 双向链表源码深度分析

1.3.1 链表成员变量与外部类

1.3.2 双向链表结构器

1.3.3 链表插入（重点）

1）双向链表尾插法

2）双向链表两头插入

1.3.4 双向链表批改办法

1.3.5 双向链表查询方法

1.3.6 双向链表删除办法

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:一起探秘不可不知双向链表底层原理

双向链表与数据结构

1.2 双向链表继承关系

1.3 双向链表源码深度分析

1.3.1 链表成员变量与外部类

1.3.2 双向链表结构器

1.3.3 链表插入（重点）

1） 双向链表尾插法

2）双向链表两头插入

1.3.4 双向链表批改办法

1.3.5 双向链表查询方法

1.3.6 双向链表删除办法

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

1）双向链表尾插法

发表回复取消回复