【数据结构和算法】(基础篇二)—

链表

数组最麻烦的地方就是其在建立之后大小固定，对于增删数据很不方便。链表的出现解决了这个问题，链表的元素不是在内存中连续存储的，而是通过指针链接在一起的节点集合，这样的设计让链表有了动态的大小。链表是树和图结构的基础。

链表由一个个的节点构成，这些节点设计的不同会产生不同的特性和使用场景，链表主要有三种类型：单链表、双向链表和环形链表。

单链表

因为链表的内存不是连续的，为了能够让上一个节点找到下一个节点的位置，每个节点除了存储自身数据之外，还需要存储指向下一个节点的地址，这两部分称为data数据域和next指针域。

单链表的设计中，还可以根据需要选择有没有头尾节点，头尾节点的存在可以简化插入和删除操作，比如要删除第一个节点的话，有头结点的情况让其next域指向第二个节点即可；通常头节点经常使用作为指示链表的开始，尾节点让其next域为null即可。头节点的存在也可以用于判断一个链表是否为空（看其是否指向null）。

在这里插入图片描述

链表的逻辑结构示意图：

在这里插入图片描述

【示例】创建一个单链表用来存放梁山的108好汉，完成数据的增删改查，需要有两种添加数据的方法，一种是直接在链表尾部添加数据，另一种是按照英雄的座次排名进行插入数据

单链表结尾增加数据：让新节点的next指向null，遍历得到原本的尾节点，让尾节点的next指向新节点

单链表中间增加数据：先找到需要增加数据的位置，比如要在下标为n的位置增加一个节点，此时让新节点先指向n+1个节点，然后让第n个节点指向新节点。这个顺序不能反了，如果先让第n个节点指向新节点，则n+1后面的节点就都找不到了。

public class SingleLinkedListDemo {public static void main(String[] args) {//TestHeroNode hr1 = new HeroNode(1,"宋江", "及时雨");HeroNode hr2 = new HeroNode(2,"卢俊义", "玉麒麟");HeroNode hr3 = new HeroNode(3,"吴用", "智多星");HeroNode hr4 = new HeroNode(4,"林冲", "豹子头");SingleLinkedList sll = new SingleLinkedList();sll.addByOrder(hr1);sll.addByOrder(hr4);sll.addByOrder(hr3);sll.addByOrder(hr2);sll.list();System.out.println("修改后的数据-------------------");HeroNode nhr = new HeroNode(2,"卢俊义1", "玉麒麟1");sll.update(nhr);sll.list();System.out.println("删除后的数据-------------------");sll.del(hr1);sll.list();sll.del(hr2);sll.list();sll.del(hr3);sll.list();sll.del(hr4);sll.list();}
}class SingleLinkedList{// 头节点HeroNode head = new HeroNode(0,"","");public SingleLinkedList() {this.head = head;}// 添加数据public void add(HeroNode heroNode){// 先使用一个临时变量找到链表尾，将数据添加到链表尾HeroNode temp = head;while (true){if (temp.next == null){// 找到了链表尾break;}// 没找到链表尾就继续遍历temp = temp.next;}// 在循环结束后，得到的temp就处于链表尾temp.next = heroNode;}// 按照英雄排名的顺序插入数据public void addByOrder(HeroNode heroNode){HeroNode temp = head;boolean flag = false;while (true){if (temp.next == null){ //已经把整个链表都遍历玩了break;}if (temp.next.no > heroNode.no){  // 就是正确的位置break;} else if (temp.next.no == heroNode.no) {  // 已经存在相同数据flag = true;break;}temp = temp.next;}if (flag){  //System.out.printf("您要插入的第%d位的英雄数据已经存在，添加数据失败\n", heroNode.no);}else{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.next==null){// 遍历结束，没有找到对应的nobreak;} else if (temp.no == newheroNode.no) {// 找到正确的位置flag = true;break;}temp = temp.next;}if (flag){temp.name = newheroNode.name;temp.nickname = newheroNode.nickname;}else {System.out.printf("链表中没有排名为 %d 的英雄，无法修改", newheroNode.no);}}// 删除链表中的数据public void del(HeroNode target){HeroNode temp = head;boolean flag = false;while (true){if (temp.next.no == target.no){// temp的下一个数据就是需要删除的数据flag = true;break;}temp = temp.next;}if (flag){// 如果没有变量指向被删除的内存空间，它就会被垃圾回收机制回收掉temp.next = temp.next.next;}else {System.out.println("你所找的数据不在链表中，无法删除");}}// 查看链表中的数据public void list(){if (head.next == null){System.out.println("链表为空，没有数据");return;}HeroNode temp = head;while (true){if (temp.next == null){// 找到了链表尾break;}// 没找到链表尾就继续遍历System.out.println(temp);temp = temp.next;}System.out.println(temp);}
}class HeroNode{int no;String name;String nickname;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 + '\'' +'}';}
}

