标签： Java 数据结构 算法

作者： Maxchen

版本： V1.0.1

日期： 2020/4/2

1.单向链表——原理

假如我们现在要存放一些物品，但是没有足够大的空间将所有的物品一次性放下（电脑中使用链式存储不是因为内存不够先事先说明一下…，具体原因后续会说到），同时设定我们因为脑容量很小，为了节省空间，只能记住一件物品位置。此时我们很机智的找到了解决方案：存放物品时每放置一件物品就在物品上贴一个小纸条，标明下一件物品放在那里，只记住第一件物品的位置，寻找的时候从第一件物品开始寻找，通过小纸条我们可以找到所有的物品，这就是链式存储。链表实现的时候不再像线性表一样只存储数据即可，还有下一个数据元素的地址，因此先定义一个节点类(Node)，记录物品信息和下一件物品的位置，我们把物品本身叫做数据域，存储下一件物品地址信息的小纸条称为引用域。链表结构示意图如下：¹

image.png-26.5kB

提示: 寻找物品的时候发现了一个问题，我们从一件物品找下一件物品的时候很容易，但是如果要找上一件物品就得从头开始找，真的很麻烦。为了解决这个问题我们又机智了一把，模仿之前的做法，在存放物品的时候多放置一个小纸条记录上一件物品的位置，这样就可以很快的找到上一件物品了。我们把这种方式我们称为双向链表，前面只放置一张小纸条的方式称为单向链表。

2.单向链表——代码实现

代码整体实现如下图所示：首先构建一个单链表，然后初始化头节点，随后往下面添加节点，最后打印整个链表的数据。

单链表.png-13.5kB

2.1单向链表——新增与查询

第一步： 对节点进行定义，我们这里以平常经常使用的几个大品牌电脑为例，包含以下字段：序号、品牌名称、品牌外号、指向下一个节点。

class ComputerNode {public int no; //序号public String name; //品牌名称public String nickname; //品牌外号public ComputerNode next; //指向下一个节点//构造器public ComputerNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}//为了显示方法，我们重新toString@Overridepublic String toString() {return "ComputerNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

第二步： 定义一个单链表并初始化头节点

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

第三步： 往这个单链表添加节点

class SingleLinkedList {……//添加节点到单向链表public void add(ComputerNode computerNode) {//因为head节点不能动，因此我们需要一个辅助遍历 tempComputerNode temp = head;//遍历链表，找到最后while(true) {//找到链表的最后if(temp.next == null) {//next字段为空，则表示为链表结尾break;}//如果没有找到最后,next字段不为空 将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后这个节点的next指向新的节点temp.next = computerNode;}
}

第四步： 定以显示链表的方法

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

第五步： 我们对以上方法进行一次整体的测试，可以看到一种现象，链表最后展示的结果是按照代码添加的顺序排列的

public class SingleLinkedListDemo {public static void main(String[] args) {//先创建节点ComputerNode computer1 = new ComputerNode(1, "联想", "美帝良心想");ComputerNode computer2 = new ComputerNode(2, "惠普", "铁板熊掌普");ComputerNode computer4 = new ComputerNode(4, "戴尔", "人傻钱多戴");ComputerNode computer3 = new ComputerNode(3, "华硕", "奸若磐石硕");//创建要给链表并将节点加入到链表SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(computer1);singleLinkedList.add(computer2);singleLinkedList.add(computer4);singleLinkedList.add(computer3);//显示链表，最后得到的结果如下，显然链表最后展示的结果是按照代码添加的顺序排列的// ComputerNode [no=1, name=联想, nickname=美帝良心想]// ComputerNode [no=2, name=惠普, nickname=铁板熊掌普]// ComputerNode [no=4, name=戴尔, nickname=人傻钱多戴]// ComputerNode [no=3, name=华硕, nickname=奸若磐石硕]singleLinkedList.list();}}

image.png-31.3kB

第六步： 我们在前面基础上增加一个要求：按照编号顺序排序，并且重复编号的值不能添加

class SingleLinkedList {……//第二种方式在添加电脑时，根据编号顺序将电脑插入到指定位置public void addByOrder(ComputerNode computerNode) {//头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了ComputerNode temp = head;boolean flag = false; // flag标志添加的编号是否存在，默认为falsewhile(true) {if(temp.next == null) {//说明temp已经在链表的最后break;}if(temp.next.no > computerNode.no) { //位置找到，就在temp的后面插入break;} else if (temp.next.no == computerNode.no) {//说明希望添加的heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移，遍历当前链表}//判断flag 的值if(flag) { //不能添加，说明编号存在System.out.printf("准备插入的电脑的编号 %d 已经存在了, 不能加入\n", computerNode.no);} else {//插入到链表中, temp的后面computerNode.next = temp.next;temp.next = computerNode;}}}

第七步： 将add方法改为addByOrder并测试,发现链表能按照编号顺序添加节点

public class SingleLinkedListDemo {public static void main(String[] args) {……//创建要给链表并将节点加入到链表SingleLinkedList singleLinkedList = new SingleLinkedList();/*singleLinkedList.add(computer1);singleLinkedList.add(computer2);singleLinkedList.add(computer4);singleLinkedList.add(computer3);*/singleLinkedList.addByOrder(computer1);singleLinkedList.addByOrder(computer2);singleLinkedList.addByOrder(computer4);singleLinkedList.addByOrder(computer3);……}}

image.png-40kB

第八步： 我们测试一下重复添加某个节点会出现何种情况

public class SingleLinkedListDemo {public static void main(String[] args) {……//重复添加computer3singleLinkedList.addByOrder(computer1);singleLinkedList.addByOrder(computer2);singleLinkedList.addByOrder(computer3);singleLinkedList.addByOrder(computer3);……}}

image.png-31.8kB

2.2单向链表——修改

单向链表修改参考下图，直接找到对应的节点修改内容即可

image.png-30.6kB

第一步： 定义单链表修改方法

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

第二步： 测试单链表修改方法

public class SingleLinkedListDemo {public static void main(String[] args) {……System.out.println("修改后");ComputerNode newComputerNode = new ComputerNode(3, "宏碁", "偷工减料碁");singleLinkedList.update(newComputerNode);singleLinkedList.list();……}}

image.png-57.2kB

2.3单向链表——删除

链表删除操作如下图，修改节点指向下两个节点，随后下一个节点Target node被垃圾回收²

image.png-39.9kB

第一步： 定义链表删除方法

class SingleLinkedList {……//删除节点public void del(int no) {ComputerNode temp = head;boolean flag = false; // 标志是否找到待删除节点的while(true) {if(temp.next == null) { //已经到链表的最后break;}if(temp.next.no == no) {//找到的待删除节点的前一个节点tempflag = true;break;}temp = temp.next; //temp后移，遍历}//判断flagif(flag) { //找到//可以删除temp.next = temp.next.next;}else {System.out.printf("要删除的 %d 节点不存在\n", no);}}
}

第二步： 测试链表删除方法

public class SingleLinkedListDemo {public static void main(String[] args) {……System.out.println("删除后");singleLinkedList.del(3);singleLinkedList.list();……}}

image.png-46.2kB

3.单向链表——整体代码

下面附上这次单向链表的所有代码

package com.maxchen.demo.linkedlist;/*** @ClassName: SingleLinkedListDemo* @Description: TODO* @Author Maxchen* @Date 2020/4/1 18:32* @Version V1.0.0*/
public class SingleLinkedListDemo {public static void main(String[] args) {//先创建节点ComputerNode computer1 = new ComputerNode(1, "联想", "美帝良心想");ComputerNode computer2 = new ComputerNode(2, "惠普", "铁板熊掌普");ComputerNode computer3 = new ComputerNode(3, "华硕", "奸若磐石硕");ComputerNode computer4 = new ComputerNode(4, "戴尔", "人傻钱多戴");//创建要给链表并将节点加入到链表SingleLinkedList singleLinkedList = new SingleLinkedList();/*singleLinkedList.add(computer1);singleLinkedList.add(computer2);singleLinkedList.add(computer4);singleLinkedList.add(computer3);*/singleLinkedList.addByOrder(computer1);singleLinkedList.addByOrder(computer2);singleLinkedList.addByOrder(computer4);singleLinkedList.addByOrder(computer3);//显示链表，最后得到的结果如下，显然链表最后展示的结果是按照代码添加的顺序排列的// ComputerNode [no=1, name=联想, nickname=美帝良心想]// ComputerNode [no=2, name=惠普, nickname=铁板熊掌普]// ComputerNode [no=4, name=戴尔, nickname=人傻钱多戴]// ComputerNode [no=3, name=华硕, nickname=奸若磐石硕]System.out.println("删除前");singleLinkedList.list();//        System.out.println("修改后");
//        ComputerNode newComputerNode = new ComputerNode(3, "宏碁", "偷工减料碁");
//        singleLinkedList.update(newComputerNode);System.out.println("删除后");singleLinkedList.del(3);singleLinkedList.list();}}class SingleLinkedList {//先初始化一个头节点,头不存放具体的数据private ComputerNode head = new ComputerNode(0, "", "");//添加节点到单向链表public void add(ComputerNode computerNode) {//因为head节点不能动，因此我们需要一个辅助遍历 tempComputerNode temp = head;//遍历链表，找到最后while (true) {//找到链表的最后if (temp.next == null) {//next字段为空，则表示为链表结尾break;}//如果没有找到最后,next字段不为空 将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后这个节点的next指向新的节点temp.next = computerNode;}//第二种方式在添加电脑时，根据编号顺序将电脑插入到指定位置public void addByOrder(ComputerNode computerNode) {//头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了ComputerNode temp = head;boolean flag = false; // flag标志添加的编号是否存在，默认为falsewhile (true) {if (temp.next == null) {//说明temp已经在链表的最后break;}if (temp.next.no > computerNode.no) { //位置找到，就在temp的后面插入break;} else if (temp.next.no == computerNode.no) {//说明希望添加的heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移，遍历当前链表}//判断flag 的值if (flag) { //不能添加，说明编号存在System.out.printf("准备插入的电脑的编号 %d 已经存在了, 不能加入\n", computerNode.no);} else {//插入到链表中, temp的后面computerNode.next = temp.next;temp.next = computerNode;}}//修改节点的信息, 根据no编号来修改，即no编号不能改.//说明//1. 根据 newComputerNode 的 no 来修改即可public void update(ComputerNode newComputerNode) {//判断是否空if (head.next == null) {System.out.println("链表为空~");return;}//找到需要修改的节点, 根据no编号//定义一个辅助变量ComputerNode temp = head.next;boolean flag = false; //表示是否找到该节点while (true) {if (temp == null) {break; //已经遍历完链表}if (temp.no == newComputerNode.no) {//找到flag = true;break;}temp = temp.next;}//根据flag 判断是否找到要修改的节点if (flag) {temp.name = newComputerNode.name;temp.nickname = newComputerNode.nickname;} else { //没有找到System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newComputerNode.no);}}//删除节点public void del(int no) {ComputerNode temp = head;boolean flag = false; // 标志是否找到待删除节点的while (true) {if (temp.next == null) { //已经到链表的最后break;}if (temp.next.no == no) {//找到的待删除节点的前一个节点tempflag = true;break;}temp = temp.next; //temp后移，遍历}//判断flagif (flag) { //找到//可以删除temp.next = temp.next.next;} else {System.out.printf("要删除的 %d 节点不存在\n", no);}}//显示链表[遍历]public void list() {//判断链表是否为空if (head.next == null) {System.out.println("链表为空");return;}//因为头节点，不能动，因此我们需要一个辅助变量来遍历ComputerNode temp = head.next;while (true) {//判断是否到链表最后if (temp == null) {break;}//输出节点的信息System.out.println(temp);//将temp后移， 一定小心temp = temp.next;}}}class ComputerNode {public int no; //序号public String name; //品牌名称public String nickname; //品牌外号public ComputerNode next; //指向下一个节点//构造器public ComputerNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}//为了显示方法，我们重新toString@Overridepublic String toString() {return "ComputerNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}