【Java数据结构】通过Java理解和实现——无头双向链表

????无头双向链表

????双链表概念及结构

????无头双向非循环链表接口实现（注释非常详细，我????????都能看懂）

????打印双链表

????头插法插入

????尾插法插入

????查找是否包含关键字key在双链表当中

????得到双链表的长度

????任意位置插入,第一个数据节点为0号下标

????删除第一次出现关键字为key的节点

????删除所有值为key的节点

????清空链表

????单链表和双链表到底有啥区别

????无头双向链表

????双链表概念及结构

【为什么引入双链表？】

 单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

 双链表的结点中有两个指针prev和next，分别指向前驱结点和后继结点。

????无头双向非循环链表接口实现（注释非常详细，我????????都能看懂）

????打印双链表

????头插法插入

????尾插法插入

????查找是否包含关键字key在双链表当中

????得到双链表的长度

????任意位置插入,第一个数据节点为0号下标

????删除第一次出现关键字为key的节点

首先判断头结点是否为null（链表是否为空），然后找要删除的节点，要删除的节点有三种情况

①关键字在头节点：将头节点下一个节点设置为新头节点

②关键字在尾巴结点：将尾节点上一个节点设置为新尾节点

③关键字不在头结点：则将key节点的前一个节点的后驱指向key节点的后一个节点，key节点的后一节点的前驱指向key节点前一节点

????删除所有值为key的节点

????清空链表

????单链表和双链表到底有啥区别

一、指代不同

1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针，分别指向直接后继和直接前驱

2、单向链表：是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

二、优点不同

1、双向链表：从双向链表中的任意一个结点开始，都可以很方便地访问前驱结点和后继结点。

2、单向链表：单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小，结点的访问方便，可以通过循环或者递归的方法访问到任意数据。

三、缺点不同

1、双向链表：增加删除节点复杂，需要多分配一个指针存储空间。

2、单向链表：结点的删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线性表。