慈溪网站建设公司,做网站技术选择,全球设计师,wordpress分类树1.基本结构:
双向链表是一种链表数据结构#xff0c;它由一系列节点组成#xff0c;每个节点包含三个部分#xff1a;
(1).数据域#xff1a;存储节点的数据
(2).前驱指针:指向前一个节点
(3).后驱指针:指向下一个节点
2.基本特性#xff1a;
双向链接: 与单向链表…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节点以及一个用于记录整形的变量lenwhile循环每次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.6index方法的实现
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储存headwhile循环遍历链表设置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;}
}
今天分享结束喜欢的老来个三联把