【面试算法题目】单链表的逆序打印

思路：方法一，先用上面的方法把单链表反转，再进行打印，但是会破坏原来的链表结构，不推荐使用；方法二，使用栈先入后出的特性实现来实现

    // 单链表逆序打印public static void reversePrint(HeroNode head){// 判断是否为空if (head.next == null){return;}// 创建一个栈Stack<HeroNode> stack = new Stack();// 遍历HeroNode cur = head.next;while (cur != null){stack.add(cur);cur = cur.next;}// 从栈中取数据while (stack.size()>0){System.out.println(stack.pop());}}

双向链表

单向链表中的每一个节点都只能够指向下一个节点，也就是说，只能进行单向的遍历。双向链表可以解决这个问题，双向链表（Doubly Linked List）是一种线性数据结构，其中的每个元素都是一个节点，每个节点包含三个部分：数据、指向其前一个节点的指针和指向其后一个节点的指针。与单向链表相比，双向链表中的节点具有额外的指向前一个节点的链接，这使得在链表中进行前后移动都变得可能。

插入：可以在链表的头部、尾部或任意位置插入一个新的节点。插入时需要更新新节点的前后指针以及相邻节点的前后指针。
删除：可以从链表中删除一个指定节点。删除时需要更新被删除节点的前一个节点和后一个节点的指针。
遍历：可以从前向后或从后向前遍历链表，访问每一个节点。
查找：在链表中查找特定值的节点，可以通过遍历来实现。
反转：双向链表可以很容易地反转，只需要交换所有节点的前后指针即可。

【示例】创建一个双向链表完成上面的需求

