文章目录
前言一、双向链表是什么?二、案例1.节点类Node实现2.双向链表类DoubleLinkedLinst3.获取链表头,尾节点方法4.无脑增加方法add5.两个遍历方法(从头遍历和从尾遍历)6.修改节点upDate方法7删除方法delete()8.[重点菜]按顺序添加测试
总结
前言
双向链表的增删改查,其中难点在于按顺序增加,如何保持节点中指向上一个节点的pre也能被修改成功
提示：以下是本篇文章正文内容，下面案例可供参考
一、双向链表是什么?
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
二、案例
使用带 head 头的双向链表实现 –水浒英雄排行榜
1.节点类Node实现
代码如下（示例）：
public class Node {
String name
;
String nikeName
;
Integer no
;
Node next
;
Node pre
;
public Node(String name
, String nikeName
, Integer no
) {
this.name
= name
;
this.nikeName
= nikeName
;
this.no
= no
;
}
@Override
public String
toString() {
return "Node{" +
"name='" + name
+ '\'' +
", nikeName='" + nikeName
+ '\'' +
", no=" + no
+
'}';
}
}
2.双向链表类DoubleLinkedLinst
代码如下（示例）： 包含头结点 以及无参数构造方法,在创建双向链表对象的时候自动创建data为空的头节点
public class DoubleLinkedList {
Node head
;
public DoubleLinkedList() {
this.head
= new Node(null
, null
, 0);
}
}
3.获取链表头,尾节点方法
获取头
public Node
getHead(){
return head
;
}
获取链表尾部
通过遍历获取链表的最后一个节点
public Node
getLastNode() {
Node lastNode
= null
;
if (head
.next
== null
) {
System
.out
.println("链表为空");
}
Node temp
= head
.next
;
while (true) {
if (temp
== null
) {
break;
}
lastNode
= temp
;
temp
= temp
.next
;
}
return lastNode
;
}
这两个方法作用是为了后文两种遍历方法(从头遍历和从尾遍历)做铺垫
4.无脑增加方法add
找到链表的最后节点,在他后面加上新节点
/无脑添加方法add
public void add(Node newNode
) {
Node temp
= head
;
while (true) {
if (temp
.next
== null
) {
break;
}
temp
= temp
.next
;
}
temp
.next
= newNode
;
newNode
.pre
= temp
;
}
5.两个遍历方法(从头遍历和从尾遍历)
从头遍历show()
public void show() {
if (head
.next
== null
) {
System
.out
.println("链表为空");
return;
}
Node temp
= head
.next
;
while (true) {
if (temp
== null
) {
break;
}
System
.out
.println(temp
);
temp
= temp
.next
;
}
}
从尾部遍历
public void showByPre() {
Node lastNode
= getLastNode();
while (true) {
if (lastNode
== null
| lastNode
.no
== 0) {
break;
}
System
.out
.println(lastNode
);
lastNode
= lastNode
.pre
;
}
}
以上的遍历方法是为了更好地检验我们顺序添加的方法addByNo是否在添加完成节点后的next和pre都赋值正确
6.修改节点upDate方法
public void upDate(Node node
) {
if (head
.next
== null
) {
System
.out
.println("链表为空,没有能被修改的数据");
return;
}
Node temp
= head
;
boolean flag
= false;
while (true) {
if (temp
.next
== null
) {
break;
}
if (temp
.next
.no
== node
.no
) {
flag
= true;
break;
}
temp
= temp
.next
;
}
if (flag
) {
temp
.next
.name
= node
.name
;
temp
.next
.nikeName
= node
.nikeName
;
} else {
System
.out
.println("没找到对应点no");
}
}
两种遍历方式分别找到被修改节点和被修改节点的前一个节点
7删除方法delete()
public void delete(int no
) {
if (head
.next
== null
) {
System
.out
.println("链表为空");
return;
}
Node temp
= head
.next
;
boolean flag
= false;
while (true) {
if (temp
== null
) {
break;
}
if (temp
.no
== no
) {
flag
= true;
break;
}
temp
= temp
.next
;
}
if (flag
) {
temp
.pre
.next
= temp
.next
;
temp
.next
.pre
= temp
.pre
;
} else {
System
.out
.println("链表中没有这个no");
}
}
通过遍历找到被删除节点,将其前后两个节点的next和pre修改,让两者跳过被删除节点
8.[重点菜]按顺序添加
public void addByNo(Node node
) {
Node temp
= head
;
boolean flag
= false;
while (true) {
if (temp
.next
== null
) {
break;
}
if (temp
.next
.no
> node
.no
) {
break;
}
if (temp
.next
.no
== node
.no
) {
flag
= true;
break;
}
temp
= temp
.next
;
}
if (flag
) {
System
.out
.println("链表中已存在节点");
} else {
node
.next
= temp
.next
;
node
.pre
= temp
;
temp
.next
= node
;
if (node
.next
!= null
) {
node
.next
.pre
= node
;
}
}
}
为了保证我们添加后的next和pre都要指向正确的位置所以必须做出判断 情况1当我们的双向链表没有有效节点时,我们添加节点 , 这时我们只需要改动三个属性,新节点后并没有其他节点,所以后面节点的pre不需要修改,强行执行代码会出现空指针异常 情况2当 链表中有节点,同时我们的新节点要添加在head节点之后,这时必须执行第四行代码,让新节点后一个节点的pre正常赋值
测试
public class Test {
public static void main(String
[] args
) {
DoubleLinkedList doubleLinkedList
=new DoubleLinkedList();
Node n1
=new Node("1","1",1);
Node n2
=new Node("2","2",2);
Node n3
=new Node("3","3",3);
Node n4
=new Node("4","4",4);
doubleLinkedList
.addByNo(n2
);
doubleLinkedList
.addByNo(n4
);
doubleLinkedList
.addByNo(n3
);
doubleLinkedList
.addByNo(n1
);
doubleLinkedList
.show();
System
.out
.println("通过pre遍历后");
doubleLinkedList
.showByPre();
}
}
这里可以看出通过next属性或者pre属性 都可以正常遍历链表
总结
如有问题或建议,欢迎留言
