云南住房建设厅网站,与电子商务网站建设有关实训报告,织梦素材网站模板,黄页推广币是什么意思1.双向链表的结构#xff08;双向不带头不循环链表#xff09;
需要注意的一点就是#xff0c;在jdk中的链表就是双向链表
一个节点有三个域 val#xff08;数值域#xff09; next#xff08;地址域#xff09; prev#xff08;前驱记录前一个节点的地址#xff09…1.双向链表的结构双向不带头不循环链表
需要注意的一点就是在jdk中的链表就是双向链表
一个节点有三个域 val数值域 next地址域 prev前驱记录前一个节点的地址 在双向链表中我们还定义了一个last用来标记最后一个节点
2.双向链表的具体实现
1.定义一个MyLinkedLIst的类它要实现的所有内容是和单向链表中接口的方法是一样的 双向链表的实现的方法和单项链表的方法是一样的所以接入的接口也是一样的 在写这些方法之前要先定义一个双向链表的基本框架其中构造方法是为了能够链表传入val的参数 2.1双向链表中display方法打印链表方法的实现
双向链表的打印和单项链表是一样的因为都是头节点cur从头走到尾。 2.2双向链表size方法打印链表长度是多少的方法的实现
也和单向链表是一样的都是头结点从头走到尾 2.3双向链表contains找寻专门的元素在链表中对的位置的方法的实现
基本框架 代码实现 2.3双向链表addFirst方法 不进行详细讲解绿色字看不动到专栏链表一中进行查看
要注意的是要是只有一个节点的化就不能这样写会发生空指针异常所以一个的时候我们只需要让头结点指向它然后last也指向node就行了。 2.4双向两步addlast方法插入一个元素到节点的最后一个
和头插法是相似的 2.5双向链表在指定位置来对要插入的数值进行插入 和单向链表不同的是双向链表可以前进和后退
所以我们只需要走到要插入的节点的位置然后修改四个指向就可以了
先连后面再连前面 分两种情况如果在头部就直接插入如果不在头部就正常进行插入如果在尾部那么就直接尾插法循环条件大家看一下没啥问题我相信大家的能力
2.6删除方法remove删除一个元素指定的
del是要删除节点的位置 其中我们要注意两种情况
要是写错的化会有空指针异常因为headA和last存的地址的值是null所以会报错
所以我们要避免这种情况
下面是详细的图解用删除中间节点的逻辑来对其进行删除 1删除头节点的思路 将headA往后面移动一个然后将headA的prev位置重置为空 也就是 headA headA.next; head.prev null
2删除中间节点的思路 3删除最后节点的思路
总体代码实现 这个代码还有一个问题隐型的问题 如果只删除一个节点那么就会让head为null发生空指针异常所以我们要防止这种情况 总体代码太长了不能图片 public void remove(int key) {ListNode cur head;while (cur ! null) {if(cur.val key) {if(cur head) {head head.next;if(head ! null) {head.prev null;}else {//只有一个节点 且是需要删除的节点last null;}}else {cur.prev.next cur.next;//删除中间节点if(cur.next ! null) {cur.next.prev cur.prev;//cur.prev.next cur.next;}else {//删除尾巴节点//cur.prev.next cur.next;last last.prev;}}return;}cur cur.next;}}
2.7删除方法removeall删除所有这个指定元素的值
这个方法和remove方法可以说是一毛一样
在remove方法中我们不是return结束这个循环了吗我们只要不结束这个循环让他继续走那么就可以继续进入循环进行删除 所以我们可以这样 这样就完成了
整体代码
public void removeAllKey(int key) {ListNode cur head;while (cur ! null) {if(cur.val key) {if(cur head) {head head.next;if(head ! null) {head.prev null;}else {//只有一个节点 且是需要删除的节点last null;}}else {cur.prev.next cur.next;//删除中间节点if(cur.next ! null) {cur.next.prev cur.prev;//cur.prev.next cur.next;}else {//删除尾巴节点//cur.prev.next cur.next;last last.prev;}}}cur cur.next;}}
2.8clear方法删除所有的元素
让头结点和last节点都为空就直接清除了 后面我会在java进阶课程中详细讲解他的清空过程
进入clear的源码
其实和我写的差不多
io流那里估计是
最后希望大家看完这链表两个数据结构的文章以后就去看源码我写的和源码其实差不多只不过源码的封装更多
