【Java数据结构】详解LinkedList与链表（三）
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪
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(index<0||index>size()){
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(index<0||index>size()){
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的使用。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
