成都网站建设优化前十,广西智能网站建设哪家有,深圳专业做网站案例,杭州网站建设官网蓝韵网络目录 一.什么是链表
二.链表的实现
节点的插入
头插法
尾插法
指定位置插入
节点的删除
删除第一次出现的关键字节点
删除所有关键字节点
节点的查找
链表的清空
链表的长度 前言#xff1a;在上一篇文章中#xff0c;我们认识了线性数据结构中的顺序表#xff0… 目录 一.什么是链表
二.链表的实现
节点的插入
头插法
尾插法
指定位置插入
节点的删除
删除第一次出现的关键字节点
删除所有关键字节点
节点的查找
链表的清空
链表的长度 前言在上一篇文章中我们认识了线性数据结构中的顺序表而本篇文章则是介绍线性数据结构中的另一个结构——链表 想要了解顺序表相关操作的知识可以查看这篇文章图文详解顺序表的各种操作 一.什么是链表
链表是一种数据结构它由一系列节点node构成每个节点中包含了数据data和指向下一个节点的指针next。链表中的节点可以在内存中任何位置它们通过指针链接在一起形成一个链式结构。链表相对于数组的优点在于它可以动态地增加、删除节点而不需要移动大量的数据。链表的缺点是访问元素时需要遍历整个链表效率较低。
二.链表的实现
链表由不同的节点相互串起来每个节点由俩个部分组成一个是数据域用来放具体是数值内容另一个是指针域用来存放下一个节点的地址信息彼此之间就像是用链条串起来一样就像下图展示的这样所以称之为链表。 对于上图这样的结构我们可以如下定义一个链表将链表作为一个类并且在这个类中有一个内部类专门存储每一个节点的数据结构还有一个头节点单独定义来记录链表的起始位置
public class MyLinkList{//节点的数据结构static class ListNode{public int val;public ListNode next;}//链表的属性public ListNode head;//记录链表的第一个元素头节点
}对一个链表它应该完成以下这些功能我们将这些功能抽象出一个接口然后通过这个接口去实现一个真正的链表
public interface Ilist {//头插void addFirst(int data);//尾插void addLast(int data);//指定插入void addIndex(int index,int data);//查询是否存在boolean contains(int key);//删除节点void remove(int key);//删除所有与目标相同的节点void removeAllKey(int key);//得到链表的长度int size();//清空链表void clear();//输出链表的所有信息void display();
} 节点的插入
我们将节点的插入分为三种
头部插入将节点插入到链表的最前面尾部插入将节点插入到链表的最后面指定位置插入将节点插入到链表的中间
头插法
如图我们准备对于刚才的链表进行插入 我们这里分俩个步骤进行操作
将新节点指向头节点更新头节点的位置
我们更改要添加节点的指针域让它指向新的节点 在指向完成后我们新添加的节点就已经是链表的第一个节点了所以我们要更新头节点的信息记录新节点才是第一个节点 这样我们就完成了头部插入节点具体代码实现如下先生成一个节点然后按照上面图示的思路进行操作 //头插法public void addFirst(int data) {ListNode newNode new ListNode(data);newNode.next this.head;this.head newNode;}
尾插法
尾插法是将节点插入到链表的末尾但是我们是并没有记录末尾节点的位置的所以如果要使用尾插法的话就需要先找到尾部节点。那我们只需要根据最后一个节点特征进行遍历找到最后一个节点就可以了而最后一个节点最大的特征就是它只有数据域内有信息指针域里面是空。如果链表为空的话那我们直接在头节点之后添加就可以整体流程如下 整体代码实现如下先判断是否为空链表为空就直接在头节点之后添加不为空就遍历找到最后一个节点然后更改指针域内容添加新节点 //尾插法public void addLast(int data) {//当链表为空的时候直接将节点插入到头节点的位置ListNode newNode new ListNode(data);if (head null) {head newNode;}else{ListNode cur head;while (cur.next ! null){cur cur.next;}//找到最后一个节点cur.next newNode;//newNode.next null;//默认新节点的指针域为空所以这里可以不写这一行代码}}
指定位置插入
在中间位置插入是最麻烦的原因就在于我们不能立马获取到想要插入位置的信息我们需要先进行判断如果输入位置是在最前面那就可以使用头插如果是最后就使用尾插。在得知输入位置在链表中间后我们就需要先找到这个位置前后的节点的信息如下图假如我们要插入的位置是第三个位置那就需要知道第二个位置和第三个位置的信息当我们找到了后可以分俩布进行操作顺序不能更改
先让节点指向后面的节点再让前面的节点指向插入节点 第一步让插入节点指向后面的节点 第二步将前面的节点指向插入的节点 我们可以通过代码来实现这段过程先是进行合法性的判断然后是针对性的插入 //指定位置添加public void addIndex(int index, int data) {if(index 0 || index size()) {//这里不一定非要抛出自定义异常大家可以更具喜好自行设置throw new IndexException(index不合法: index);}//如果输入的位置在最前面就进行头插if (index 0)addFirst(data);//如果输入的位置在链表最后就进行尾插if (index size())addLast(data);//输入位置在中间就先找到这个节点的位置ListNode cur searchPrevIndex(index);ListNode newNode new ListNode(data);//这俩步是顺序非常重要newNode.next cur.next;cur.next newNode;}//找到位置对应的节点private ListNode searchPrevIndex(int index) {ListNode cur head;int count 0;while (count ! index-2) {cur cur.next;count;}return cur;} 节点的删除
对于节点是删除相当于插入简单了很多我们依旧是分为俩种方式进行删除一种是只删除第一次出现的节点另一种是删除全部想要删除的节点。
删除第一次出现的关键字节点
我们依旧是用初始的链表进行举例假如我们想要删除第三个节点 第一步我们直接更改要删除节点的前面节点的指针域让它指向要删除的节点后的节点 第二步我们将要删除的节点的指针域置为空 这俩步的顺序同样也不能错因为一旦我们先将要删除的节点的指针域置为空我们就无法再找到后面的节点了链表就相当于断开了
我们封装一个函数用来找到要删除节点的前一个节点然后通过它再删除目标节点 //删除第一个关键字public void remove(int key) {if (head null)return;if (head.val key){head head.next;return;}//查找val等于key的节点ListNode cur findKey(key);if (cur null){System.out.println(查无此元素无法删除);return;}ListNode delNode cur.next;cur.next delNode.next;//cur.next cur.next.next;}//找到要删除的元素的前一个节点private ListNode findKey(int key){ListNode cur head;while (cur.next ! null){if (cur.next.val ! key) {cur cur.next;}else{return cur;}}return null;}
删除所有关键字节点
与刚才不同的是删除一个节点是先找到前驱节点然后通过这个前驱节点进行操作而要删除所有的关键字节点则是对整个链表进行遍历一旦是关键字那我们就进行覆盖删除这里就不再画图了毕竟整个流程相当于多执行几次单个删除操作 //删除所有的关键字public void removeAllKey(int key) {if(head null) {return;}ListNode prev head;ListNode cur head.next;while (cur ! null) {if(cur.val key) {prev.next cur.next;cur cur.next;}else {prev cur;cur cur.next;}}//除了头节点都删除完成了if(head.val key) {head head.next;}} 节点的查找
节点的查找就是遍历整个链表如果找到就返回true没有找到就返回false //查找是否存在public boolean contains(int key) {ListNode cur head;while (cur ! null){if (cur.val key)return true;cur cur.next;}return false;} 链表的清空
当链表的头节点为空我们就视为链表被清空了 //清空链表public void clear() {head null;} 链表的长度
遍历整个链表使用计算器进行累加记录节点个数然后返回就可以 //求链表的长度public int size() {int count 0;ListNode cur head;while (cur ! null){count;cur cur.next;}return count;} 本次的分享就到此为止了希望我的分享能给您带来帮助也欢迎大家三连支持你们的点赞就是博主更新最大的动力如有不同意见欢迎评论区积极讨论交流让我们一起学习进步有相关问题也可以私信博主评论区和私信都会认真查看的我们下次再见
