数据结构：单向链表

单链表

文章目录

• • 单链表
  • • 前言
    • 单向链表的结构
    • 代码实现
    • • 链表存储的节点
      • 链表初始化
      • 链表的基本操作
      • • 增加节点
        • 按照编号顺序添加节点
        • 更新节点中数据
        • 遍历链表
        • 获取链表长度
        • 获取倒数第n个节点

前言

在链表的学习之前，我们已经学过了数组，在数组创建时，其数组长度已经写死了，因此对于数据的拓展，数组具有一定的局限性。数组有一个很重要的结构就是索引，我们在数组中查询数据也是用索引去查询，因此当需要删除数据时，必须将所有数据进行移动改变索引，性能开销相当大，而链表就可以解决以上问题。

---

单向链表的结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hyce4Vv3-1627915099881)(C:/Users/Supreme%20honor/Desktop/NoteBook/%E9%93%BE%E8%A1%A8.jpg)]

链表结构比较简单，就是一个个节点连接在一起，形成一个完整链式结构。每个节点包含两部分(如图)，一个是用于存储数据的数据域，一个是用于指向下一个节点的next指针。当删除数据时，只需要要改变前后节点的next引用关系即可，不需要像数组一次性出发所有数据的移动，速度比数组快很多，也节省了很大的性能开销。

---

代码实现

链表存储的节点

//存储人物信息 class HeroNode {//人物序号：链表操作中有根据序号进行排序的方法,添加此节点以测试链表数据的插入public int num;public String name;public String nickname;public HeroNode next;/*** 构造器*/public HeroNode(int num, String name, String nickname) {this.num = num;this.name = name;this.nickname = nickname;}@Overridepublic String toString() {return "HeroNode{" +"num=" + num +", name='" + name + '\'' +", nickname='" + nickname+"}";} }

链表初始化

class SingleLinkedList {/*** 先初始化一个头节点,不放具体的数据*/private HeroNode headNode = new HeroNode(0,"",""); }

链表的基本操作

增加节点

/*** 添加节点到单向链表* 思路:当不考虑编号顺序时* 1.找到当前链表的最后一个节点* 2.将最后节点的next指向新的节点* @param node*/public void add(HeroNode node){//因为head节点不能动,因此我们需要一个辅助遍历指针tempHeroNode temp = headNode;//遍历链表while (true){if (temp.next == null){break;}//后移指针temp = temp.next;}//退出while循环时,temp就指向了链表的最后//将最后的节点指向新的节点//注意:不是headNode.next = node;temp.next = node;}

按照编号顺序添加节点

/*** 需要按照编号的顺序添加* 1.首先要找到新添加的节点的位置,是通过辅助指针遍历* 2.新的节点.next = temp.next* 3.将temp.next = 新的节点* @param node*/ public boolean addByOrder(HeroNode node) {//头节点不能动,因此需要使用辅助指针找到应插入的位置//单链表:temp要找到添加位置的前一个节点(让这前一个节点的next域指向新的节点)HeroNode temp = headNode;//编号是否以及存在,如果存在则添加失败boolean hasExit = false;//遍历链表while (true){//链表遍历完毕if (temp.next == null){break;}//要让temp指向要添加位置的前一个节点if (temp.next.num > node.num){break;}else if (temp.next.num == node.num){hasExit = true;break;}//向后移动指针temp = temp.next;}//编号已经存在if (hasExit){System.out.println("编号已存在,添加失败....");return false;}else{//切记顺序不可调换node.next = temp.next;temp.next = node;}return true; }

更新节点中数据

/*** 修改节点的信息,根据No编号来修改,No编号不能改* @param node*/ public void update(HeroNode node) {//判断链表是否为空if (headNode.next == null){System.out.println("链表为空....");return;}//根据编号找到需要修改的节点HeroNode temp = headNode.next;boolean hasFound = false;while (true){//链表已经遍历完毕if (temp == null){break;}//找到待修改节点if (temp.num == node.num){hasFound = true;break;}temp = temp.next;}//找到节点if (hasFound){temp.name = node.name;temp.nickname = node.nickname;}else{System.out.println("没有找到该编号的节点....");} }

遍历链表

/*** 遍历链表*/public void list(){System.out.println("-------------------------------List-------------------------------");//判断链表是否为空if (headNode.next == null){System.out.println("链表为空");return;}//头节点不能动HeroNode temp = headNode.next;while (true){if (temp == null){break;}//输出节点信息System.out.println(temp);//将temp后移temp = temp.next;}}

获取链表长度

/*** 获取单链表的节点个数(带头结点的链表不需要统计头节点)* @return 有效节点个数*/ public int getLength() {//空链表if (headNode.next == null){return 0;}int length = 0;HeroNode temp = headNode;while (temp.next != null){length++;temp = temp.next;}return length; }

获取倒数第n个节点

/*** 查找单链表中的倒数第n个节点* 1.接受index->倒数第index个节点* 2.获取链表长度length* 3.遍历length-index个节点*/ public HeroNode getLastIndexNode(int index) throws Exception {if (headNode.next == null){return null;}int length = getLength();//对index进行校验if (index <= 0 || index > length){throw new Exception("输入索引错误!");}HeroNode temp = headNode.next;for (int i = 0; i < length - index; i++){temp = temp.next;}return temp; } 《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的数据结构：单向链表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。