双向链表的基本结构及功能实现

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;}
}

今天分享结束，喜欢的老来个三联把！