1、线性表之链表

  1. 1、链表-概述：
  2.     1-1、n个节点离散分配，彼此通过指针相连，每个元素包含两个节点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域，首节点没有前驱节点，尾节点没有后续节点。
  3.     1-2、确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。
  4.     1-3、链表一个链表节点的数据结构：value值+next指针。
  5.     1-4、是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 对于链表的新增，删除等操作(在找到指定操作位置后），仅需处理结点间的引用即可。
  6.     1-5、对于链表的新增，删除等操作(在找到指定操作位置后),时间复杂度为O(1)， 而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。
  8. 2、链表的-优点：
  9.     2-1、链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
  10.     2-2、添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
  12. 3、链表的-缺点：
  13.     3-1、因为含有大量的指针域，占用空间较大；
  14.     3-2、查找元素需要遍历链表来查找，非常耗时。
  16. 4、适用场景：
  17.     4-1、数据量较小，需要频繁增加，删除操作的场景
  19. 5、链表-单链表-举例Demo
  20.     public class Node {
  21.         public Node next;    //下一个节点
  22.         private Object data;    //链表存储的数据
  23.         public Node(Object data) {
  24.           this.data = data;
  25.         }
  26.     }
  28.     //循环遍历-单链表
  29.     public static void getDataByLoop(Node node){
  30.         while (node != null) {
  31.         System.out.println(node.getData()+"");
  32.         node = node.getNext();
  33.         }
  34.     }
  36.    //递归遍历-单链表
  37.    public static void getDataByRecursion(Node node) {
  38.            if (node == null) {
  39.             return;
  40.         }
  41.         System.out.println(node.getData()+" ");    //15 1 9
  42.         getDataByRecursion(node.getNext());
  43.    }
  45.    //链表：链表是一种物理存储单元上非连续、非顺序的存储结构
  46.    //特点：插入、删除时间复杂度O(1) 查找遍历时间复杂度0(N) 插入快、查找慢
  47.    public static void main(String[] args) {
  48.          Node node=new Node(15);
  49.          node.next=new Node(1);
  50.          node.next.next=new Node(9);
  51.          System.out.println("使用while循环遍历链表");
  52.          getDataByLoop(node);
  53.          System.out.println();
  54.          System.out.println("使用递归遍历链表");
  55.          getDataByRecursion(node);
  56.          System.out.println();
  57.    }

1.1、链表-分类

  1. 1、链表分类：根据指针的指向，链表能形成不同的结构
  2.     1-1、单向链表: 一个节点指向下一个节点。
  3.     1-2、双向链表: 一个节点有两个指针域。
  4.     1-3、环形链表: 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环。
  5.         1-3-1、应用：比如：单向环形链表->约瑟夫问题?

1.2、链表之单链表分析

  1. 1、链表之单链表分析：
  2.     1-1、单链表结构：head头节点->首节点->xxxx->尾节点->next[null]
  3.         1-1-1、头节点：不存放具体的数据，只用来表时单链表头next。
  4.     1-2、
  6. 2、单链表遍历-伪代码：
  7.     /**
  8.      * 遍历链表
  9.      * @param head 头节点
  10.      */
  11.     public static void traverse(Node head) {
  12.         //临时节点，从首节点开始
  13.         Node temp = head.next;
  14.         // 为null则说明到了链表的尾部
  15.         while (temp != null) {
  16.             System.out.println("链表数据：" + temp.data);
  17.             //继续下一个,
  18.             temp = temp.next;
  19.         }
  20.     }
  21. 3、单链表-添加(创建)-伪代码：
  22.     3-1、先创建一个head头结点，
  23.     3-2、当不考虑编号顺序时,每添加一个节点，直接加入到链表的最后(遍历链表)
  24.     3-3、考虑编号顺序时，遍历链表：
  25.          3-3-1、修改：
  26.             1、先创建一个head头结点
  27.             2、根据编号找到需要修改信息的节点(遍历链表)
  28.             public static void update(int value, Node Head){
  29.             //初始化要加入的节点
  30.                 Node newNode = new Node(value);
  31.                 //临时节点,因为head节点不能动，所以需要一个辅助遍历节点 temp
  32.                 Node temp = head;
  33.                 // 找到尾节点,temp.next为null,则说明找到尾节点了。
  34.                 while (temp.next != null) {
  35.                     // 找到节点信息
  36.                     if(temp.no = newNode.no){
  37.                         // 将找到节点信息更新为新的信息
  38.                         temp.xxx = newNode.xxx;
  39.                     }
  40.                     // 没有找到最后，则将temp后移
  41.                     temp = temp.next;
  42.                 }
  43.                 // temp.next=null，说明到了尾节点了，将最后这个节点的next 指向新的节点
  44.                 // 到链表的尾部了，还没匹配上需要修改节点的信息，不做处理
  45.             }
  46.         3-3-2、删除：
  47.             1、先创建一个head头结点
  48.             2、先找到需要删除的这个节点的前一个节点(temp.next.no = delNode.no)
  49.             3、将待删除节点的前一个节点下一个指向(就是指向待删除的节点)，修改为下下一个节点(将指向待删除节点的前一个节点指针指向待删除节点的下一个节点)
  50.             temp.next = temp.next.next
  51.             4、被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收掉。

1.2.1、链表之单链表分析代码示例

  1. 1、当不考虑编号顺序时，思路：
  2.     1.找到当前链表的最后节点
  3.     2.将最后这个节点的next，指向新的节点
  4.         public static void addData(int value, Node head) {
  5.             //初始化要加入的节点
  6.             Node newNode = new Node(value);
  7.             //临时节点,因为head节点不能动，所以需要一个辅助遍历节点 temp
  8.             Node temp = head;
  9.             // 找到尾节点,temp.next为null,则说明找到尾节点了。
  10.             while (temp.next != null) {
  11.                 // 没有找到最后，则将temp后移
  12.                 temp = temp.next;
  13.             }
  14.             // temp.next=null，说明到了尾节点了，将最后这个节点的next 指向新的节点
  15.             temp.next = newNode;
  16.         }
  18.         //显示链表（遍历）
  19.         public void list(){
  20.             //判断链表是否为空
  21.             if(head.next==null){
  22.                 System.out.println("链表为空");
  23.                 return;
  24.             }
  25.             //因为头结点，不能动，因此我们需要一个辅助变量来遍历
  26.             Node temp = head.next;
  27.             //判断是否到链表最后,为null则表示到链表最后
  28.             while(temp != null){
  29.                 //输出节点信息
  30.                 System.out.println(temp.toString());
  31.                 //将next后移 一定注意
  32.                 temp = temp.next;
  33.             }
  34.         }
  36. 2、考虑编号顺序时，思路：
  37.     1、找到新添加的节点的位置，通过辅助遍历(指针)，遍历链表
  38.     // 因为单链表，因为我们找到temp是位于添加位置的前一个节点
  39.     temp = temp.next; // 后移，遍历当前链表
  40.     2、将新节点的next指向temp的next,
  41. newNode.next = temp.next;
  42.     3、将temp的next指向新节点
  43.         temp.next = newNode;
  44.     // 考虑编号顺序时,添加新的节点
  45.     public void addByOrder(HeroNode heroNode){
  46.         //因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
  47.         //因为单链表，因为我们找到temp是位于添加位置的前一个节点，否则插入不了
  48.         HeroNode temp =head;
  49.         boolean flag = false;//flag 标识添加的编号是否为存在，默认为false
  50.         while(true){
  51.             if(temp.next==null){//说明temp已经在链表最后
  52.                 break;
  53.             }
  54.             if(temp.next.no>heroNode.no){//位置找到，就在temp的后面插入
  55.                 break;
  56.             }else if(temp.next.no==heroNode.no){//说明希望添加的heroNode编号已经存在 不能再添加（规定）
  57.                 flag =true;//说明编号存在
  58.                 break;
  59.             }
  60.             temp =temp.next;//后移，遍历当前链表
  61.         }
  62.         //判断flag的值
  63.         if(flag){//不能添加，说明编号存在
  64.             System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
  65.         }else {
  66.             //插入到链表中 temp后面
  67.             heroNode.next=temp.next;
  68.             temp.next=heroNode;
  69.         }
  70.     }

1.2.2、链表之单链表-面试题

  1. 1、求一个单链表的节点个数(头结点不保存数据)：注意检查链表是否为空
  2.      public int getLength(Node head) {
  3.         if (head == null) {
  4.             return 0;
  5.         }
  6.         int length = 0;
  7.     // 头结点不保存数据,统计有效节点时：需要将头结点去掉
  8.     // Node current = head.next;
  9.         Node current = head;
  10.         while (current != null) {
  11.             length++;
  12.             // 将节点后移
  13.             current = current.next;
  14.         }
  15.         return length;
  16.     }
  17. 2、查找单链表中倒数第K个节点
  18.     思路：1、先定义temp变量接收head节点，index：表示倒数第k个节点的节点下标
  19.      2、链表遍历，得到链表的长度(size)
  20.      3、再次遍历链表，范围：size - index
  22. 3、单链表的反转
  23.     /** 
  24.     head节点信息:
  25.     head = {HeroNode@631} "HeroNode{no=0, name='', nickname=''}"
  26.             head.next = {HeroNode@632} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  27.             head.next.next = {HeroNode@633} "HeroNode{no=2, name='卢俊义', nickname='玉麒麟'}"
  29.         第一次遍历：
  30.         cur = {HeroNode@632} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  31.             next = {HeroNode@633} "HeroNode{no=2, name='卢俊义', nickname='玉麒麟'}"
  32.             reverseHead = {HeroNode@654} "HeroNode{no=0, name='', nickname=''}"
  33.             head = {HeroNode@631} "HeroNode{no=0, name='', nickname=''}"
  34.             head.next = {HeroNode@632} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  35.             reverseHead.next = {HeroNode@632} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  37.         public void reverse(){
  38.             //如果当前链表为空，或者只有一个节点，无需反转，直接发返回
  39.             if(head.next==null||head.next.next==null){
  40.                 return;
  41.             }
  42.             //定义一个辅助指针（变量），帮助我们遍历原来的链表
  43.             HeroNode cur = head.next;
  44.             HeroNode next = null;//指向当前节点的下一个节点
  45.             HeroNode reverseHead = new HeroNode(0,"","");
  46.             //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reversehead的最前端
  47.             while(cur!=null)//cur=null说明遍历结束
  48.             {
  49.                 next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
  50.                 cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
  51.                 reverseHead.next=cur;//将cur连接到新的链表上
  52.                 cur = next;//让cur后移
  53.             }
  54.             //连接head.next指向reverseHead.next 实现单链表反转
  55.             head.next = reverseHead.next;
  56.         }
  57.     */
  58.     3-1、头结点插入方式
  59.     /**
  60.     头结点插入法的实质是重新创建了一个新的链表，通过遍历待反转链表，将链表每一个节点插入到创建的链表中，然后的到的这个创建的链表就是反转后的链表。
  61.     */
  62.     public static ListNode reverseListByInsert(ListNode listNode){
  63.             //定义一个带头节点的,保存反转之后的链表信息
  64.             ListNode resultList = new ListNode(-1); // 此时反转的链表只有一个头结点
  65.             //循环节点，初始值为待反转的链表
  66.             ListNode p = listNode;
  67.     // 遍历待反转的链表
  68.             while(p!= null){
  69.                 //定义一个链式链表，用来保存p.next的值，用于下一次循环
  70.                 // 第一次遍历时，p.next = {1}，故ListNode tempList = {1}
  71.                 ListNode tempList = p.next;
  72.                 // 将p.next(当前指向的首节点)与反转后的链表的头结点之后的节点连接起来
  73.                 // 第一次遍历的时候，此时反转的链表只有一个头结点，resultList.next = null,故：p.next = null
  74.                 p.next = resultList.next;
  75.                 // 将拼接起来的节点 拼接到反转后链表的头结点的后面
  76.                 // 第一次遍历，p = ListNode{0},故：resultList = {-1},resultList.next = ListNode{0},resultList.next.next = null
  77.                 resultList.next = p;
  78.                 // 第一次遍历后，p = tempList = {1}
  79.                 p = tempList;
  80.             }
  81.     // resultList.next 是去除掉头结点-1的值
  82.             return resultList.next;
  83.         }
  84. 3-2、就地反转方式
  85.         /**
  86.         在待反转链表基础上修改节点顺序得到反转链表。
  87.         难点在于理解循环中resultList.next指向性的变化，以及p和pNext两个变量的变化, p指向的链表首结点永远是1,只是节点1在resultList链表中位置在发生变化,而pNext是随着p移动的。
  88.         resultList = {HeroNode@634} "HeroNode{no=-1, name='', nickname=''}"
  89.             p = {HeroNode@631} "HeroNode{no=0, name='', nickname=''}"
  90.             pNext = {HeroNode@639} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  91.             pNext.next = {HeroNode@652} "HeroNode{no=2, name='卢俊义', nickname='玉麒麟'}"
  92.             p.next = {HeroNode@639} "HeroNode{no=1, name='宋江', nickname='及时雨'}"
  93.             resultList.next = {HeroNode@631} "HeroNode{no=0, name='', nickname=''}"
  94.         */
  95.         public static ListNode reverseListByLocal(ListNode listNode){
  96.         // 定义一个带头节点的,保存反转之后的链表信息
  97.         // resultList: -1 -> null
  98.             ListNode resultList = new ListNode(-1);
  99.         // 将保存反转后的链表的 头结点指向待反转的链表。
  100.         // resultList : -1 -> 0 -> 1 -> 2 -> 3 ->4
  101.             resultList.next= listNode;
  102.         // 循环节点，初始值为待反转的链表
  103.         // p: 0 -> 1 -> 2 -> 3 ->4
  104.             ListNode p = listNode;
  105.         // 定义一个链式链表，用来保存p.next的值，用于下一次循环
  106.         // pNext: 1 ->2 ->3 -> 4
  107.             ListNode pNext = p.next;
  108.             while (pNext!=null){
  109.                 // 第一次遍历，pNext.next = HeroNode{2}
  110.                 // p: 0 -> 2 -> 3 ->4 -> null
  111.                 p.next = pNext.next;
  112.                 // 第一次遍历，resultList.next = HeroNode{0}
  113.                 // pNext: 1 -> 0 -> 2 -> 3 ->4
  114.                 // resultList: -1 ->0 -> 2 -> 3 ->4 -> null ??? 理解->1 去哪里了
  115.                 pNext.next = resultList.next;
  116.                 // 让resultList头结点指向pNext
  117.                 // 第一次遍历，pNext = HeroNode{1}
  118.                 // resultList: 
  119.                 resultList.next = pNext;
  120.                 // 让pNext指向p的下一个节点
  121.                 pNext=p.next;
  122.             }
  123.             return resultList.next;
  124.         }

1.3、链表之双向链表分析

  1. 1、双向链表可以向前或者向后 单链表需依靠辅助节点进行删除
  2. 3、双向链表结构图：prev+Element+next
  3. 4、操作：
  4.     4-1、遍历：与单链表一样，只是可以向前，也可以向后查找
  5.     4-2、添加(链表尾部)：
  6.         先找到双向链表的尾部节点(设置为temp)
  7.         temp.next = newNode;
  8.         newNode.pre = temp;
  9.     4-3、删除：可自我删除
  10.         先找到双向链表的删除节点(设置为temp)
  11.         temp.pre.next = temp.next;
  12.         temp.next.pre = temp.per;