单链表的介绍
线性表的链式存储又称单链表,它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系,对每个链表节结点,除存放元素自身的信息外,还需要存放一个指向其后继的指针。
单链表结构如下所示,其中data为数据域,存放数据元素,next为指针域,存放其后继结点的地址。
由于单链表的元素离散地分布在存储空间中,所以单链表是非随机存取的数据结构,即不能直接找到表中某个特定的结点。查找某个特定的结点时,需要从表头开始遍历,依次查找。
链表分带头结点的链表和没有头结点的链表,根据实际的需求来确定。通常用头指针来标识一个单链表,如单链表L,头指针为null时表示一个空表。此外,为了操作方便,在单链表第一个结点之前附加一个结点,称为头结点。头结点的数据域可以不存放任何信息,也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
头指针和头结点的区分
不管带不带头结点,头指针始终指向链表的第一个结点,而头结点是带头结点的链表中的第一个结点,结点内通常不存储信息。
引入头结点的好处
- 由于第一个数据结点的位置被存放在头结点的指针域中,所以链表的第一个位置上的操作和在表的其他位置上的操作一致,无需进行特殊处理。
- 无论链表是否为空,其头指针都是指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就得到了统一。
单链表的实现思路
单链表的创建
- 先创建一个head 结点,作用就是表示单链表的头部
- 后面我们每添加一个结点,就直接加入到链表的最后(尾插法)
单链表的遍历
- 由于头指针不能动,需要通过一个辅助指针帮助遍历整个链表。
插入新节点
- ① 首先找到新添加的结点位置,是通过辅助指针,通过遍历来实现
- ② 新的结点.next = tmp.next
- ③ 将tmp.next指向新的结点
修改结点
- ① 先通过遍历找到该结点
- ② tmp.name = node.name
tmp.nickname = node.nickname
删除节点
- ① 我们先找到需要删除的这个结点的前一个结点 tmp
- ② tmp.next = tmp.next.next
- ③ 被删除的结点,将不会有其他引用指向,会被垃圾回收机制回收。
代码实现
package cn.kuetr.linkedlist;
public class SingleLinkedListTest {
public static void main(String[] args) {
//测试
//先创建结点
LinkNode hero1 = new LinkNode(1, "宋江", "及时雨");
LinkNode hero2 = new LinkNode(2, "卢俊义", "玉麒麟");
LinkNode hero3 = new LinkNode(3, "吴用", "智多星");
LinkNode hero4 = new LinkNode(4, "林冲", "豹子头");
//创建链表
SingleLinkedList l = new SingleLinkedList();
l.insert(hero1);
l.insert(hero4);
l.insert(hero2);
l.insert(hero3);
l.list();
//测试修改结点
LinkNode info = new LinkNode(2, "小卢", "小尾巴");
l.modify(info);
//显示链表
l.list();
//删除一个节点
l.delete(1);
l.delete(4);
l.delete(2);
l.delete(3);
//显示链表
l.list();
}
}
//定义一个SingleLinkedList来管理结点
class SingleLinkedList {
// 先初始化一个头结点,头结点不要动,也不存放具体数据
private LinkNode head = new LinkNode(0, "", "");
// 添加结点到单向链表
/*
* 思路,当不考虑编号顺序时, 1.找到当前链表的最后结点 2.将最后这个结点指向新结点。
*/
public void addNode(LinkNode node) {
// 因为head结点不能动,因此需要一个辅助指针
LinkNode tmp = head;
// 遍历链表,找到最后
while (true) {
// 如果tmp.next == null 说明tmp是尾节点
if (tmp.next == null) {
break;
} else {
tmp = tmp.next; // 如果没有找到,就把指针后移
}
}
// 当退出while循环时,tmp指向链表的最后,此时链接上即可
tmp.next = node;
}
//在链表中插入结点:
public void insert(LinkNode node) {
//由于头指针不能动,因此必须要通过辅助指针来帮助找到添加的位置
//因为是单链表,因此我们找的tmp是位于添加位置的前一个结点,否则无法插入
LinkNode tmp = head;
boolean flag = false; //标识添加的编号是否存在,默认为false
while(true) {
if(tmp.next == null) { //说明tmp已经在链表的最后
break;
}
if(tmp.next.id > node.id) { //找到位置,在tmp的后面插入
break;
}else if(tmp.next.id == node.id) {
flag = true; //说明编号存在
break;
}
tmp = tmp.next; //后移,遍历当前链表
}
//判断flag的值,是否进行添加
if(flag) { //不能添加,因为编号存在
System.out.printf("由于编号%s存在,不能完成添加操作!\n",node.id);
}else {
//插入到链表中
node.next = tmp.next;
tmp.next = node;
}
}
//删除结点
//思路:
//1.因为head结点不能动,因此需要tmp辅助结点,找到待删除结点的前一个结点。
//2.我们在比较时,是tmp.next.id和需要删除的结点的id比较
public void delete(int id) {
LinkNode tmp = head;
boolean flag = false; //标识是否找到待删除结点
while(true) {
if(tmp.next == null) {
break;
}
if(tmp.next.id == id) {
//找到了待删除结点的前一个结点
flag = true;
break;
}
tmp = tmp.next;
}
if(flag) { //找到结点
//此时可以删除
tmp.next = tmp.next.next;
}else {
System.out.println("要删除的结点不存在");
}
}
//修改结点的信息,根据编号来修改,即id不能改
//1.根据node的id来进行修改
public void modify(LinkNode node) {
//判断是否为空
if(head.next == null) {
System.out.println("链表为空。");
return;
}
//找到需要修改的结点:
//先定义一个辅助变量
LinkNode tmp = head.next;
boolean flag = false; //表示是否找到该结点
while(true) {
if(tmp.next == null) {
break; //已经到了链表的最后,已经遍历完链表
}
if(tmp.id == node.id) {
//找到
flag = true;
break;
}
tmp = tmp.next;
}
//根据flag是否找到要修改的结点
if(flag) {
tmp.name = node.name;
tmp.nickname = node.nickname;
}else {
System.out.println("没有找到要修改的结点,请检查传入参数是否正确!");
}
}
// 显示链表[遍历]
public void list() {
// 先判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 因为头结点不能动,因此需要辅助指针来帮助遍历
LinkNode tmp = head.next;
while (true) {
//判断是否
if (tmp == null) {
break;
}
//输出结点信息
System.out.println(tmp);
//将tmp后移,必须要注意
tmp = tmp.next;
}
}
}
//定义一个LinkNode,每个LinkNode就是一个结点
class LinkNode {
public int id;
public String name;
public String nickname;
public LinkNode next; // 指向下一个结点
public LinkNode(int id, String name, String nickname) {
this.id = id;
this.name = name;
this.nickname = nickname;
}
// 为了显示方便,我们重写toString方法
@Override
public String toString() {
return "HeroNode [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
}
}