🔒文章目录:
1.❤️❤️前言~🥳🎉🎉🎉
2.无头双向非循环链表的实现
2.1成员属性
2.2成员方法
display——打印链表
size——获取单链表长度
addFirst——头插
addLast——尾插
addIndex——在任意位置插入
contains——判定是否包含某个元素
remove——删除第一次出现关键字为key的结点
removeAll——删除所有值为key的结点
clear——清空单链表
2.3完整代码及使用
完整代码
完整代码的使用
3.总结
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋,这里是E绵绵呀✍️✍️。
如果你喜欢这篇文章,请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣,记得关注我👀👀以便不错过每一篇精彩。
当然,如果在阅读中发现任何问题或疑问,我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力,一起进步!
加油,一起CHIN UP!💪💪
🔗个人主页:E绵绵的博客
📚所属专栏:1. JAVA知识点专栏
深入探索JAVA的核心概念与技术细节
2.JAVA题目练习
实战演练,巩固JAVA编程技能
3.c语言知识点专栏
揭示c语言的底层逻辑与高级特性
4.c语言题目练习
挑战自我,提升c语言编程能力
📘 持续更新中,敬请期待❤️❤️
2.无头双向非循环链表的实现
2.1成员属性
其成员属性跟无头单向非循环链表的成员属性类似。只是在内部类中多了个prev前驱,以及成员变量多了个last。
public class MyLinkedList { static class ListNode{ int val; ListNode next; ListNode prev; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last;
2.2成员方法
display——打印链表
注意:MyLinkedList 中不存在该方法,为了方便看测试结果 。
public void display(){ ListNode cur=head; if(head==null) return; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); }
size——获取单链表长度
直接遍历链表即可
public int size(){ ListNode cur=head; int count=0; while(cur!=null){ cur =cur.next; count++; } return count; }
addFirst——头插
实现思路:
- 判断链表是否为空,如果为空,直接将head和last指向新节点listNode。
- 如果链表不为空,将新节点listNode的next指向当前头节点head,当前头节点head的prev指向新节点listNode,最后将head指向新节点listNode,完成头插操作。
public void addFirst(int a){ ListNode listNode = new ListNode(a); if(head==null){ head=listNode; last=listNode; }else{ listNode.next=head; head.prev=listNode; head=listNode; } }
addLast——尾插
实现思路与头插法类似:
判断链表是否为空,如果为空,则将头结点 head 和尾结点 last 都指向新节点 listNode。
如果链表不为空,将新节点 listNode 的 prev 指针指向当前的尾结点 last,将当前的尾结点 last 的 next 指针指向新节点 listNode,然后将尾结点 last 更新为新节点 listNode。
public void addLast(int a){ ListNode listNode = new ListNode(a); if(last==null){ head=listNode; last=listNode; }else{ listNode.prev=last; last.next=listNode; last=listNode; } }
addIndex——在任意位置插入
具体实现步骤如下:
判断链表是否为空。如果为空,则新建一个节点listNode,并将头结点head指向listNode,然后返回。
判断index是否越界。如果小于0或者大于链表长度size(),则抛出自定义异常MyIndexException,打印异常堆栈信息,然后返回。
如果index等于0,则调用addFirst(a)方法在链表头部添加元素a,然后返回。
如果index等于size(),则调用addLast(a)方法在链表尾部添加元素a,然后返回。
否则,新建一个节点listNode,并遍历链表找到第index-1个节点cur。
将cur节点的后继节点的前驱指针指向listNode节点。
将listNode节点的前驱指针指向cur节点。
将listNode节点的后继指针指向cur节点的后继节点。
将cur节点的后继指针指向listNode节点。
public void addIndex(int index,int a){ if(head==null){ ListNode listNode = new ListNode(a); head=listNode; return; } if(indexsize()){ try{ throw new MyIndexException("位置不合法"); } catch(Exception e){ e.printStackTrace(); } return; } if(index==0){ addFirst(a); return; } if(index==size()){ addLast(a); return; } ListNode listNode = new ListNode(a); ListNode cur=head; for (int i = 0; i <index-1 ; i++) { cur=cur.next; } cur.next.prev=listNode; listNode.prev=cur; listNode.next=cur.next; cur.next=listNode; } class MyIndexException extends RuntimeException{ public MyIndexException(String message) { super(message); } }
contains——判定是否包含某个元素
比较简单,遍历这个数组即可
public void contain(int key){ ListNode cur=head; while(cur!=null){ if(cur.val==key){ System.out.println(true); return; } cur=cur.next; } System.out.println(false); }
因为这里我们存放的是 int 类型的变量,但 LinkedList 当中是存放引用数据类型的
⚠️⚠️⚠️当表中是引用类型时,就不可以用“等号”比较,应该用 equals 方法
remove——删除第一次出现关键字为key的结点
首先判断链表是否为空,若为空则输出“为空链表,不能进行删除操作”,并直接返回。
若链表不为空,则判断头节点head的值是否等于给定key值。如果是,将head指向下一个节点,并将原来的head节点删除。如果此时head已经变成空节点,说明该链表只有一个节点,直接更新last为null;否则,将head节点的前驱指针设为null。
如果头节点的值不等于给定key值,则从头节点的后继开始遍历链表。当遇到某个节点的值等于给定key值时,将该节点的前驱节点指向该节点的后继节点,并将该节点删除。
如果整个链表中不存在值等于给定key值的节点,则输出“不存在该数”
public void remove(int key){ ListNode cur=head; if(head==null) { System.out.println("为空链表,不能进行删除操作"); return; } if(cur.val==key) { head=head.next; if(head==null){ last=null; }else head.prev=null; return; } while(cur.next!=null){ if(cur.next.val==key){ cur.next.next.prev=cur; cur.next=cur.next.next; return; } cur=cur.next; } System.out.println("不存在该数"); }
removeAll——删除所有值为key的结点
首先判断链表是否为空,如果为空则无法进行删除操作,直接返回。
然后从头节点开始遍历链表,每次检查当前节点的下一个节点的值是否等于 key,如果相等,则把当前节点的下一个节点删除(即把当前节点的 next 指针指向下下个节点),同时要把下下个节点的 prev 指针指向当前节点。
如果当前节点的下一个节点的值不等于 key,则把当前节点移动到下一个节点。
最后,如果头节点的值等于 key,需要特殊处理头节点,将头节点指向下一个节点。如果此时头节点已经为空,则需要将尾节点也设为 null;否则我们就将新的头节点的 prev 指针设为 null。
public void removeAll(int key){ if(this.head == null) { System.out.println("为空链表,不能进行删除操作"); return; } ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ cur.next.next.prev=cur; cur.next=cur.next.next; } else { cur = cur.next; }} if(head.val==key){ head = head.next; if(head==null){ last=null; }else head.prev=null; } }
clear——清空单链表
该方法首先要判断头节点是否为空,若为空,则直接返回。若不为空,则通过一个while循环,将每个节点的前驱和后继均置为null,以便垃圾回收机制及时回收节点所占用的内存。最后,将头节点和尾节点均置为null,以实现链表清空。
如果节点中的val是引用类型,则需要将其也全变为null。基本类型则不需要。
public void clear(){ while (head==null) return; ListNode cur=head; while (cur!=null){ cur.prev=null; ListNode temp=cur.next; cur.next=null; cur=temp; } head=null; last=null; }
当然也存在暴力解法,就是直接将head=null,last=null,也能得到一样的效果。
public void clear(){ head=null; last=null; }
此时链表中的各个节点中 就不存在 有固定存在的引用去指向它们,它们节点自己的互相指向就形成了个死循环,此时系统就默认将这些节点自动回收掉,所以能得到一样的效果。
对于无头单向非循环链表中的clear我们采用的是暴力解法,当然也可以像这里一样把引用变量全都变为null,都是可取的,效果一样。我个人还是比较喜欢暴力解法。
2.3完整代码及使用
完整代码
public class MyLinkedList { static class ListNode{ int val; ListNode next; ListNode prev; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; public void display(){ ListNode cur=head; if(head==null) return; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); } public int size(){ ListNode cur=head; int count=0; while(cur!=null){ cur =cur.next; count++; } return count; } public void addFirst(int a){ ListNode listNode = new ListNode(a); if(head==null){ head=listNode; last=listNode; }else{ listNode.next=head; head.prev=listNode; head=listNode; } } public void addLast(int a){ ListNode listNode = new ListNode(a); if(last==null){ head=listNode; last=listNode; }else{ listNode.prev=last; last.next=listNode; last=listNode; } } public void addIndex(int index,int a){ if(head==null){ ListNode listNode = new ListNode(a); head=listNode; return; } if(indexsize()){ try{ throw new MyIndexException("位置不合法"); } catch(Exception e){ e.printStackTrace(); } return; } if(index==0){ addFirst(a); return; } if(index==size()){ addLast(a); return; } ListNode listNode = new ListNode(a); ListNode cur=head; for (int i = 0; i <index-1 ; i++) { cur=cur.next; } cur.next.prev=listNode; listNode.prev=cur; listNode.next=cur.next; cur.next=listNode; } public void remove(int key){ ListNode cur=head; if(head==null) { System.out.println("为空链表,不能进行删除操作"); return; } if(cur.val==key) { head=head.next; if(head==null){ last=null; }else head.prev=null; return; } while(cur.next!=null){ if(cur.next.val==key){ cur.next.next.prev=cur; cur.next=cur.next.next; return; } cur=cur.next; } System.out.println("不存在该数"); } public void removeAll(int key){ if(this.head == null) { System.out.println("为空链表,不能进行删除操作"); return; } ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ cur.next.next.prev=cur; cur.next=cur.next.next; } else { cur = cur.next; }} if(head.val==key){ head = head.next; if(head==null){ last=null; }else head.prev=null; } } public void clear(){ while (head==null) return; ListNode cur=head; while (cur!=null){ cur.prev=null; ListNode temp=cur.next; cur.next=null; cur=temp; } head=null; last=null; } public void contain(int key){ ListNode cur=head; while(cur!=null){ if(cur.val==key){ System.out.println(true); return; } cur=cur.next; } System.out.println(false); } } class MyIndexException extends RuntimeException{ public MyIndexException(String message) { super(message); } }
完整代码的使用
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addFirst(110);
myLinkedList.addFirst(15);
myLinkedList.addLast(45);
myLinkedList.addLast(64);
myLinkedList.addLast(43);
myLinkedList.addIndex( 4,45);
myLinkedList.addFirst(45);
myLinkedList.display();
myLinkedList.remove(15);
myLinkedList.removeAll(45);
myLinkedList.display();
myLinkedList.contain(110);
System.out.println(myLinkedList.size());
}
}
3.总结
这篇文章我们就将无头双向非循环链表的模拟讲清楚了,它跟无头单向非循环链表的模拟很相似,但还是有一点区别的。我们下篇文章将给大家带来LinkedList的使用。在此,我们诚挚地邀请各位大佬们为我们点赞、关注,并在评论区留下您宝贵的意见与建议。让我们共同学习,共同进步,为知识的海洋增添更多宝贵的财富!🎉🎉🎉❤️❤️💕💕🥳👏👏👏