java数据结构实现单链表

1.什么是链表：

链表是有序的列表，但是它在内存中可以以不连续空间存放，存储如下

根据上图，可以发现：

1. 链表是以节点的方式来存储，是链式存储
2. 每个节点包含 data 域，next域:指向下一个节点.
3. 链表的各个节点不一定是连续存储.
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定（头节点一般不存储数据，只用于作为标识）
   因而带头节点的单链表的逻辑结构可以看作：
   

2.单链表的实现

需求：
使用带head头节点的单链表；
每个节点data域有no（No.顺序）和name字段，和指向下一节点的next；
需要实现对每个节点的增删改查操作

实现思路与代码：

2.1 首先我们创建这个节点类：

//定义SingleNode，每个SingleNode对象就是一个节点 class SingleNode{ public int no; public String name; //no和name可以认为是节点的数据部分 public SingleNode next; //指向下一个节点 //构造器 public SingleNode(int no, String name) { this.no = no; this.name = name; } //为了显示方法，重新显示toString(不打印next节点，否则或造成将后续节点全部打印) @Override public String toString() { return "SingleNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } } 

2.2 然后我们写一个链表类，初始化一个头节点，然后在链表类中编写链表的增删改查方法：

//定义一个SingleLinkedList 管理链表 class SingleLinkedList{ //先初始化一个头节点,一般头节点不存储数据 private SingleNode head=new SingleNode(0,""); } 

2.3 添加节点的方法（这里按照需求，可以有两种添加方式）：

2.3.1 直接添加到链表的尾部

//添加节点到单向链表 //当不考虑编号顺序时 //1.找到当前节点的最后节点 //2.将最后这个节点的next指向 新的节点 public void add(SingleNode singleNode){ //因为head头不能动，因此我们需要一个辅助遍历temp(类似于指针)，先将temp指向head节点 SingleNode temp=head; //遍历链表，找到最后 while (true){ //找到链表的最后 if(temp.next==null){ break; } //如果没有找到最后，继续指向下一个 temp=temp.next; } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next，指向新的节点 temp.next=singleNode; } 

2.3.2 按照no将节点插入到指定位置（如果有这个no，则添加失败，并给出提示）
思路分析如下：

1. 首先找到新添加的节点的位置是通过辅助变量temp(指针),通过遍历来搞定
2. temp指向位于要添加位置的前一个节点
3. 要添加的节点.next = temp.next
4. 将temp.next=新添加的节点

//第二种方式在添加节点时，根据no将节点插入到指定位置 //如果有这个no，则添加失败，并给出提示 public void addByOrder(SingleNode singleNode){ //因为头节点不能动，需要一个辅助指针来帮助找到添加的位置（指向前一位） //因为单链表，因此我们找的tmep是位于添加位置的前一个节点，否则插入不了 SingleNode temp=head; boolean flag=false;//flag标志添加的编号是否存在，默认为false while(true){ if(temp.next==null){//说明temp已经在链表的最后 break; } if(temp.next.no>singleNode.no){ //位置找到，就在temp的后面插入 break; }else if(temp.next.no==singleNode.no){ //说明希望添加的编号已经存在 flag=true;//说明编号存在 break; } temp=temp.next; //后移，遍历当前链表 } //是否添加，判断flag的值 if(flag){//不能添加，说明编号存在 System.out.printf("准备插入的节点的编号 %d 已经存在了，不能加入\n",singleNode.no); }else { //插入到链表中，tmep的后面 singleNode.next=temp.next; temp.next=singleNode; } } 

2.3 修改节点data
思路分析如下：
（这里我们直接传入一个newNode，通过no找到节点，然后替换data）