public class DoubleLinkedListDemo {public static void main(String[] args) {HeroNode2 hr1 = new HeroNode2(1,"宋江", "及时雨");HeroNode2 hr2 = new HeroNode2(2,"卢俊义", "玉麒麟");HeroNode2 hr3 = new HeroNode2(3,"吴用", "智多星");HeroNode2 hr4 = new HeroNode2(4,"林冲", "豹子头");DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.addByOrder(hr1);doubleLinkedList.addByOrder(hr3);doubleLinkedList.addByOrder(hr2);doubleLinkedList.addByOrder(hr4);doubleLinkedList.list();/*System.out.println("删除最后一个数据");doubleLinkedList.del(hr4);doubleLinkedList.list();System.out.println("修改第二个数据后：");HeroNode2 hr5 = new HeroNode2(2,"卢俊义2", "玉麒麟2");doubleLinkedList.update(hr5);doubleLinkedList.list();*/}
}class DoubleLinkedList{// 头节点HeroNode2 head = new HeroNode2(0,"","");//返回头节点public HeroNode2 getHead() {return head;}public DoubleLinkedList() {this.head = head;}// 按照英雄座次排序插入节点public void addByOrder(HeroNode2 heroNode){HeroNode2 temp = head;boolean flag = false;while (true){if (temp.next == null){ //已经把整个链表都遍历玩了break;}if (temp.next.no > heroNode.no){  // 就是正确的位置，在temp的后面插入数据break;} else if (temp.next.no == heroNode.no) {  // 已经存在相同数据flag = true;break;}temp = temp.next;}if (flag){  //System.out.printf("您要插入的第%d位的英雄数据已经存在，添加数据失败\n", heroNode.no);}else{if (temp.next != null){temp.next.pre = heroNode;heroNode.next = temp.next;}temp.next = heroNode;heroNode.pre = temp;}}// 修改节点数据public void update(HeroNode2 newheroNode){// 根据英雄的排名（no）修改信息if(head.next == null){System.out.println("链表为空，不能修改");return;}HeroNode2 temp = head;boolean flag = false;while (true){if (temp.next==null){// 遍历结束，没有找到对应的nobreak;} else if (temp.no == newheroNode.no) {// 找到正确的位置flag = true;break;}temp = temp.next;}if (flag){temp.name = newheroNode.name;temp.nickname = newheroNode.nickname;}else {System.out.printf("链表中没有排名为 %d 的英雄，无法修改", newheroNode.no);}}// 删除数据，自我删除public void del(HeroNode2 target){// 直接自我删除，从第一个有效数据节点开始HeroNode2 temp = head.next;boolean flag = false;while (temp != null){if (temp.no == target.no){// temp的下一个数据就是需要删除的数据flag = true;break;}temp = temp.next;}if (flag){// 如果没有变量指向被删除的内存空间，它就会被垃圾回收机制回收掉temp.pre.next = temp.next;// 只有不是尾节点时才执行if (temp.next !=null){temp.next.pre = temp.pre;}}else {System.out.println("你所找的数据不在链表中，无法删除");}}// 添加数据到链表尾public void add(HeroNode2 heroNode){// 先使用一个临时变量找到链表尾，将数据添加到链表尾HeroNode2 temp = head;while (true){if (temp.next == null){// 找到了链表尾break;}// 没找到链表尾就继续遍历temp = temp.next;}// 在循环结束后，得到的temp就处于链表尾temp.next = heroNode;heroNode.pre = temp;}// 遍历public void list(){// 先判断链表是否为空if (head.next == null){System.out.println("链表为空，没有数据");return;}HeroNode2 temp = head;while (true){if (temp.next == null){// 找到了链表尾break;}// 没找到链表尾就继续遍历System.out.println(temp.next);temp = temp.next;}}
}class HeroNode2{int no;String name;String nickname;HeroNode2 next;HeroNode2 pre;HeroNode2 head;public HeroNode2(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}@Overridepublic String toString() {return "HeroNode2{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

环形链表

环形链表（Circular Linked List）是一种特殊的链表形式，其中最后一个节点的“next”指针不是指向None，而是指向链表的头节点，形成了一个闭环。这种结构使得从链表的任何一点出发都能通过“next”指针遍历整个链表并回到起点，从而提供了连续访问所有元素的能力。

环形链表可以是单向的，也可以是双向的。在双向环形链表中，除了每个节点都有一个指向前一个节点的“prev”指针外，最后一个节点的“next”指针会指向头节点，而头节点的“prev”指针也会指向最后一个节点。

创建环形单链表：先创建一个象征链表逻辑开始的头节点，最开始的头结点也应该指向自己，在链表为空时，head.next指向head本身，可以作为一种标志，表明链表当前没有其他节点。头结点除了在添加第一个数据节点时都不应该进行改动。

添加数据到环形单链表末尾时，需要一个临时变量作为链表的逻辑结尾，temp.next == first表示到达逻辑结尾

添加数据到环形单链表中间的时候，需要先进行遍历找到要添加的前一个位置

遍历环形单链表：使用一个临时变量实现，当temp.next == first表示遍历结束

【示例】约瑟夫环问题：假设有一群人围成一圈，从某个人开始报数，每数到第m个人，就将这个人从圈中移除，然后从下一个人继续报数，直到只剩下最后一个人为止。问题要求确定在初始状态下，哪个人会是最后存活下来的。

创建一个辅助变量helper指向first的前一个，用来帮助实现出队列（因为单链表的删除数据需要将辅助变量指向前一个）
在开始出队列之前，先把first指向指定的位置，helper也要同步移动
根据指定的数数个数，进行循环，每次的first指向的节点就是需要被删除的节点，first = first.next; helper.next = first.

package dataStructure.list;public class Josephues {public static void main(String[] args) {// 测试创建和遍历循环链表CircleLinkedList circleLinkedList = new CircleLinkedList();circleLinkedList.add(5);circleLinkedList.showBoys();circleLinkedList.countBoy(1,2,5);}
}class CircleLinkedList{// 先创建first变量Boy first = null;/*** 约瑟夫出圈问题* @param startNo   从哪里开始数* @param countNo   每次数几个数* @param sum    最初的总节点个数*/public void countBoy(int startNo, int countNo, int sum){// 数据校验if(first == null || startNo < 1 || startNo > sum || countNo > sum){System.out.println("输入参数有误");return;}// 创建辅助变量，置于队尾Boy helper = first;while (true){helper = helper.getNext();if (helper.getNext() == first){break;}}// 将first移动到指定的位置，即startNofor (int i = 0; i < startNo-1; i++) {first = first.getNext();helper = helper.getNext();}// 进行出队列，每次循环countNo次，直到链表中只剩下一个节点（helper == first）while (true){for (int i = 0; i < countNo-1; i++) {first = first.getNext();helper = helper.getNext();}//此时的first 指向的就是要出队列的节点System.out.printf("小孩%d出圈\n", first.getNo());first = first.getNext();helper.setNext(first);if (helper == first){break;}}System.out.println("队列中的最后一个孩子编号为：" + first.getNo());}// 添加数据, nums 表示需要添加的个数public void add(int nums){if (nums < 1){System.out.println("nums的值不正确");return;}Boy curboy = null;for (int i = 1; i <= nums ; i++) {// 根据i作为no创建boy对象Boy boy = new Boy(i);if (i == 1){ //第一个节点需要覆盖掉firstfirst = boy;first.setNext(first);curboy = first;}curboy.setNext(boy);boy.setNext(first);curboy = boy;}}// 遍历public void showBoys(){// 判断链表是否为空if(first == null){System.out.println("链表中没有数据了。。。");return;}// 使用一个临时变量辅助遍历Boy curboy = first;while (true){System.out.println("当前小孩的编号为：" + curboy.getNo());if (curboy.getNext() == first){break;}curboy = curboy.getNext();}}
}class Boy{private int no;private Boy next;public int getNo() {return no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}public Boy(int no) {this.no = no;}
}