双向链表的基本结构及功能实现
1.基本结构:
双向链表是一种链表数据结构，它由一系列节点组成，每个节点包含三个部分：
(1).数据域：存储节点的数据
(2).前驱指针:指向前一个节点
(3).后驱指针:指向下一个节点
2.基本特性：
双向链接: 与单向链表不同，双向链表的每个节点都可以向前和向后移动，这使得在链表中插入和删除节点更加灵活。
3.基本操作：
我们要实现的功能：
addFirst(头插) 、 addLast（尾插）、disPlay（展示）、size（数组长度）、contains（是否包含某个元素）、 index（在某个节点处插入某个元素）、remove（移除某个元素）、removeAllKey(移除所有符合元素)、clear（清除所有数据），当然这些方法都要在接口List中都要进行定义。
3.0 双向链表基本结构的实现：
（1）.包含基本结构：数据域、前驱指针、后驱指针
（2） 构造方法的实现：每个数据域对应的值输入（整数）
(3). 头节点、尾节点的定义。
具体代码如下：
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.1 头插方法的实现：
1.创建一个node 节点
2.判断头节点是否为空(链表是否为空)，为空的话，将头尾节点均置为空。
3. 插入元素：将node.next = head, head.prev = node
head = node;(更新头节点)
具体代码如下：
public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{node.next = head;head.prev = node;head = node;}}3.2 尾插方法的实现：
1.创建一个新节点node储存新元素
2.判断头节点是否为空
3.插入元素：
具体代码如下：
@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = last = null;}else{last.next = node;node.prev = last;last = last.next;}}3.3 disPlay方法的实现：
1.创建新节点cur 来保存头节点。
2.while循环遍历打印元素，同时更新cur节点
具体代码如下：
public void disPlay() {ListNode cur = head;while(cur!=null){System.out.println(cur.val);cur = cur.next;}System.out.println();}3.4 size（）方法的实现：
1.创建一个保存头节点的cur节点，以及一个用于记录整形的变量len，while循环，每次len++ 并更新cur节点，最后返回len的值。
具体代码如下:
@Overridepublic int size() {int len = 0;ListNode cur = head;while(cur!=null){len++;cur = cur.next;}return len;}3.5 contains方法的实现：
1.创建一个新节点cur来保存头节点
2.while循环，遍历过程中判断data是否 == cur.val,是的话，返回true，否则返回false，具体代码如下：
public boolean contains(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){return true;}cur = cur.next;}return false;}3.6：index方法的实现：
1.判断给出的index位置是否合理：<0/ >len(链表长度)，返回。
2.若index == 0,头插， index == len，尾插
3.创建findIndex方法，找到位于index位置处的节点。
ListNode cur = head,while循环（index不为0）遍历cur进入下一个节点，同时index自减1，
循环结束返回cur。 具体代码如下：
private ListNode findIndex(int index){ListNode cur = head;while( index !=0){cur = cur.next; //到达index位置处index--;}return cur;}4.插入 node节点：
3.7 remove方法的实现：
创建一个cur节点来存储head节点，while循环cur!=null,循环结束cur要更新至下一个节点
1.头删的实现：
2.尾删的情况：
3.中间情况的实现
具体代码实现：
public void remove(int key) {ListNode cur = head;while(cur!=null){if(cur.val == key){if(cur == head){head = head.next;if(cur!=null){cur.prev = null;}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}return ;}cur = cur.next;}}}
3.8 removeAllkey方法的实现：
将remove方法中的return去掉即可，这样消除了一个元素后可以继续遍历循环删除。
3.9 clear方法的实现：
创建新节点cur储存head，while循环遍历链表，设置curN节点为cur的下一个节点，在cur清除当前节点元素后，cur = curN, cur进入下一个位置即curN，进入下一次循环后curN再次后移。
最后，遍历结束后head节点和尾节点要手动置为null。
具体代码如下：
@Overridepublic void clear() {ListNode cur = head;while(cur!=null){ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = last = null;}
}今天分享结束，喜欢的老来个三联把！