1. 先找到该节点,通过遍历
2. temp.name = newNode.name ;

 //修改节点的信息，根据no编号来修改，即no编号不能改。 //说明:根据newNode的no来修改即可 public void update(SingleNode newNode){ //判断是否为空 if(head.next==null){ System.out.println("链表为空~"); return; } //找到需要修改的节点，根据no编号 //先定义一个辅助遍历 SingleNode temp=head.next; boolean flag=false;//表示是否找到该节点 while(true){ if(temp==null){ break; //已经遍历完链表 } if(temp.no==newNode.no){ //找到 flag=true; break; } temp=temp.next; } //根据flag 判断是否找到要修改的节点 if(flag){ temp.name=newNode.name; }else { System.out.printf("没有找到 编号 %d 的节点，不能修改\n",newNode.no); } } 

2.4 删除节点：
思路分析如下：

1. 我们先找到需要删除的这个节点的前一个节点temp
2. temp.next = temp.next. next
3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

//删除节点 //思路： //头节点不能动，需要一个辅助指针来帮助找到待删除节点的前一个节点 //2.我们在比较时，时temp.next.no和需要删除的节点的no比较 public void del(int no){ SingleNode temp=head; boolean flag=false; //标志是否找到待删除节点 while(true){ if(temp.next==null){ //已经到链表末尾 break; } if(temp.next.no==no){ //找到的待删除节点的前一个节点temp flag=true; break; } temp=temp.next; //temp后移，遍历 } if(flag){//找到。可以删除 temp.next=temp.next.next; //删除的节点会因为垃圾回收机制被回收 }else { System.out.printf("要删除的%d 节点不存在\n",no); } } 

2.5 遍历链表

//显示链表，通过辅助变量 遍历 public void list(){ //判断链表是否为空 if (head.next == null) { System.out.printf("链表为空"); return; } //因为头节点，不能动，因此我们需要一个辅助变量来变量 SingleNode temp=head.next; while (true){ //判断是否到链表最后 if(temp==null){ break; } //不为空，输出节点信息 System.out.println(temp); //将temp后移 temp=temp.next; } } 

2.6 组合代码，编写主函数进行测试

public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 SingleNode node1 = new SingleNode(1, "北京"); SingleNode node2 = new SingleNode(2, "上海"); SingleNode node3 = new SingleNode(3,"广州"); SingleNode node4 = new SingleNode(4, "深圳"); //创建一个单链表 SingleLinkedList singleLinkedList=new SingleLinkedList(); /*
        //加入
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        */ //加入按照编号的顺序 singleLinkedList.addByOrder(node1); singleLinkedList.addByOrder(node2); singleLinkedList.addByOrder(node3); singleLinkedList.addByOrder(node4); singleLinkedList.list(); //测试修改节点的代码 SingleNode newHeroNode=new SingleNode(3,"重庆"); //显示 singleLinkedList.update(newHeroNode); System.out.printf("修改后的链表：\n"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); System.out.printf("删除后的链表情况：\n"); singleLinkedList.list(); } } 

运行结果：

完整代码实现：

这里我们可以以内部类的方式编写该代码：
SingleLinkedListDemo.java:

/*
* 单链表
* */ public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 SingleNode node1 = new SingleNode(1, "北京"); SingleNode node2 = new SingleNode(2, "上海"); SingleNode node3 = new SingleNode(3,"广州"); SingleNode node4 = new SingleNode(4, "深圳"); //创建一个单链表 SingleLinkedList singleLinkedList=new SingleLinkedList(); /*
        //加入
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        */ //加入按照编号的顺序 singleLinkedList.addByOrder(node1); singleLinkedList.addByOrder(node2); singleLinkedList.addByOrder(node3); singleLinkedList.addByOrder(node4); singleLinkedList.list(); //测试修改节点的代码 SingleNode newHeroNode=new SingleNode(3,"重庆"); //显示 singleLinkedList.update(newHeroNode); System.out.printf("修改后的链表：\n"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); System.out.printf("删除后的链表情况：\n"); singleLinkedList.list(); } } //定义一个SingleLinkedList 管理链表 class SingleLinkedList{ //先初始化一个头节点，头节点不要动,一般头节点不存储数据 private SingleNode head=new SingleNode(0,""); //添加节点到单向链表 //当不考虑编号顺序时 //1.找到当前节点的最后节点 //2.将最后这个节点的next指向 新的节点 public void add(SingleNode singleNode){ //因为head头不能动，因此我们需要一个辅助遍历temp(类似于指针)，先将temp指向head节点 SingleNode temp=head; //遍历链表，找到最后 while (true){ //找到链表的最后 if(temp.next==null){ break; } //如果没有找到最后，继续指向下一个 temp=temp.next; } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next，指向新的节点 temp.next=singleNode; } //第二种方式在添加节点时，根据no将节点插入到指定位置 //如果有这个no，则添加失败，并给出提示 public void addByOrder(SingleNode singleNode){ //因为头节点不能动，需要一个辅助指针来帮助找到添加的位置（指向前一位） //因为单链表，因此我们找的tmep是位于添加位置的前一个节点，否则插入不了 SingleNode temp=head; boolean flag=false;//flag标志添加的编号是否存在，默认为false while(true){ if(temp.next==null){//说明temp已经在链表的最后 break; } if(temp.next.no>singleNode.no){ //位置找到，就在temp的后面插入 break; }else if(temp.next.no==singleNode.no){ //说明希望添加的编号已经存在 flag=true;//说明编号存在 break; } temp=temp.next; //后移，遍历当前链表 } //是否添加，判断flag的值 if(flag){//不能添加，说明编号存在 System.out.printf("准备插入的节点的编号 %d 已经存在了，不能加入\n",singleNode.no); }else { //插入到链表中，tmep的后面 singleNode.next=temp.next; temp.next=singleNode; } } //修改节点的信息，根据no编号来修改，即no编号不能改。 //说明:根据newNode的no来修改即可 public void update(SingleNode newNode){ //判断是否为空 if(head.next==null){ System.out.println("链表为空~"); return; } //找到需要修改的节点，根据no编号 //先定义一个辅助遍历 SingleNode temp=head.next; boolean flag=false;//表示是否找到该节点 while(true){ if(temp==null){ break; //已经遍历完链表 } if(temp.no==newNode.no){ //找到 flag=true; break; } temp=temp.next; } //根据flag 判断是否找到要修改的节点 if(flag){ temp.name=newNode.name; }else { System.out.printf("没有找到 编号 %d 的节点，不能修改\n",newNode.no); } } //删除节点 //思路： //头节点不能动，需要一个辅助指针来帮助找到待删除节点的前一个节点 //2.我们在比较时，时temp.next.no和需要删除的节点的no比较 public void del(int no){ SingleNode temp=head; boolean flag=false; //标志是否找到待删除节点 while(true){ if(temp.next==null){ //已经到链表末尾 break; } if(temp.next.no==no){ //找到的待删除节点的前一个节点temp flag=true; break; } temp=temp.next; //temp后移，遍历 } if(flag){//找到。可以删除 temp.next=temp.next.next; //删除的节点会因为垃圾回收机制被回收 }else { System.out.printf("要删除的%d 节点不存在\n",no); } } //显示链表，通过辅助变量 遍历 public void list(){ //判断链表是否为空 if (head.next == null) { System.out.printf("链表为空"); return; } //因为头节点，不能动，因此我们需要一个辅助变量来变量 SingleNode temp=head.next; while (true){ //判断是否到链表最后 if(temp==null){ break; } //不为空，输出节点信息 System.out.println(temp); //将temp后移 temp=temp.next; } } } //定义SingleNode，每个SingleNode对象就是一个节点 class SingleNode{ public int no; public String name; //no和name可以认为是节点的数据部分 public SingleNode next; //指向下一个节点 //构造器 public SingleNode(int no, String name) { this.no = no; this.name = name; } //为了显示方法，重新显示toString(不打印next节点，否则或造成将后续节点全部打印) @Override public String toString() { return "SingleNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } } 

本文地址：https://blog.csdn.net/qq_28840013/article/details/108035096