Hello, Hello~ 亲爱的朋友们👋👋,这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章,请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣,记得关注我👀👀以便不错过每一篇精彩。 当然,如果在阅读中发现任何问题或疑问,我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力,一起进步! 加油,一起CHIN UP!💪💪
其成员属性跟无头单向非循环链表的成员属性类似。只是在内部类中多了个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;
注意: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();
}
直接遍历链表即可
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;
}
class MyIndexException extends RuntimeException{
public MyIndexException(String message) {
super(message);
}
}
比较简单,遍历这个数组即可
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 方法
首先判断链表是否为空,若为空则输出“为空链表,不能进行删除操作”,并直接返回。
若链表不为空,则判断头节点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("不存在该数");
}
首先判断链表是否为空,如果为空则无法进行删除操作,直接返回。
然后从头节点开始遍历链表,每次检查当前节点的下一个节点的值是否等于 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;
}
}
该方法首先要判断头节点是否为空,若为空,则直接返回。若不为空,则通过一个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,都是可取的,效果一样。我个人还是比较喜欢暴力解法。
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());
}
}
这篇文章我们就将无头双向非循环链表的模拟讲清楚了,它跟无头单向非循环链表的模拟很相似,但还是有一点区别的。我们下篇文章将给大家带来LinkedList的使用。在此,我们诚挚地邀请各位大佬们为我们点赞、关注,并在评论区留下您宝贵的意见与建议。让我们共同学习,共同进步,为知识的海洋增添更多宝贵的财富!🎉🎉🎉❤️❤️💕💕🥳👏👏👏