湘潭网站制作建设,天津短视频seo,北京中御建设公司网站,河北省住房和城乡建设厅 网站数据结构和算法-单链表
1. 链表介绍 链表是有序的列表#xff0c;但是它在内存中是存储如下 图1 单链表示意图 小结:
链表是以节点的方式存储每个节点包含data域#xff0c;next域#xff0c;指向下一个节点。如图#xff1a;发现链表的各个节点不一定是连续存储。比如地…数据结构和算法-单链表
1. 链表介绍 链表是有序的列表但是它在内存中是存储如下 图1 单链表示意图 小结:
链表是以节点的方式存储每个节点包含data域next域指向下一个节点。如图发现链表的各个节点不一定是连续存储。比如地址为150的节点下一个节点的地址不为160而是指向地址为110的节点。链表分带头节点的链表和没有头节点的链表根据实际的需求来确定。
单链表(带头结点)逻辑结构示意图如下 图2 带头结点的单链表 注意图2中逻辑结构的连接并不是按照地址的顺序画的而是按照每个节点的next域的内存地址连接的。真实的内存存储世图1所示
2. 单链表的应用实例
使用带head头的单向链表实现-水浒英雄排行榜管理
完成对英雄人物的增删改查操作注删除和修改查找。第一种方法在添加英雄时直接添加到链表尾部第二种方法在添加英雄时根据排名将英雄插入到指定位置(如果有这个排名则添加失败并给出提示)
思路使用一个类来代表一个节点 其中类中的属性来表示节点中的内容
添加创建 先创建一个head节点作用就是表示单链表的头后面每添加一个节点就直接加入到链表的最后 遍历 通过一个辅助变量遍历帮助遍历整个链表
class HeroNode{int no;String name;String nickName;HeroNode next;
}图3 单链表的创建示意图 2.1 直接将节点添加到链表尾部
实现添加节点时直接添加到链表尾部
public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode heroNode1 new HeroNode(1, 松江, 及时雨);HeroNode heroNode2 new HeroNode(2, 卢俊义, 玉麒麟);HeroNode heroNode3 new HeroNode(3, 吴用, 智多星);HeroNode heroNode4 new HeroNode(4, 林冲, 豹子头);//创建一个列表SingleLinkedList singleLinkedList new SingleLinkedList();//加入singleLinkedList.add(heroNode1);singleLinkedList.add(heroNode2);singleLinkedList.add(heroNode3);singleLinkedList.add(heroNode4);//显示singleLinkedList.list();}
}//定义SingleLinkedList管理节点
class SingleLinkedList {//先初始化一个头节点 头节点不要动 不存放具体的数据private HeroNode head new HeroNode(0, , );//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next 指向 新的节点public void add(HeroNode heroNode) {//因为head节点不能动 因此需要一个辅助变量tempHeroNode temp head;//遍历链表 找到最后while (true) {//链表的最后一个节点的next为nullif (temp.next null) {//说明此时temp就指向了链表的最后temp.next heroNode;break;} else {temp temp.next;//将此节点的下一个节点作为新循环的判断(后移一个节点判断)}}}//显示链表[遍历]public void list() {//判断链表是否为空if (head.next null) {System.out.println(链表为空);return;}//因为head节点不能动 因此需要一个辅助变量temp来遍历HeroNode temp head.next;while (true) {//输出节点信息System.out.println(temp);//判断是否到链表最后if (temp.next null) {//说明这个节点是最后一个节点break;}temp temp.next;//后移一个节点}}
}//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode {public int no;public String name;public String nickname;public HeroNode next; //指向下一个节点//构造器public HeroNode(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}Overridepublic String toString() {return HeroNode{ no no , name name \ , nickname nickname \ , next (next null ? null : next.hashCode()) };}
}2.2 按顺序添加节点
实现添加节点时根据排名将英雄插入到指定位置(如果有这个排名则添加失败并给出提示) 图4 按顺序添加节点示意图 需要按照编号的顺序添加节点 思路
首先找到新添加的节点的位置是通过辅助变量(指针)通过遍历来搞定新的节点.next temp.next将 temp.next 新的节点
自己写代码如下重写了一下类
//定义SingleLinkedList2按顺序管理节点
class SingleLinkedList2 {//先初始化一个头节点 头节点不要动 不存放具体的数据private HeroNode head new HeroNode(0, , );//按顺序添加节点到单向链表public void add(HeroNode heroNode) {if (head.next null) {//说明此时空链表head.next heroNode;//直接将此节点添加到头节点的后面return;}HeroNode temp head;do {if (heroNode.no temp.next.no) {//将此节点插入到temp和temp.next中间
// HeroNode temp2 temp.next;//保存temp的下一个节点
// temp.next heroNode; //将temp下一行节点指向heroNode
// heroNode.next temp2; //将heroNode的下一个节点指向到原temp.nextheroNode.next temp.next; //将heroNode的下一个节点指向到temp.nexttemp.next heroNode; //将temp下一行节点指向heroNodereturn; //直接结束战斗} else if (heroNode.no temp.next.no) {System.out.println(已经当有相同节点了 添加失败 请自重);return;}temp temp.next; //节点后移} while (temp.next ! null);//如果正常退出 说明此对象的序号值最大 直接放在最后面temp.next heroNode;}//显示链表[遍历]public void list() {if (head.next null) {System.out.println(别闹宝 空链表~~);return;}HeroNode temp head;while (temp.next ! null) {//如果下一个节点不为空(存了数据)System.out.println(temp.next); //输出下一个节点temp temp.next; //后移到下一个节点}}
}韩老师教的如下 在SingleLinkedList类中新添加了一个按顺序排列的函数
//第二种方式在添加英雄时 根据排名将英雄插入到指定位置
//(如果有这个排名 则添加失败 并给出提示)
public void addByOrder(HeroNode heroNode) {//因为头节点不能动 因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为是单链表 找的temp是位于添加位置的前一个节点 否则插入不了HeroNode temp head;boolean flag false; //标志添加的编号是否存在 默认为falsewhile (true) {if (temp.next null) {//说明temp已经在链表的最后break;}if (temp.next.no heroNode.no) { //位置找到 就在temp的后面插入break;} else if (temp.next.no heroNode.no) { //说明希望添加的heroNode的编号已经存在flag true; //说明编号存在break;}temp temp.next; //后移一位 相当于遍历链表}//判断flag的值if(flag){ //不能添加 说明编号存在System.out.printf(准备插入的英雄的编号 %d 已经存在了不能加入\n,heroNode.no);} else {//因为不管是temp.next null还是temp.next.no heroNode.no 都需要把heroNode放在temp的后面//加入到链表中 temp的后面heroNode.next temp.next;temp.next heroNode;}
}2.3 单链表节点的修改根据no编号来修改
自己写的如下 在类中增加了一个修改函数
//修改节点的信息 根据no编号来修改 即no编号不能改
public void modify(int no, String name,String nickname) {if (head.next null) {//说明此时空链表System.out.println(空链表 修改失败 改不了);return;}HeroNode temp head;while (temp.next ! null){ //遍历if(no temp.next.no){ //如果编号相同temp.next.name name;temp.next.nickname nickname;return;//结束函数}temp temp.next;}//如果正常退出循环 则说明没找到对应的编号System.out.println(不好意思没找到对应编号的位置);
}韩老师写的如下
//修改节点的信息根据no编号来修改 即no编号不能改
//说明
//1. 根据newHeroNode 的 no 来修改即可
public void update(HeroNode newHeroNode){//判断是否为空if(head.next null){System.out.println(链表为空);return;}//找到需要修改的节点 根据no编号//定义一个辅助变量HeroNode temp head.next;boolean flag false;//表示是否找到该节点while (true){if(temp null){break;//已经遍历完链表}if(temp.no newHeroNode.no){//找到flag true;break;}temp temp.next;}//根据flag 判断是否找到要修改的节点if(flag){temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;}else {//没有找到System.out.println(修改失败 没有找到);}
}2.4 单链表节点的删除
自己写的代码如下
//节点的删除 根据no编号来删除
public void delete(int no){if (head.next null) {//说明此时空链表System.out.println(空链表 删除失败 请自重宝~~);return;}HeroNode temp head;while (temp.next ! null){if(temp.next.no no){temp.next temp.next.next; //将temp指向后移两位return;//结束函数}temp temp.next;//后移一位}//正常退出while 则说明没找到对应的编号System.out.println(没找到对应的编号);
}韩老师思路如下
从单链表中删除一个节点的思路temp.next temp.next.next被删除的节点 将不会有其它引用 会被垃圾回收机制回收 图5 单链表删除示意图 代码如下
//删除节点
//思路
//1. head 不能动 因此我们需要一个temp辅助找到带删除节点的前一个节点
//2. 说明在比较时 是temp.next.no 和 需要删除的节点的no比较
public void del(int no){HeroNode temp head;boolean flag false; //标志是否找到待删除节点的while (true){if(temp.next null){ //已经到链表的最后break;}if(temp.next.no no){//找到待删除节点的前一个节点tempflag true;break;}temp temp.next; //temp后移 遍历}if(flag){//找到//可以删除temp.next temp.next.next;}else {System.out.println(要删除的节点不存在);}
}3. 单链表面试题
3.1 求单链表中节点的个数不统计头节点
其中就是遍历一遍即可
3.2 查找单链表中的倒数第k个节点
//查找单链表中倒数第k个节点
//思路
//1. 编写一个方法 接收head节点 同时接收一个index
//2. index 表示是倒数第index个节点
//3. 先把链表从头到尾遍历得到链表的总长度
//4. 得到size后从链表的第一个开始遍历(size - index)个 就可以得到
//5. 找到则返回该节点 否则返回null
public static HeroNode findLastIndexNode(HeroNode head, int index) {//判断如果链表为空 返回nullif (head.next null) {return null; //没有找到}//第一次遍历得到链表的长度int size getLength(head);//第二次遍历 size - index 1位置 就是倒数的第k个节点//先做一个index的校验if (index 0 || index size) {return null;}//定义一个辅助变量HeroNode temp head.next;for (int i 0; i size - index; i) {temp temp.next;}return temp;
}3.3 单链表的反转
按照自己写的如下 思路就是每一次分别找到原链表中第size - i 个节点即新链表中第i个节点(包含头节点)然后进行连接 public static void reverse(HeroNode head) {if (head.next null) {//判断如果链表为空return; //没有找到}//第一次遍历得到链表的长度int size getLength(head);HeroNode temp1 null;HeroNode temp2 null;HeroNode temp3 head.next; //保存好原链表的第一个节点for (int i 0; i size; i) {temp1 temp3;for (int j 0; j size - i - 1; j) { //每个大循环依次从原链表中得到最后一个到第一个节点temp1 temp1.next;}
// System.out.println(temp1);temp2 head;for (int j 0; j i; j) { //每个大循环依次从新链表得到头节点到最后第二个节点temp2 temp2.next;}
// System.out.println(i temp1 temp2);temp2.next temp1; //重新将节点连接起来}temp3.next null; //切记 别忘了把新链表的最后一个(原链表的第一个)的next置null}韩老师的思路
先定义一个节点 reverseHead new HeroNode();从头到尾遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead的最前端原来的链表的head.nextreverseHead.next;
//将单链表反转
public static void reverseList(HeroNode head){//如果当前链表为空 或者只有一个节点 无需反转 直接返回if(head.next null || head.next.next null){return;}//定义一个辅助指针(变量) 帮助遍历原来的链表HeroNode cur head.next;HeroNode next null; //指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0,,);//遍历原来的链表 每遍历一个节点 就将其取出 并放在新的链表reverseHead的最前面while (cur ! null){next cur.next; //保存原链表中的下一个节点 cur.next reverseHead.next; //先让此节点的next域指向新链表的首位reverseHead.next cur; //再将新链表的头部指向此节点 实现cur节点插入cur next; //再将该cur引用重新指向原链表没有进行操作的节点}//将head.next 指向reverseHead.next 实现单链表的反转head.next reverseHead.next;
}不得不说啊这韩老师就是牛啊短短几行代码就搞定了其实就类似于插入将原链表的节点按顺序插入到新链表的头部与第一个节点之间此节点就作为新链表的第一个节点。那么最后原链表中的第i个节点就依次排到新链表中的size-i个节点中了。
3.4 从尾到头打印单链表
【方式一反向遍历 方式二Stack栈】
3.4.1 逆序输出 反向遍历
韩老师没演示这种 自己写的如下
//遍历逆序输出
public static void reverseOutput(HeroNode head){if (head.next null) {//判断如果链表为空return; //没有找到}//第一次遍历得到链表的长度int size getLength(head);HeroNode temp1 null;for (int i 0; i size; i) {temp1 head.next;for (int j 0; j size - i - 1; j) { //每个大循环依次从原链表中得到最后一个到第一个节点temp1 temp1.next;}System.out.println(temp1);}
}//递归逆序输出
public static void reverseOutputDiGui(HeroNode head){if(head.nextnull){//说明到头了}else {reverseOutputDiGui(head.next);}if(head.no ! 0){System.out.println(head);}
}3.4.2 Stack栈
韩老师思路如下 可以利用栈这个数据结构将各个节点压入到栈中 然后利用栈的先进后出的特点 就实现了逆序打印的效果 /*** author 小小低头哥* version 1.0* 演示Stack的使用*/
public class TestStack {public static void main(String[] args) {StackString stack new Stack();//入栈stack.add(jack);stack.add(tom);stack.add(smith);//出栈while (stack.size() 0){System.out.println(stack.pop());//POP就是将栈顶的数据取出}}
}//逆序输出
//利用栈这个数据结构将各个节点压入到栈中 然后利用栈的先进后出的特点 就实现了逆序打印的效果
public static void reversePrint(HeroNode head){if (head.next null) {//判断如果链表为空return; //空链表 不能打印}//创建一个栈 将各个节点压入栈StackHeroNode stack new Stack();HeroNode cur head.next;//将链表的所有节点压入栈while (cur ! null){stack.push(cur); //入栈cur cur.next; //后移}//将战中节点打印while (stack.size() 0){System.out.println(stack.pop()); //出栈 先进后出}
}3.5 合并两个有序的单链表合并之后的链表依然有序
自己苦战出来的试过输入没毛病的情况下 结果还可以
思路 以链表一为基准遍历链表一的每一个节点。在遍历每个链表一的节点期间将链表二中节点编号依次与此时遍历的链表一中 的节点编号进行比较满足条件的则接在新链表的最后一个节点上。由于是链表一二都是顺序排列所以一旦链表二中节点编号有不满足条件的则将此时链表一中遍历的节点接在新链表的最后一个节点上并跳出遍历链表二的循环继续遍历链表一中的下一个节点再接着上次链表二中第一个不满足的节点进行比较(注意不是重新与链表二中的节点一个个比较)。以此循环。
/*** 合并两个有序链表* 但是要确保输入的两个链表都是从小到大排序的 否则需要if(temp2.no temp1.no)中的 换成 * param head1* param head2* return 合并后的链表*/
public static HeroNode mergeList(HeroNode head1, HeroNode head2) {HeroNode newHero new HeroNode(0, , );//新建一个节点HeroNode end newHero; //保存newHero最后一个节点HeroNode temp1 head1.next; //链表一指针HeroNode temp2 head2.next; //链表二指针HeroNode next null; //保存下一个节点while (true){//以链表一进行顺序遍历while (true){//当链表二中有节点的no 小于链表一中的当前节点的no时if(temp2.no temp1.no){ //从小到大排序next temp2.next;end.next temp2;//将temp2插入到newHero最后end end.next; //将end后移一个temp2 next; //将temp2指向链表二的下一个节点继续与temp1比较}else {next temp1.next;end.next temp1;//将temp1插入到newHero最后end end.next; //将end后移一个if(next null){ //说明temp1比较完了 直接把temp2插入到newHero最后end.next temp2;return newHero;}temp1 next; //没比较完 则temp1后移break; //结束链表二中的节点与链表一中temp1节点的比较(因为是有序的 所以链表二后面的肯定也不符合条件)}if(temp2 null){//说明链表二中的节点都比较完毕 那么直接把链表一中剩下的节点temp1连接上新链表即可end.next temp1;return newHero;}}}
}
