文章目录
- 节点类
- 定义单链表类
- 总结
单链表是一种常用的数据结构,它由若干个节点(Node)组成,每个节点包含两部分:一部分是数据域,用于存储数据;另一部分是指针域,用于指向下一个节点。。
节点类
定义的节点类:
public class HeroNode {
public int no;
public String name;
public HeroNode next; //指向下一个节点
public HeroNode(int no, String name, HeroNode next) {
this.no = no;
this.name = name;
this.next = next;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
在这个代码中,HeroNode 类定义了三个实例变量:no 表示英雄编号,name 表示英雄姓名,next 表示指向下一个节点的引用。
构造方法用于初始化对象的属性,toString() 方法用于打印节点的信息。
定义单链表类
public class SingleLinkedList {
/** 初始化头节点 不存放数据 只是一个标记 */
private HeroNode head = new HeroNode(0, "", null);
/** 插入节点 尾插法 */
public void add(HeroNode newNode){
if( newNode == null ){
return;
}
HeroNode currentNode = head;
while ( currentNode.next != null ) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
/** 修改节点 */
public void update(HeroNode newNode){
if( newNode == null ){
return;
}
HeroNode currentNode = head.next;
while ( currentNode != null ){
if( currentNode.no == newNode.no ){
currentNode.name = newNode.name;
}
currentNode = currentNode.next;
}
}
/** 删除节点 */
public void delNode(int no){
HeroNode currentNode = head;
while ( currentNode != null && currentNode.next != null ) {
if( currentNode.next.no == no ){
currentNode.next = currentNode.next.next;
}
currentNode = currentNode.next;
}
}
/** 展示列表 */
public void show(){
HeroNode currentNode = head.next;
while ( currentNode != null ) {
System.out.println(currentNode);
currentNode = currentNode.next;
}
}
}
在 SingleLinkedList 类中实现了以下几个方法:
add(HeroNode newNode)
:在链表的尾部插入一个新节点。
update(HeroNode newNode)
:根据节点编号找到指定节点,并更新节点的姓名。
delNode(int no)
:根据节点编号找到指定节点的前一个节点,并将其 next 引用指向下一个节点,从而实现删除节点的功能。
show()
:遍历链表,并打印每个节点的信息。
这些方法都是单链表常见的操作,有几个小地方需要注意:
在 add(HeroNode newNode) 方法中,使用的是尾插法,即将新节点添加到链表的尾部。这是常用的插入方法之一,可以有效地保持链表的顺序性。
在 update(HeroNode newNode) 方法中,首先需要找到待修改的节点,然后更新其数据。这是正确的操作。但是,在找到节点后,没有中断循环,而是继续遍历链表直到结束,是因为考虑到链表中可以存在重复的节点。
在 delNode(int no) 方法中,首先需要找到待删除节点的前一个节点,然后将其 next 引用指向待删除节点的下一个节点。
在 show() 方法中,你首先将头节点赋给 currentNode,然后通过 currentNode.next 遍历链表。这样做是为了跳过头节点,只展示真实数据节点。这也是常见的展示列表的操作。
以上就是一个单链表的简单的实现。
总结
单链表的特点包括:
- 链表中的节点是通过指针相连的,每个节点都指向下一个节点,最后一个节点指向空(null)。
- 单链表可以动态地增加、删除节点,而不需要移动其他节点的位置。
- 链表的插入和删除操作效率高,时间复杂度为 O(1)。
- 链表的查找操作相对较慢,时间复杂度为 O(n),需要从头节点开始依次向后遍历。
单链表的优势在于可以方便地进行插入和删除操作,但其缺点是查找操作效率较低。在实际编程中,单链表常用于不需要频繁查找操作,但需要频繁插入和删除操作的场景中。
单链表是一种重要的数据结构,能够有效地解决一些特定的问题,例如处理动态数据或者构建一些数据结构。