Java数据结构与算法------单链表

相比于数组与队列，链表是一个非连续、非顺序的存储结构。

链表是以结点的方式来存储的（链式存储）每个结点都包含存储数据元素的数据域（data域），存储下一个结点地址的指针域（next域）链表的各个结点不一定是连续存储的链表分为带头结点的链表与没有头结点的链表，一般根据实际情况决定 逻辑图如下： 好了，单链表的大概结构已经了解，接下来是代码实现，这里我们以 插入梁山英雄好汉到单链表 为例：

1.首先我们要创建结点 我们需要定义一个类，包含英雄的编号，名字，昵称，以及指向下一个结点的next

class HeroNode{ public int no;//英雄的编号 public String name;//英雄的名字 public String nickname;//英雄的昵称 public HeroNode next;//指向下一个结点 //构造器 public HeroNode(int hno,String hname,String hnickname) { this.no=hno; this.name=hname; this.nickname=hnickname; } //为了显示方法，重写toString @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } }

2.接下来就要创建一个链表了

我们需要初始化一个头结点头结点在最前面，所以不能改变，以防止单链表找不到头结点 class SingleLinkedList{ private HeroNode head = new HeroNode(0,"",""); }

3.添加结点到单链表（不考虑编号顺序）

把新加入的结点放在链表的最后因为头结点不能动，所以定义一个辅助temp用于遍历，另temp=head当temp.next==null时，说明找到了链表最后的结点接着把新加入的结点赋给temp.next public void add(HeroNode heronode) { //因为head结点不能动，所以需要一个辅助遍历的temp HeroNode temp = head; //遍历链表，找到最后的结点 while(true) { if(temp.next == null) { break; } //如果没有没有找到最后结点 temp = temp.next; } //当退出循环时，temp就指向了链表的最后 //将最后这个结点的next 指向新的结点 temp.next=heronode; }

4.添加结点到链表（考虑编号顺序）

依然定义一个辅助temp如果新添加的结点编号已经存在，那么就不用再加入，所以定义一个布尔变量flag 用于判断新添加的结点编号是否已经存在当temp.next=null时，说明此时链表已经到了最后，那么插入链表后面当temp.next.no大于新结点的编号时，那么要插入的位置就已经找到，即temp的后面 new.next=temp.next temp.next=new如果temp.next.no等于新结点的编号时，那么准备加入的结点已经存在，flag设为true 此时需要把编号为3的结点插入链表，设该结点名称为new3那么需要new3.next=temp.next接着把temp指向新插入的结点temp.next=new3 public void addByOrder(HeroNode heronode) { //还是头结点不能动，所以定义一个辅助的temp,帮助找到要添加的位置 //因为是单链表，因此temp要找到 位于添加位置的前一个结点，否则添加不了 HeroNode temp= head; boolean flag = false;//标识添加的编号是否存在，默认为false while(true) { if(temp.next==null) {//说明此事temp已经在链表的最后 break; } if(temp.next.no>heronode.no) {//位置就在temp的后面插入（因为如果此时条件成立，那么说明要加入的结点排名就在temp与temp.next之间） break; }else if(temp.next.no==heronode.no) {//如果此时条件成立，说明此时新加入的结点的编号已经存在 flag = true;//说明编号存在 break; } temp=temp.next; } //判断flag的值 if(flag) {//此时说明要加入的结点的编号已经存在，因此不能加入 System.out.printf("准备插入的英雄编号%d已经存在，不能加入\n",heronode.no); } else { //插入到链表中，temp的后面 heronode.next=temp.next; temp.next=heronode; } }

5.修改指定结点

依然定义temp与flag当temp.no等于新结点的no时，就找到了需要修改的结点把新结点的名字与昵称赋给老结点 public void update(HeroNode newheronode) {//根据这个新结点的no来修改 //判断是否为空 if(head.next==null) { System.out.println("链表为空"); return; } //找到需要修改的结点 还是先定义一个辅助结点 HeroNode temp = head; 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.printf("没有找到编号%d的结点",newheronode.no); } }

6.删除指定结点

依然定义temp与flag我们通过把需要删除的结点 的上一个结点的next指向 需要删除结点的下一个结点 来实现删除指定结点因此我们需要先找到需要删除结点的上一个结点 假设为temp 那么需要删除的结点为temp.next 下一个结点为temp.next.next当temp.next.no=指定的结点no时，找到了指定结点那么可以另temp.next=temp.next.next public void delete(int no) { //判断是否为空 if(head.next==null) { System.out.println("链表为空"); return; } HeroNode temp = head; boolean flag = false;//判断是否找到需要删除结点的前一个结点 while(true) { if(temp == null) { break;//表示链表已经遍历结束 } if(temp.next.no==no) {//找到了需要删除的结点 flag = true; break; } temp=temp.next; } if(flag) {//temp为被删除结点的上一个结点，temp.next为被删除结点，temp.next.next为被删除结点的下一个结点 temp.next=temp.next.next;//将被删除结点的上一个结点的next指向 被删除结点的下一个结点 }else { System.out.println("没有找到要删除的结点"); } }

7.遍历整个链表

public void list() { //先判断链表是否为空 if(head.next==null) { System.out.println("链表为空"); return; } //因为头结点不能动，因此需要辅助变量遍历 HeroNode temp = head.next; while(true) { //判断是否到链表最后 if(temp==null) { break; } //如果不为空，输出结点的信息 System.out.println(temp); //将temp后移 temp=temp.next; } }

接着就可以进行测试了，这里我不一一测试，以下为总的源代码： 里面会有详细的注释供参考

package Linkedlist; public class SingleLinklist { public static void main(String[] args) { //先创建几个结点 HeroNode heroNode = new HeroNode(1,"宋江","及时雨"); HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟"); HeroNode heroNode3 = new HeroNode(3,"吴用","智多星"); HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头"); //创建链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //第一种方法加入，即在链表尾部加入，例如：已经加入了编号为2和4的，那么在插入编号为3的要在2与4之后 此时链表内容：head-2-4-3 // singleLinkedList.add(heroNode); // singleLinkedList.add(heroNode3); // singleLinkedList.add(heroNode2); // singleLinkedList.add(heroNode4); //第二种方法加入，即按排名顺序，例如：已经加入了编号为2和编号为4的，那么在插入编号为3的要在2与4之间 此时链表内容：head-2-3-4 singleLinkedList.addByOrder(heroNode); singleLinkedList.addByOrder(heroNode3); singleLinkedList.addByOrder(heroNode2); singleLinkedList.addByOrder(heroNode4); //显示一下 singleLinkedList.list(); System.out.println(); //修改结点 HeroNode newheronode = new HeroNode(1,"送江","毛毛雨"); singleLinkedList.update(newheronode); singleLinkedList.list(); System.out.println(); // HeroNode heroNode5 = new HeroNode(2,"卢俊义","玉麒麟"); singleLinkedList.delete(2); singleLinkedList.list(); } } //创建一个单链表SingleLinkedList，管理英雄人物 class SingleLinkedList{ //先初始化一个头结点，因为在遍历时，头结点在最前面，所以头结点不变，以防单链表找不到头结点 private HeroNode head = new HeroNode(0,"",""); //添加结点到单向链表 当不考虑编号顺序时 //找到当前链表的最后一个结点，将最后这个结点的next指向新的结点 public void add(HeroNode heronode) { //因为head结点不能动，所以需要一个辅助遍历的temp HeroNode temp = head; //遍历链表，找到最后的结点 while(true) { if(temp.next == null) { break; } //如果没有没有找到最后结点 temp = temp.next; } //当退出循环时，temp就指向了链表的最后 //将最后这个结点的next 指向新的结点 temp.next=heronode; } //第二种添加方式，根据英雄的排名插入到指定位置(如果有这个排名则添加失败，即这名英雄已经在链表) public void addByOrder(HeroNode heronode) { //还是头结点不能动，所以定义一个辅助的temp,帮助找到要添加的位置 //因为是单链表，因此temp要找到 位于添加位置的前一个结点，否则添加不了 HeroNode temp= head; boolean flag = false;//标识添加的编号是否存在，默认为false while(true) { if(temp.next==null) {//说明此事temp已经在链表的最后 break; } if(temp.next.no>heronode.no) {//位置就在temp的后面插入（因为如果此时条件成立，那么说明要加入的结点排名就在temp与temp.next之间） break; }else if(temp.next.no==heronode.no) {//如果此时条件成立，说明此时新加入的结点的编号已经存在 flag = true;//说明编号存在 break; } temp=temp.next; } //判断flag的值 if(flag) {//此时说明要加入的结点的编号已经存在，因此不能加入 System.out.printf("准备插入的英雄编号%d已经存在，不能加入\n",heronode.no); } else { //插入到链表中，temp的后面 heronode.next=temp.next; temp.next=heronode; } } //根据编号修改结点信息， public void update(HeroNode newheronode) {//根据这个新结点的no来修改 //判断是否为空 if(head.next==null) { System.out.println("链表为空"); return; } //找到需要修改的结点 还是先定义一个辅助结点 HeroNode temp = head; 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.printf("没有找到编号%d的结点",newheronode.no); } } //删除结点 public void delete(int no) { //判断是否为空 if(head.next==null) { System.out.println("链表为空"); return; } HeroNode temp = head; boolean flag = false;//判断是否找到需要删除结点的前一个结点 while(true) { if(temp == null) { break;//表示链表已经遍历结束 } if(temp.next.no==no) {//找到了需要删除的结点 flag = true; break; } temp=temp.next; } if(flag) {//temp为被删除结点的上一个结点，temp.next为被删除结点，temp.next.next为被删除结点的下一个结点 temp.next=temp.next.next;//将被删除结点的上一个结点的next指向 被删除结点的下一个结点 }else { System.out.println("没有找到要删除的结点"); } } //显示链表 public void list() { //先判断链表是否为空 if(head.next==null) { System.out.println("链表为空"); return; } //因为头结点不能动，因此需要辅助变量遍历 HeroNode temp = head.next; while(true) { //判断是否到链表最后 if(temp==null) { break; } //如果不为空，输出结点的信息 System.out.println(temp); //将temp后移 temp=temp.next; } } } //创建一个结点 class HeroNode{ public int no;//英雄的编号 public String name;//英雄的名字 public String nickname;//英雄的昵称 public HeroNode next;//指向下一个结点 //构造器 public HeroNode(int hno,String hname,String hnickname) { this.no=hno; this.name=hname; this.nickname=hnickname; } //为了显示方法，重写toString @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } }