3.链表 ====== 3.1.链表概念介绍 ---------------- - 链接方式存储的线性表简称为链表（Linked List） - 链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 - 以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。 3.1.1.链接存储方法 ~~~~~~~~~~~~~~~~~~ - 链表的具体存储表示为： - 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） - 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） - 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 3.1.2.链表分类结构 ~~~~~~~~~~~~~~~~~~ 在实际中，链表的分类结构非常多，比如： - 带头、不带头 - 单向、双向 - 循环、非循环 3.1.3.节点结构 ~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.1.3_1.png 3.1.4.带头单向链表内存结构图 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.1带头单向链表内存结构图.jpg 3.1.5.带头单向链表添加功能代码实现 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ NodeManager.java类代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: LinkedListDemo.java * @Package com.tuling.linked * @Description: * @author: 北京图灵学院 * @date: 2019年11月23日 下午4:23:32 * @version V1.0 * @Copyright: */ package com.tuling.linked; /** * @ClassName LinkedListDemo * @Description * @Author 北京图灵学院 */ public class LinkedListDemo { /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { NodeManager2 nm = new NodeManager2(); nm.add("A"); nm.add("B"); nm.add("C"); nm.add("D"); nm.add("E"); nm.show(); } } class NodeManager2{ //头结点，不存储数据，只是记录位置。 private Node2 head = new Node2(""); /** * * @Title: add * @Description:添加节点 * 1、变遍历链表，找到当前链表的最后一个节点 * 2、将最后一个节点的 next 指向新节点。 * @param: data * @return: void * @throws */ public void add(String data) { //首先准备一个辅助遍历的临时节点对象 Node2 currNode = head; //循环遍历，找到最后一个节点。 while(true) { if(currNode.next == null) {//条件成立，说明找到了最后一个节点 break; } //辅助节点后移一位 currNode = currNode.next; } //当循环完成，此时 currNode 指向当前链表的最后一个节点 //把当前链表的最后一个节点的 next 指向要添加的新节点。 currNode.next = new Node2(data); } /** * * @Title: show * @Description:显示当前链表的所有数据 * @param: * @return: void * @throws */ public void show() { //判断当前链表是否为空 if(head.next == null) { System.out.println("链表为空！"); return; } //辅助遍历的临时节点对象。 Node2 currNode = head.next; while(true) { if(currNode == null) { break; } //打印当前节点的数据 System.out.print(currNode.data + " "); //节点后移 currNode = currNode.next; } System.out.println(); } /** * * @ClassName Node * @Description 节点对象 * @Author 北京图灵学院 */ class Node2{ //要存储的数据 private String data; //下一个节点的指针 private Node2 next; /** * @param data */ public Node2(String data) { this.data = data; } } } 3.1.6.带头单向列表删除内存图 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.2带头单向链表删除操作内存图.jpg 3.1.7.带头单向链表删除功能代码实现 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ NodeManager.java类代码如下： .. code:: java class NodeManager2{ //头结点，不存储数据，只是记录位置。 private Node2 head = new Node2(""); /** * * @Title: del * @Description:删除节点 * 1、需要一个辅助遍历的节点对象，记录要删除的节点 * 2、找到要删除的节点之后 * currNode.next = currNode.next.next; * @param: data * @return: void * @throws */ public void del(String data) { //准备一个临时节点，用来记录要删除的节点 Node2 currNode = head; //准备一个变量，用来记录是否找到要删除的节点 boolean flag = false; while(true) { //说明已经到了当前链表的最后一个节点，没有找到要删除的节点 if(currNode.next == null) { break; } //判断当前节点的下一个节点的 data 是否和要删除的 data 相等 if(currNode.next.data.equals(data)) { flag = true; break; } //节点后移 currNode = currNode.next; } //根据标记变量的值来确定如何操作 if(flag) { currNode.next = currNode.next.next; }else { System.out.println("要删除的节点不存在！"); } } /** * * @ClassName Node * @Description 节点对象 * @Author 北京图灵学院 */ class Node2{ //要存储的数据 private String data; //下一个节点的指针 private Node2 next; /** * @param data */ public Node2(String data) { this.data = data; } } } 完整代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: LinkedListDemo.java * @Package com.tuling.linked * @Description: * @author: 北京图灵学院 * @date: 2019年11月23日 下午4:23:32 * @version V1.0 * @Copyright: */ package com.tuling.linked; /** * @ClassName LinkedListDemo * @Description * @Author 北京图灵学院 */ public class LinkedListDemo { /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { NodeManager2 nm = new NodeManager2(); nm.add("A"); nm.add("B"); nm.add("C"); nm.add("D"); nm.add("E"); nm.show(); System.out.println("----------删除操作--------------"); nm.del("E"); nm.show(); } } class NodeManager2{ //头结点，不存储数据，只是记录位置。 private Node2 head = new Node2(""); /** * * @Title: add * @Description:添加节点 * 1、变遍历链表，找到当前链表的最后一个节点 * 2、将最后一个节点的 next 指向新节点。 * @param: data * @return: void * @throws */ public void add(String data) { //首先准备一个辅助遍历的临时节点对象 Node2 currNode = head; //循环遍历，找到最后一个节点。 while(true) { if(currNode.next == null) {//条件成立，说明找到了最后一个节点 break; } //辅助节点后移一位 currNode = currNode.next; } //当循环完成，此时 currNode 指向当前链表的最后一个节点 //把当前链表的最后一个节点的 next 指向要添加的新节点。 currNode.next = new Node2(data); } /** * * @Title: del * @Description:删除节点 * 1、需要一个辅助遍历的节点对象，记录要删除的节点 * 2、找到要删除的节点之后 * currNode.next = currNode.next.next; * @param: data * @return: void * @throws */ public void del(String data) { //准备一个临时节点，用来记录要删除的节点 Node2 currNode = head; //准备一个变量，用来记录是否找到要删除的节点 boolean flag = false; while(true) { //说明已经到了当前链表的最后一个节点，没有找到要删除的节点 if(currNode.next == null) { break; } //判断当前节点的下一个节点的 data 是否和要删除的 data 相等 if(currNode.next.data.equals(data)) { flag = true; break; } //节点后移 currNode = currNode.next; } //根据标记变量的值来确定如何操作 if(flag) { currNode.next = currNode.next.next; }else { System.out.println("要删除的节点不存在！"); } } /** * * @Title: show * @Description:显示当前链表的所有数据 * @param: * @return: void * @throws */ public void show() { //判断当前链表是否为空 if(head.next == null) { System.out.println("链表为空！"); return; } //辅助遍历的临时节点对象。 Node2 currNode = head.next; while(true) { if(currNode == null) { break; } //打印当前节点的数据 System.out.print(currNode.data + " "); //节点后移 currNode = currNode.next; } System.out.println(); } /** * * @ClassName Node * @Description 节点对象 * @Author 北京图灵学院 */ class Node2{ //要存储的数据 private String data; //下一个节点的指针 private Node2 next; /** * @param data */ public Node2(String data) { this.data = data; } } } 3.2.双向链表 ------------ 3.2.1.双向链表内存结构图 ~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.3带头双向链表内存结构图.jpg 3.2.2.双向链表删除示意图 ~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.4带头双向链表删除内存结构图.jpg .. image:: _static/3.链表/3.5带头双向链表内存流程图.jpg 3.2.3.双向链表操作分析： ~~~~~~~~~~~~~~~~~~~~~~~~ - 添加：（尾插法） - 先遍历找到链表的最后一个节点 - 将最后一个节点的 next 指向新节点 - currNode.next = newNode; - 将新节点的 pre 指向最后一个节点 - newNode.pre = currNode; - 删除： - 双向链表可以删除自己 - 遍历找到要删除的节点 currNode - currNode 节点的前一个节点的后一个节点指向 currNode 的后一个节点 - currNode.pre.next = currNode.next; - currNode.next 为空什么都不做 - currNode.next 不为空 - currNode.next.pre = currNode.pre; - 遍历：和单向链表类似，双向链表还可以从后向前遍历 3.2.4.双向链表代码实现 ~~~~~~~~~~~~~~~~~~~~~~ .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: DoubleLinkedListDemo.java * @Package com.tuling.linked * @Description: * @author: 北京图灵学院 * @date: 2019年11月23日 下午6:30:44 * @version V1.0 * @Copyright: */ package com.tuling.linked; /** * @ClassName DoubleLinkedListDemo * @Description * @Author 北京图灵学院 */ public class DoubleLinkedListDemo { /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { NodeManager nm = new NodeManager(); nm.add("A"); nm.add("B"); nm.add("C"); nm.add("D"); nm.add("E"); nm.show(); System.out.println(); System.out.println("------------删除操作-----------------"); nm.del("E"); nm.show(); } } class NodeManager{ private Node headNode = new Node(""); /** * * @Title: add * @Description:双向链表添加操作（尾插法） * 1、准备一个辅助遍历的临时节点 * 2、遍历链表，找到当前链表的最后一个节点 * 3、将最后一个节点的 next 指向新节点 * 4、将新节点的 pre 指向链表的最后一个节点（这里就是 currNode 辅助遍历的节点对象） * @param: data * @return: void * @throws */ public void add(String data) { //创建一个临时节点对象 Node currNode = headNode; //遍历链表，找到最后一个节点 while(true) { if(currNode.next == null) { break; } //节点后移 currNode = currNode.next; } //当循环结束，currNode 指向当前链表的最后一个节点 Node addNode = new Node(data); currNode.next = addNode; addNode.per = currNode; } /** * * @Title: del * @Description:双向链表删除操作 * 1、判断当前链表是否为空 * 2、遍历链表，找到要删除的节点 * 找到 flag = true; * 未找到 flag = false; * 3、根据标记变量处理 * @param: data * @return: void * @throws */ public void del(String data) { //先判断当前链表是否为空 if(headNode.next == null) { System.out.println("链表为空！"); return; } //准备一个辅助遍历的节点对象 Node currNode = headNode.next; //标记变量 boolean flag = false; while(true) { if(currNode == null) { break; } if(currNode.data.equals(data)) { flag = true; break; } //节点后移 currNode = currNode.next; } //循环结束，根据 flag 的值确定操作 if(flag) { /** * 删除的原理： * 1、当前节点的前一个节点的下一个节点 指向 当前节点的下一个节点 * 2、当前节点的下一个节点的前一个节点 指向 当前节点的前一个节点 */ currNode.per.next = currNode.next; if(currNode.next != null) { currNode.next.per = currNode.per; } }else { System.out.println("为找到要删除的节点！"); } } /** * * @Title: show * @Description:显示链表中的所有数据 * 1、先判断当前链表是否为空 * 2、遍历链表，显示每个节点的数据 * @param: * @return: void * @throws */ public void show() { if(headNode.next == null) { System.out.println("链表为空！"); return; } Node currNode = headNode.next; while(true) { if(currNode == null) { break; } //打印当前节点的数据 System.out.print(currNode.data + " "); //节点后移 currNode = currNode.next; } } class Node{ //要存储的数据 private String data; //前一个节点的指针 private Node per; //后一个节点的指针 private Node next; /** * @param data */ public Node(String data) { this.data = data; } } } 3.3.循环链表 ------------ 3.3.1.循环链表内存结构图 ~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: _static/3.链表/3.6单向循环链表内存结构流程图.jpg 3.3.2.循环链表操作分析 ~~~~~~~~~~~~~~~~~~~~~~ 1. 添加 1. 空链表添加第一个节点 2. 正常添加节点 1. 利用辅助节点，找到链表的最后一个节点 2. 将新节点添加到最后 2. 删除 1. 删除首节点 1. 如果删除首节点后 size为0，说明链表为空。 2. 正常删除首节点 ``注意：需要先找到当前链表的最后一个节点，改变尾结点的next指向新的首节点。`` 2. 删除正常节点 3.3.3.循环链表代码实现 ~~~~~~~~~~~~~~~~~~~~~~ .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: CircleNodeManager.java * @Package com.tuling.linked * @Description: * @author: 北京图灵学院 * @date: 2019年11月30日 下午3:50:01 * @version V1.0 * @Copyright: */ package com.tuling.linked; /** * @ClassName CircleNodeManager * @Description * @Author 北京图灵学院 */ public class CircleNodeManager { //自己维护首节点 private Node first; //记录当前链表的长度，也可用作空链的判断条件。 private int size; /** * */ public CircleNodeManager() { init(); } /** * @Title: init * @Description: * @param: * @return: void * @throws */ private void init() { first = new Node(-1); //形成环形链表 first.setNext(first); size = 0; } /** * @return the first */ public Node getFirst() { return first; } /** * * @Title: add * @Description:环形链表的添加操作 * 1、添加的是首节点： * 如果：size == 0;需要将 data 添加到 first 节点中。 * 2、添加其他节点： * 2.1> 使用辅助节点遍历找到当前链表的最后一个节点 条件为：currNode.next == first; * 2.2> currNode 的 next 应该指向新节点 addNode * 2.3> 新添加的节点的 next 应该指向首节点，以形成环形链表。 * 3、size+1 * @param: data * @return: void * @throws */ public void add(int data) { //判断当前链表是否为空 if(size == 0) { first.setData(data); }else { //添加其他的节点 Node currNode = first; while(true) { if(currNode.next == first) { break; } currNode = currNode.getNext(); } //当循环结束，此时 currNode 指向当前链表的最后一个节点 Node addNode = new Node(data); currNode.setNext(addNode); addNode.setNext(first); } size++; } /** * * @Title: show * @Description:显示当前链表中的所有数据 * @param: * @return: void * @throws */ public void show() { //判断当前链表是否为空 if(size == 0) { System.out.println("链表为空！"); return; } Node currNode = first; while(true) { System.out.print(currNode.getData() + " --> "); if(currNode.getNext() == first) { break; } //节点后移 currNode = currNode.getNext(); } System.out.println(); } /** * * @Title: del * @Description:环形链表删除操作 * 1、删除的是正常节点 * 1.1 遍历链表找到要删除的节点对象，使用 currNode 记录要删除的节点对象 * 1.2 如果找到要删除的节点对象，使用标记变量记录，根据标记变量的值确定操作 * 1.3 删除的原理：设置当前节点的下一个节点指向当前节点的下一个节点的下一个节点 * 2、删除的是首节点 * 2.1> 删除首节点后链表为空 * 直接调用 init 方法，重新初始化即可。 * 2.2> 删除首节点后链表中还有数据 * 2.2.1> 遍历找到当前链表的最后一个节点 * 2.2.2> 将 first 指向它的下一个节点 * 2.2.3> 将最后一个节点的 next 指向新的 first * @param: data * @param: @return * @return: Node * @throws */ public Node del(int data) { Node delNode = null; Node currNode = first; //先判断当前链表是否为空 if(size == 0) { System.out.println("链表为空！"); return delNode; } if(first.getData() == data) {//要删除的是首节点 //记录要删除的节点，后面需要return delNode = first; if(size-1 == 0) {//删除首节点后链表为空 init(); }else { //循环遍历找到最后一个节点 while(true) { if(currNode.getNext() == first) { break; } //临时节点后移 currNode = currNode.getNext(); } //当循环结束，此时 currNode 指向当前链表的最后一个节点 first = first.getNext(); currNode.setNext(first); size--; } }else {//删除的是其他节点 boolean flag = false; while(true) { if(currNode.getNext().getData() == data) { flag = true; break; } if(currNode.getNext() == first) { break; } currNode = currNode.getNext(); } //循环结束，根据 flag 的值确定操作 if(flag) {//找到了要删除的节点 //记录要删除的节点 delNode = currNode.getNext(); currNode.setNext(currNode.getNext().getNext()); size--; }else { System.out.println("要 删除的节点不存在！"); } } return delNode; } class Node{ private int data; private Node next; /** * @param data */ public Node(int data) { super(); this.data = data; } /** * @return the data */ public int getData() { return data; } /** * @param data the data to set */ public void setData(int data) { this.data = data; } /** * @return the next */ public Node getNext() { return next; } /** * @param next the next to set */ public void setNext(Node next) { this.next = next; } } } 测试代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: CircleLinkedDemo.java * @Package com.tuling.linked * @Description: * @author: 北京图灵学院 * @date: 2019年11月30日 下午4:00:27 * @version V1.0 * @Copyright: */ package com.tuling.linked; import com.tuling.linked.CircleNodeManager.Node; /** * @ClassName CircleLinkedDemo * @Description * @Author 北京图灵学院 */ public class CircleLinkedDemo { /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { CircleNodeManager cnm = new CircleNodeManager(); cnm.add(1); cnm.add(3); cnm.add(5); cnm.add(7); cnm.add(9); cnm.show(); System.out.println("---------------------------"); cnm.del(1); cnm.show(); } } 3.3.4.约瑟夫环 ~~~~~~~~~~~~~~ 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 .. image:: _static/3.链表/3.7约瑟夫环.jpg 3.3.5.解决约瑟夫环 ~~~~~~~~~~~~~~~~~~ 修改测试代码： .. code:: java /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { CircleNodeManager cnm = new CircleNodeManager(); //先手动形成一个约瑟夫环 int nums = 41; int space = 3; for(int i = 1; i <= nums; i++) { cnm.add(i); } //开始出圈 Node currNode = cnm.getFirst(); while(currNode.getNext() != currNode) { //首先需要将游标后移 space 次 for(int j = 1; j < space; j++) { //游标后移 currNode = currNode.getNext(); } //获取要自杀的节点对象 Node delNode = cnm.del(currNode.getData()); if(delNode != null) { System.out.print(delNode.getData() + ", "); } //一定要记得游标后移一位 currNode = currNode.getNext(); } System.out.println(); System.out.println("最后活着的是：" + cnm.getFirst().getData()); } }