【数据结构】双向链表的模拟实现（无头）
目录
前言：
1、认识双向链表中的结点
2、认识并创建无头双向链表
3、实现双向链表当中的一些方法
3.1、遍历输出方法（display）
3.2、得到链表的长度（size）
3.3、查找关键字key是否包含在双链表中(contains)
3.4、头插法（addFirst）
【代码思路】
【代码实现】
3.5、尾插法 （addIndex）
【代码思路】
【代码实现】
3.6、任意位置插入 ，第一个数据结点为0号下标（addIndex）
【代码思路】
【代码示例】
3.7、 删除第一次出现关键字key的结点(remove)
【代码思路】
第一种情况，删除头节点。
【代码示例】
3.8、删除所有值为key的结点（removeAllKey）
【代码思路】
【代码示例】
3.9、清空双向链表（clear）
【代码思路】
【代码示例】
前言：
单向链表能够解决逻辑关系为"一对一"数据的存储问题，但是在解决某些特殊问题的时候，单链表并不是效率最有的存储结构。比如，需要找某个节点的前驱节点，使用单链表并不合适，单链表更适合"从前往后"找，而"从后往前"找并不是单链表的强项。这里就要使用双向链表来解决这类问题。
1、认识双向链表中的结点
双向链表中的结点有两个指针域和一个数据域，一个指针指向前驱结点，一个指向后继节点。（双向链表当中第一个结点的prev为null，最后一个结点的next为null）
2、认识并创建无头双向链表
在Java当中，双链表相比于单链表增加了一个引用last，last永远指向双链表的最后一个结点。
创建链表类
public class MyLinkedList {static class ListNode{//结点类public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val){this.val = val;}}public ListNode head;public ListNode last;//指向双向链表的结尾
}3、实现双向链表当中的一些方法
以下这些方法写在MyLinkdeList类当中
3.1、遍历输出方法（display）
public void display(){ListNode cur = head;while(cur != null){//说明cur还没有遍历完这个链表System.out.print(cur.val+" ");cur = cur.next;}System.out.println();//当整体输出完成之后换行，下一次打印的时候在下一行}
3.2、得到链表的长度（size）
public int size(){ListNode cur = head;int len = 0;while(cur != null){len++;//因为cur是从head向后遍历，先通过len++将head计算在内cur = cur.next;}return len;}
3.3、查找关键字key是否包含在双链表中(contains)
public Boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){//如果cur在遍历的过程中找到了return true;}cur = cur.next;//没有找到就向后走}return false;//遍历完还没找到返回false}3.4、头插法（addFirst）
【代码思路】
头插法存在两种情况
【代码实现】
public void addFirst(int data){ListNode node = new ListNode(data);//创建一个新的结点if(head == null){//如果链表为空，插入结点之后，头和尾都指向nodehead = node;last = node;}else{//如果链表不为空。先连接后继，再链接前驱，最后将head前移node.next = head;head.prev = node;head = node;}}3.5、尾插法 （addIndex）
【代码思路】
尾插法存在两种情况。
【代码实现】
public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{last.next = node;node.prev = last;last = node;}}❗❗❗ 总结：
单链表的时间复杂度为O(N)，而双链表的时间复杂度为O(1)。
3.6、任意位置插入 ，第一个数据结点为0号下标（addIndex）
【代码思路】
【代码示例】
public void addIndex(int index,int data){if(index < 0 || index >size()){//检查位置的合法性return;//这里可以抛异常，也可以直接return}if(index == 0){//在链表的开头插入结点addFirst(data);return;}if(index == size()){//再链表的结尾插入结点addLast(data);return;}ListNode node = new ListNode(data);//创建一个新的结点ListNode cur = findIndex(index);//通过调用这个方法，找到要插入的位置node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//通过这个方法来找要插入的位置private ListNode findIndex(int index){ListNode cur = head;while(index != 0){//从头开始遍历链表。cur = cur.next;index--;}return cur;}3.7、 删除第一次出现关键字key的结点(remove)
【代码思路】
第一种情况，删除头节点。
第二种和第三种情况，删除中间节点和结尾
【代码示例】
public void remove(int key){ListNode cur = head;while(cur != null){//开始删除了if(cur.val == key){//1、删除的是头节点if(cur == head){head = head.next;//head向后移//处理链表只有一个结点的情况if(head != null) {head.prev = null;//将head的前驱置为空}}else{//删除的是中间和结尾cur.prev.next = cur.next;//2、删除中间结点if(cur.next != null){cur.next.prev = cur.next;//3、删除尾巴结点}else{last = cur.prev;}}return;//这个return对应的是第2个if，找到一个与key值相等的结点，删除之后，就返回，只删一个与key值相等的结点}cur = cur.next;//对应最开始的if，若是要和删除的key不相同，继续向后走}}3.8、删除所有值为key的结点（removeAllKey）
【代码思路】
当写出删除一个值为key的结点的代码，那么删除所有值为key的结点的代码，就非常简单了，只需要将上述代码中的return去掉就可以了。让上述的代码从头跑到结尾就行，这样cur在遍历链表的时候，也只是遍历了一遍，就将所有与key值相等的结点就删除完了。他的时间复杂度为O(N).
【代码示例】
public void removeAllKey(int key){ListNode cur = head;while(cur != null){//开始删除了if(cur.val == key){//1、删除的是头节点if(cur == head){head = head.next;//head向后移//处理链表只有一个结点的情况if(head != null) {head.prev = null;//将head的前驱置为空}}else{//删除的是中间和结尾cur.prev.next = cur.next;//2、删除中间结点if(cur.next != null){cur.next.prev = cur.next;//3、删除尾巴结点}else{last = cur.prev;}}}cur = cur.next;}}3.9、清空双向链表（clear）
这里很多人会想到将head和last直接置为空，不让head引用和last引用，引用链表的节点即可，但是head所引用的结点的后继结点，还引用这个结点，last所引用的结点的前驱结点，还引用这个结点。所以这样的操作还是不能将链表清空，必须要将双向链表的所有结点的指针域清空。
【代码思路】
【代码示例】
public void clear(){ListNode cur = head;while(cur != null){//将每个结点的指针域都置为空，由于这里的数据域是基本数据类型，不用置空，但是当数据域当中为引用数据类型的时候，数据域还要置空ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;//因为head和last作为引用，还在引用链表的第一个结点和最后一个结点。last = null;}