前言：

一 线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是由n个具有相同特性数据元素组成的有限序列。

1.1 相关概念

前驱元素：若A元素在B元素的前面，则称A为B的前驱元素
后继元素：若B元素在A元素的后面，则称B为A的后继元素
线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。
1. 第一个数据元素没有前驱，这个数据元素被称为头结点。
2. 最后一个数据元素没有后继，这个数据元素被称为尾结点。
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

如果把线性表用数学语言来定义，则表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素。
image.png
线性表的分类：
线性表中的数据物理存储方式可分为顺序存储、链式存储，即线性表分为顺序表和链表。

二 顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中逻辑结构的数据与物理结构的数据一致(相邻的两个元素逻辑和物理存储单元位置一致)。即通过数据元素物理存储相邻关系来反映数据元素逻辑上相邻关系。

2.1 代码实现

关键代码：

  1. add添加元素
  2. add重载添加元素
  3. remove 移除元素
  4. ensureCapacity 扩容以及缩容 ```java package com.ycc.data.structure.line;

import java.util.Iterator;

/**

  • 顺序表 *
  • @author liaozx
  • @description

  • @create 2020-11-23 22:12 / public class MyArrayList implements Iterable { /*

    • 用来保存此队列中内容的数组 / private Object[] elementData; /*
    • 保存当前为第几个元素的指标 / private int current; /*

    • 表示数组大小的容量指标 */ private int capacity;

      /**

    • 初始化线性表，并且声明保存内容的数组大小 *

    • @param initSize */ public MyArrayList(int initSize) { if (initSize < 0) {

      1.  throw new RuntimeException("initalSize必须大于0：" + initSize);

      } else {

      1.  //初始化数组
      2.  this.elementData = new Object[initSize];
      3.  this.current = 0;
      4.  this.capacity = initSize;

      } }

      /**

    • 如果初始化时，未声明大小，则默认为10 */ public MyArrayList() { this(10); }

      /**

    • 添加元素的方法 添加前，先确认是否已经满了 *
    • @param e

    • @return */ public void add(E e) { // 确认容量 ensureCapacity(); this.elementData[current++] = e; }

      /**

    • 在指定下标位置处插入数据e *
    • @param index 下标
    • @param e 需要插入的数据

    • @return */ public void add(int index, E e) { validateIndex(index); ensureCapacity(); //先把index索引处的元素及其后面的元素依次向后移动一位 for (int i = current; i > index; i—) {

      1.  elementData[i] = elementData[i - 1];

      } //再把t元素放到i索引处即可 elementData[index] = e; //元素个数+1 current++; }

      /**

    • 删除指定下标出的数据 *
    • @param index
    • @return */ public E remove(int index) { validateIndex(index); Object temp = elementData[index]; //把index的后面元素向前移动一个 for (int i = index; i < current - 1; i++) {
      1.  elementData[i] = elementData[i + 1];
      } current—; ensureCapacity(); return (E) temp; }
  1. /**
  2.  * 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量
  3.  */
  4. private void ensureCapacity() {
  5.     boolean isResize = false;
  6.     //扩容 默认扩展2倍
  7.     if (current == capacity) {
  8.         capacity = capacity * 2;
  9.         isResize = true;
  10.     }
  12.     //缩容 当数据量小于 容量的1/4 则需要缩容成1/2
  13.     if (current < capacity / 4) {
  14.         capacity = capacity / 2;
  15.         isResize = true;
  16.     }
  17.     if (isResize) {
  18.         Object[] newData = new Object[capacity];
  19.         for (int i = 0; i < current; i++) {
  20.             newData[i] = this.elementData[i];
  21.         }
  22.         this.elementData = newData;
  23.     }
  24. }
  26. /**
  27.  * 得到指定下标的数据
  28.  *
  29.  * @param index
  30.  * @return
  31.  */
  32. public E get(int index) {
  33.     validateIndex(index);
  34.     return (E) this.elementData[index];
  35. }
  37. /**
  38.  * 返回当前队列大小
  39.  *
  40.  * @return
  41.  */
  42. public int size() {
  43.     return this.current;
  44. }
  47. /**
  48.  * 验证当前下标是否合法，如果不合法，抛出运行时异常
  49.  *
  50.  * @param index 下标
  51.  */
  52. private void validateIndex(int index) {
  53.     if (index < 0 || index > current) {
  54.         throw new RuntimeException("数组Index错误：" + index + "范围是：0-" + current);
  55.     }
  56. }
  59. @Override
  60. public Iterator iterator() {
  61.     return new MyArrayListIterator();
  62. }
  64. //实现迭代器
  65. private class MyArrayListIterator implements Iterator {
  67.     private int curr;
  69.     public MyArrayListIterator() {
  70.         curr = 0;
  71.     }
  73.     @Override
  74.     public boolean hasNext() {
  75.         return curr < current;
  76.     }
  78.     @Override
  79.     public Object next() {
  80.         return elementData[curr++];
  81.     }
  82. }

}

  1. 测试代码
  2. ```java
  3. package com.ycc.data.structure.test;
  5. import com.alibaba.fastjson.JSONObject;
  6. import com.ycc.data.structure.line.MyArrayList;
  8. /**
  9.  * @author liaozx
  10.  * @date 2020-11-23
  11.  */
  12. public class MyArrayListTest {
  14.     public static void main(String[] args) {
  15.         MyArrayList<String> myArrayList = new MyArrayList<>(3);
  16.         myArrayList.add("张三");
  17.         myArrayList.add("李四");
  18.         myArrayList.add("王五");
  19.         myArrayList.add(3, "赵六");
  20.         System.out.println(JSONObject.toJSONString(myArrayList));
  21.         for (String str : myArrayList) {
  22.             System.out.println(str);
  23.         }
  24.     }
  25. }

2.2 时间复杂度分析

  1. 查询某个元素: get(i): 只需要一次eles[i]就可以获取到对应的元素，所以时间复杂度为O(1);
  2. add(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n);
  3. remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为O(n);

PS: 扩容导致性能下降
顺序表的底层由数组实现，且数组长度是固定的，所以在操作过程中涉及到容器扩容操作。这样会导致顺序表在使用过程中时间复杂度不是线性的，因为它在某些时刻需要扩容，这时耗时会突增，尤其是元素越多，问题越明显。

三 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能表示元素的逻辑顺序。数据元素的逻辑顺序是通过链表中指针连接实现，即每个结点都有一个指针(next)指向下一个节点。

3.1 单链表代码实现

单向链表是链表中的一种，它由多个结点组成，且每个结点都由一个数据域和一个指针域组成，数据域存储数据，指针域指向其后继结点。链表头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
image.png
关键代码：

  1. add 新增元素
  2. add 重载新元素
  3. remove移除元素 ```java package com.ycc.data.structure.line;

import java.util.Iterator;

/**

  • 单向链表 *
  • @author liaozx
  • @description

  • @create 2020-11-23 23:12 / public class MyLinedList implements Iterable { /*

    • 头结点 */ private final Node head;

      /**

    • 表示数组大小的指标 */ private int current;

      public MyLinedList() { //初始化头结点 this.head = new Node(null, null); //初始化元素个数 this.current = 0; }

      /**

    • 在链表的末尾插入节点 *

    • @param e */ public void add(E e) { //找到当前最后一个结点 Node node = head; while (node.next != null) {

      1.  node = node.next;

      } // 根据需要添加的内容，封装为结点 Node newNode = new Node<>(e, null); node.next = newNode; // 当前大小自增加1 current++; }

      /**

    • 指定index位置，新增一个对象 *
    • @param index

    • @param e */ public void add(int index, E e) { //获取index节点 Node currentNode = getNode(index); //创建新结点，并且newNode.next=indexNode.next;即断开链表 Node newNode = new Node(e, currentNode.next); //然后插入链表节点 currentNode.next = newNode; //元素的个数+1 current++; }

      /**

    • 移除一个元素 *
    • @param index

    • @return */ public E remove(int index) { //找到index位置的前一个节点 Node preNode = getNode(index); //找到index结点 Node currentNode = preNode.next; //找到index位置的下一个节点 Node nextNode = currentNode.next; //前一个结点指向下一个结点 preNode.next = nextNode; //元素个数-1 current—; return (E) currentNode.item; }

      /**

    • 遍历当前链表，取得当前索引对应的元素 *

    • @return */ private Node getNode(int index) { // 先判断索引正确性 if (index > current || index < 0) {

      1.  throw new RuntimeException("索引值有错：" + index + ",其范围是0-" + current);

      } Node currentNode = head; int count = 0; while (count != index) {

      1.  currentNode = currentNode.next;
      2.  count++;

      } return currentNode; }

      /**

    • 根据索引，取得该索引下的数据 *
    • @param index

    • @return */ public E get(int index) { // 先判断索引正确性 if (index >= current || index < 0) {

      1.  throw new RuntimeException("索引值有错：" + index);

      } //因为头节点，不存数据，即head.next 为第一个节点 Node tem = head.next; int count = 0; while (count != index) {

      1.  tem = tem.next;
      2.  count++;

      } return tem.item; }

      public int size() { return current; }

      @Override public Iterator iterator() { return new MyLinedListIterator(); }

/**

  1.  * 用来存放数据的结点型内部类
  2.  */
  3. private class Node<E> {
  4.     private final E item;// 结点中存放的数据
  5.     private Node<E> next;// 用来指向该结点的下一个结点
  7.     public Node(E item, Node next) {
  8.         this.item = item;
  9.         this.next = next;
  10.     }
  12. }
  14. private class MyLinedListIterator implements Iterator {
  16.     private Node node;
  18.     public MyLinedListIterator() {
  19.         this.node = head;
  20.     }
  22.     @Override
  23.     public boolean hasNext() {
  24.         return node.next != null;
  25.     }
  27.     @Override
  28.     public Object next() {
  29.         node = node.next;
  30.         return node.item;
  31.     }
  32. }

}

  1.  测试代码
  2. ```java
  3. package com.ycc.data.structure.test;
  5. import com.alibaba.fastjson.JSONObject;
  6. import com.ycc.data.structure.line.MyLinedList;
  8. /**
  9.  * @author liaozx
  10.  * @date 2020/11/23
  11.  */
  12. public class MyLinedListTest {
  13.     public static void main(String[] args) {
  14.         //创建顺序表对象
  15.         MyLinedList<String> sl = new MyLinedList<>();
  16.         //测试插入
  17.         sl.add("烟雨楼0");
  18.         sl.add("烟雨楼1");
  19.         sl.add("烟雨楼2");
  20.         sl.add(2, "烟雨楼3");
  21.         System.out.println(JSONObject.toJSONString(sl));
  22.         System.out.println(JSONObject.toJSONString(sl.get(0)));
  23.         for (String str: sl) {
  24.             System.out.println(str);
  25.         }
  26.     }
  27. }

3.2 双向链表代码实现

双向链表也叫双向表，是链表中的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域存储数据，其中一个指针域指向其后继结点，另一个指针域指向前驱结点。链表头结点的数据域不存数据，指向前驱结点的指针值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
image.png

  1. package com.ycc.data.structure.line;
  3. import java.util.Iterator;
  5. /**
  6.  * 双向链表
  7.  *
  8.  * @author liaozx
  9.  * @date 2020/11/23
  10.  */
  11. public class MyBothWayLinedList<E> implements Iterable<E> {
  13.     /**
  14.      * 头结点
  15.      */
  16.     private final Node<E> head;
  17.     /**
  18.      * 最后一个结点
  19.      */
  20.     private Node<E> last;
  22.     /**
  23.      * 表示数组大小的指标
  24.      */
  25.     private int current;
  27.     public MyBothWayLinedList() {
  28.         //初始化头结点
  29.         this.head = new Node(null, null, null);
  30.         this.last = null;
  31.         //初始化元素个数
  32.         this.current = 0;
  33.     }
  35.     /**
  36.      * 在链表的末尾插入节点
  37.      *
  38.      * @param e
  39.      */
  40.     public void add(E e) {
  42.         //如果链表为空：
  43.         if (current == 0) {
  44.             //创建新的结点,即，上一个节点为头节点，下一个为null
  45.             Node newNode = new Node(e, head, null);
  46.             //让新结点称为尾结点
  47.             last = newNode;
  48.             //让头结点指向尾结点
  49.             head.next = last;
  50.         } else {
  51.             Node oldLast = last;
  52.             //创建新的结点,即,上一个节点为last，下一个节点为null
  53.             Node newNode = new Node(e, oldLast, null);
  54.             //链接上last的节点
  55.             last.next = newNode;
  56.             //新节点变成为尾部节点
  57.             last = newNode;
  58.         }
  59.         current++;
  60.     }
  62.     /**
  63.      * 指定index位置，新增一个对象
  64.      *
  65.      * @param index
  66.      * @param e
  67.      */
  68.     public void add(int index, E e) {
  69.         //获取index节点
  70.         Node currentNode = getNode(index);
  71.         //创建新结点，并且newNode.next=indexNode.next; 即断开链表
  72.         Node newNode = new Node(e, currentNode, currentNode.next);
  73.         //然后插入链表节点
  74.         currentNode.next = newNode;
  75.         //元素的个数+1
  76.         if (index == current) {
  77.             last = newNode;
  78.         }
  79.         current++;
  80.     }
  82.     /**
  83.      * 移除一个元素
  84.      *
  85.      * @param index
  86.      * @return
  87.      */
  88.     public E remove(int index) {
  89.         //找到index结点，它是待删除的
  90.         Node prNode = getNode(index);
  91.         Node currentNode = prNode.next;
  92.         //找到index位置的下一个节点
  93.         Node nextNode = currentNode.next;
  94.         //删除index节点，即：前一个结点指向下一个结点
  95.         currentNode.pre.next = nextNode;
  96.         //元素个数-1
  97.         current--;
  98.         //如果删除的是末尾节点则，处理last节点指向
  99.         if (index == current) {
  100.             last = nextNode == null ? currentNode.pre : nextNode;
  101.         }
  102.         return (E) currentNode.item;
  103.     }
  105.     /**
  106.      * 遍历当前链表，取得当前索引对应的元素
  107.      *
  108.      * @return
  109.      */
  110.     private Node<E> getNode(int index) {
  111.         // 先判断索引正确性
  112.         if (index > current || index < 0) {
  113.             throw new RuntimeException("索引值有错：" + index + ",其范围是0-" + current);
  114.         }
  115.         Node<E> currentNode = head;
  116.         int count = 0;
  117.         while (count < index) {
  118.             currentNode = currentNode.next;
  119.             count++;
  120.         }
  121.         return currentNode;
  122.     }
  124.     /**
  125.      * 根据索引，取得该索引下的数据
  126.      *
  127.      * @param index
  128.      * @return
  129.      */
  130.     public E get(int index) {
  131.         // 先判断索引正确性
  132.         if (index >= current || index < 0) {
  133.             throw new RuntimeException("索引值有错：" + index);
  134.         }
  135.         //因为头节点，不存数据，即head.next 为第一个节点
  136.         Node<E> tem = head.next;
  137.         int count = 0;
  138.         while (count != index) {
  139.             tem = tem.next;
  140.             count++;
  141.         }
  142.         return tem.item;
  143.     }
  145.     public int size() {
  146.         return current;
  147.     }
  149.     @Override
  150.     public Iterator iterator() {
  151.         return new MyBothWayLinedListIterator();
  152.     }
  154.     /**
  155.      * 用来存放数据的结点型内部类
  156.      */
  157.     private class Node<E> {
  158.         private final E item;// 结点中存放的数据
  159.         private final Node<E> pre;//上一个节点
  160.         private Node<E> next;// 用来指向该结点的下一个结点
  162.         public Node(E item, Node pre, Node next) {
  163.             this.item = item;
  164.             this.pre = pre;
  165.             this.next = next;
  166.         }
  168.     }
  170.     private class MyBothWayLinedListIterator implements Iterator {
  172.         private Node node;
  174.         public MyBothWayLinedListIterator() {
  175.             this.node = head;
  176.         }
  178.         @Override
  179.         public boolean hasNext() {
  180.             return node.next != null;
  181.         }
  183.         @Override
  184.         public Object next() {
  185.             node = node.next;
  186.             return node.item;
  187.         }
  188.     }
  190. }

测试代码

  1. package com.ycc.data.structure.test;
  3. import com.alibaba.fastjson.JSONObject;
  4. import com.ycc.data.structure.line.MyBothWayLinedList;
  6. /**
  7.  * @author liaozx
  8.  * @date 2020/11/23
  9.  */
  10. public class MyBothWayLinedListTest {
  11.     public static void main(String[] args) {
  12.         //创建顺序表对象
  13.         MyBothWayLinedList<String> sl = new MyBothWayLinedList<>();
  14.         //测试插入
  15.         sl.add("烟雨楼0");
  16.         sl.add("烟雨楼1");
  17.         sl.add("烟雨楼2");
  18.         sl.add(3, "烟雨楼3");
  19.         sl.remove(3);
  20.         System.out.println(JSONObject.toJSONString(sl));
  21.         System.out.println(JSONObject.toJSONString(sl.get(0)));
  22.         for (String str : sl) {
  23.             System.out.println(str);
  24.         }
  25.     }
  26. }

3.3 时间复杂度分析

  1. get(int i):每次查询要从链表头部开始依次向后查找，数据元素越多，比较就越多，时间复杂度为 O(n)
  2. add(int i,T t):每次插入要先找到i位置的前一个元素，然后完成插入操作，数据元素越多，查找的元素越多，时间复杂度为O(n)
  3. remove(int i):每次移除要先找到i位置的前一个元素，然后完成插入操作，数据元素越多，查找的元素越多，时间复杂度为O(n)

PS：

  1. 增删改快：链表和顺序表虽然操作(插入和删除)复杂度虽然一样，但有很大优势，因为链表物理地址是不连续的，且它不需要预先指定存储空间大小(即不需要扩容+移动拷贝元素)。

  2. 查询慢：所以，查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

    四 链表相关问题

    4.1 链表反转

    递归反转其实就是从原链表第一个存数据结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕。

    1. //用来反转整个链表
    2.  public void reverse() {
    3.      //判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
    4.      if (current == 0) {
    5.          return;
    6.      }
    7.      reverse(head.next);
    8.  }
    10.  //反转指定的结点curr，并把反转后的结点返回
    11.  public Node reverse(Node curr) {
    12.      if (curr.next == null) {
    13.          head.next = curr;
    14.          return curr;
    15.      }
    16.      //递归的反转当前结点curr的下一个结点；返回值就是链表反转后，当前结点的上一个结点
    17.      Node pre = reverse(curr.next);
    18.      //让返回的结点的下一个结点变为当前结点curr；
    19.      pre.next = curr;
    20.      //把当前结点的下一个结点变为null
    21.      curr.next = null;
    22.      return curr;
    23.  }

    4.2 快慢指针

    指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值。一般情况下，快指针的移动步长为慢指针的两倍。

    4.2.1 中间值问题

    利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。

    1. public class FastSlowTest {
    3.  public static void main(String[] args) throws Exception {
    4.      //创建结点
    5.      Node<String> node1 = new Node<>("aa", null);
    6.      Node<String> node2 = new Node<>("bb", null);
    7.      Node<String> node3 = new Node<>("cc", null);
    8.      Node<String> node4 = new Node<>("dd", null);
    9.      Node<String> node5 = new Node<>("ee", null);
    10.      Node<String> node6 = new Node<>("ff", null);
    11.      Node<String> node7 = new Node<>("gg", null);
    13.      //完成结点之间的指向
    14.      node1.next = node2;
    15.      node2.next = node3;
    16.      node3.next = node4;
    17.      node4.next = node5;
    18.      node5.next = node6;
    19.      node6.next = node7;
    21.      //查找中间值
    22.      String mid = getMid(node1);
    23.      System.out.println("中间值为：" + mid);
    24.  }
    26.  /**
    27.   * @param first 链表的首结点
    28.   * @return 链表的中间结点的值
    29.   */
    30.  public static String getMid(Node<String> first) {
    31.      //定义两个指针
    32.      Node<String> fast = first;
    33.      Node<String> slow = first;
    34.      //使用两个指针遍历链表，当快指针指向的结点没有下一个结点了，就可以结束了，结束之后，慢指针指向的结点就是中间值
    35.      while (fast != null && fast.next != null) {
    36.          //变化fast的值和slow的值
    37.          fast = fast.next.next;
    38.          slow = slow.next;
    39.      }
    40.      return slow.item;
    41.  }
    43.  //结点类
    44.  private static class Node<T> {
    45.      //存储数据
    46.      T item;
    47.      //下一个结点
    48.      Node next;
    50.      public Node(T item, Node next) {
    51.          this.item = item;
    52.          this.next = next;
    53.      }
    54.  }
    55. }

    4.2.2 单向链表是否有环

    使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。 ```java package com.ycc.data.structure.test;

public class CircleListCheckTest { public static void main(String[] args) throws Exception {

  1.     //创建结点
  2.     Node<String> node1 = new Node<>("aa", null);
  3.     Node<String> node2 = new Node<>("bb", null);
  4.     Node<String> node3 = new Node<>("cc", null);
  5.     Node<String> node4 = new Node<>("dd", null);
  6.     Node<String> node5 = new Node<>("ee", null);
  7.     Node<String> node6 = new Node<>("ff", null);
  8.     Node<String> node7 = new Node<>("gg", null);
  10.     //完成结点之间的指向
  11.     node1.next = node2;
  12.     node2.next = node3;
  13.     node3.next = node4;
  14.     node4.next = node5;
  15.     node5.next = node6;
  16.     node6.next = node7;
  18.     //产生环
  19.     node7.next = node3;
  20.     //判断链表是否有环
  21.     boolean circle = isCircle(node1);
  22.     System.out.println("first链表中是否有环：" + circle);
  23. }
  25. /**
  26.  * 判断链表中是否有环
  27.  *
  28.  * @param first 链表首结点
  29.  * @return ture为有环，false为无环
  30.  */
  31. public static boolean isCircle(Node<String> first) {
  32.     //定义快慢指针
  33.     Node<String> fast = first;
  34.     Node<String> slow = first;
  36.     //遍历链表，如果快慢指针指向了同一个结点，那么证明有环
  37.     while (fast != null && fast.next != null) {
  38.         //变换fast和slow
  39.         fast = fast.next.next;
  40.         slow = slow.next;
  42.         if (fast.equals(slow)) {
  43.             return true;
  44.         }
  45.     }
  47.     return false;
  48. }
  50. //结点类
  51. private static class Node<T> {
  52.     //存储数据
  53.     T item;
  54.     //下一个结点
  55.     Node next;
  57.     public Node(T item, Node next) {
  58.         this.item = item;
  59.         this.next = next;
  60.     }
  61. }

}

  1. <a name="pikGj"></a>
  2. ### 4.2.3 有环链表入口问题
  3. 当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入
  4. ```java
  5. package com.ycc.data.structure.test;
  7. /**
  8.  * @author liaozx
  9.  * @date 2020/11/23
  10.  */
  11. public class CircleListInTest {
  14.     public static void main(String[] args) throws Exception {
  15.         //创建结点
  16.         Node<String> node1 = new Node<>("aa", null);
  17.         Node<String> node2 = new Node<>("bb", null);
  18.         Node<String> node3 = new Node<>("cc", null);
  19.         Node<String> node4 = new Node<>("dd", null);
  20.         Node<String> node5 = new Node<>("ee", null);
  21.         Node<String> node6 = new Node<>("ff", null);
  22.         Node<String> node7 = new Node<>("gg", null);
  24.         //完成结点之间的指向
  25.         node1.next = node2;
  26.         node2.next = node3;
  27.         node3.next = node4;
  28.         node4.next = node5;
  29.         node5.next = node6;
  30.         node6.next = node7;
  32.         //产生环
  33.         node7.next = node3;
  35.         //查找环的入口结点
  36.         Node<String> entrance = getEntrance(node1);
  37.         System.out.println("first链表中环的入口结点元素为：" + entrance.item);
  38.     }
  40.     /**
  41.      * 查找有环链表中环的入口结点
  42.      *
  43.      * @param first 链表首结点
  44.      * @return 环的入口结点
  45.      */
  46.     public static Node getEntrance(Node<String> first) {
  47.         //定义快慢指针
  48.         Node<String> fast = first;
  49.         Node<String> slow = first;
  50.         Node<String> temp = null;
  52.         //遍历链表，先找到环(快慢指针相遇),准备一个临时指针，指向链表的首结点，继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的结点就是环的入口
  53.         while (fast != null && fast.next != null) {
  54.             //变换快慢指针
  55.             fast = fast.next.next;
  56.             slow = slow.next;
  58.             //判断快慢指针是否相遇
  59.             if (fast.equals(slow)) {
  60.                 temp = first;
  61.                 continue;
  62.             }
  63.             //让临时结点变换
  64.             if (temp != null) {
  65.                 temp = temp.next;
  66.                 //判断临时指针是否和慢指针相遇
  67.                 if (temp.equals(slow)) {
  68.                     break;
  69.                 }
  70.             }
  71.         }
  73.         return temp;
  74.     }
  76.     //结点类
  77.     private static class Node<T> {
  78.         //存储数据
  79.         T item;
  80.         //下一个结点
  81.         Node next;
  83.         public Node(T item, Node next) {
  84.             this.item = item;
  85.             this.next = next;
  86.         }
  87.     }
  88. }

4.3 循环链表

循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。
image.png

4.4 约瑟夫问题

  1. public class JosephTest {
  2.     public static void main(String[] args) {
  3.         //解决约瑟夫问题
  5.         //1.构建循环链表，包含41个结点，分别存储1~41之间的值
  6.         //用来就首结点
  7.         Node<Integer> first = null;
  8.         //用来记录前一个结点
  9.         Node<Integer> pre = null;
  11.         for (int i = 1; i <= 41; i++) {
  13.             //如果是第一个结点
  14.             if (i == 1) {
  15.                 first = new Node<>(i, null);
  16.                 pre = first;
  17.                 continue;
  18.             }
  20.             //如果不是第一个结点
  21.             Node<Integer> newNode = new Node<>(i, null);
  22.             pre.next = newNode;
  23.             pre = newNode;
  24.             //如果是最后一个结点，那么需要让最后一个结点的下一个结点变为first,变为循环链表了
  25.             if (i == 41) {
  26.                 pre.next = first;
  27.             }
  29.         }
  31.         //2.需要count计数器，模拟报数
  32.         int count = 0;
  33.         //3.遍历循环链表
  34.         //记录每次遍历拿到的结点，默认从首结点开始
  35.         Node<Integer> n = first;
  36.         //记录当前结点的上一个结点
  37.         Node<Integer> before = null;
  38.         while (n != n.next) {
  39.             //模拟报数
  40.             count++;
  41.             //判断当前报数是不是为3
  42.             if (count == 3) {
  43.                 //如果是3，则把当前结点删除调用，打印当前结点，重置count=0，让当前结点n后移
  44.                 before.next = n.next;
  45.                 System.out.print(n.item + ",");
  46.                 count = 0;
  47.                 n = n.next;
  48.             } else {
  49.                 //如果不是3，让before变为当前结点，让当前结点后移；
  50.                 before = n;
  51.                 n = n.next;
  52.             }
  53.         }
  55.         //打印最后一个元素
  56.         System.out.println(n.item);
  57.     }
  60.     //结点类
  61.     private static class Node<T> {
  62.         //存储数据
  63.         T item;
  64.         //下一个结点
  65.         Node next;
  67.         public Node(T item, Node next) {
  68.             this.item = item;
  69.             this.next = next;
  70.         }
  71.     }
  72. }

五 栈

栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。
image.png

5.1 代码实现

顺序结构的栈

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * @author liaozx
  5.  * @description
  6.  * @create 2020-11-24 10:45
  7.  */
  8. public class MyArrayStack<E> {
  9.     /**
  10.      * 用来保存数据线性表
  11.      */
  12.     private final MyArrayList<E> list = new MyArrayList<E>();
  13.     /**
  14.      * 表示当前栈元素个数
  15.      */
  16.     private int size;
  18.     /**
  19.      * 入栈操作
  20.      *
  21.      * @param e
  22.      */
  23.     public void push(E e) {
  24.         list.add(e);
  25.         size++;
  26.     }
  28.     /**
  29.      * 出栈操作
  30.      *
  31.      * @return
  32.      */
  33.     public E pop() {
  34.         E e = list.get(size - 1);
  35.         list.remove(size - 1);
  36.         size--;
  37.         return e;
  38.     }
  41.     public boolean isEmpty() {
  42.         return size == 0;
  43.     }
  44. }

链表结构的栈

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * @author liaozx
  5.  * @description
  6.  * @create 2020-11-24 10:45
  7.  */
  8. public class MyLinedStack<E> {
  9.     /**
  10.      * 用来保存数据线性表
  11.      */
  13.     private final MyLinedList<E> list = new MyLinedList<E>();
  15.     /**
  16.      * 表示当前栈元素个数
  17.      */
  18.     private int size;
  20.     /**
  21.      * 入栈操作
  22.      *
  23.      * @param e
  24.      */
  25.     public void push(E e) {
  26.         list.add(e);
  27.         size++;
  28.     }
  30.     /**
  31.      * 出栈操作
  32.      *
  33.      * @return
  34.      */
  35.     public E pop() {
  36.         E e = list.get(size - 1);
  37.         list.remove(size - 1);
  38.         size--;
  39.         return e;
  40.     }
  42.     public boolean isEmpty() {
  43.         return size == 0;
  44.     }
  45. }

5.2 测试代码

  1. package com.ycc.data.structure.test;
  3. import com.alibaba.fastjson.JSONObject;
  4. import com.ycc.data.structure.line.MyArrayStack;
  5. import com.ycc.data.structure.line.MyLinedStack;
  7. /**
  8.  * @author liaozx
  9.  * @date 2020/9/14
  10.  */
  11. public class MyStackTest {
  13.     public static void main(String[] args) {
  14.         //创建栈对象
  15.         MyArrayStack<String> stack = new MyArrayStack<>();
  16.         //测试压栈
  17.         stack.push("a");
  18.         stack.push("b");
  19.         stack.push("c");
  20.         stack.push("d");
  21.         System.out.println("---stack---" + JSONObject.toJSONString(stack));
  22.         //测试弹栈
  23.         String result = stack.pop();
  24.         System.out.println("弹出的元素是：" + result);
  26.         //创建栈对象
  27.         MyLinedStack<String> myLinedStack = new MyLinedStack<>();
  28.         //测试压栈
  29.         myLinedStack.push("a");
  30.         myLinedStack.push("b");
  31.         myLinedStack.push("c");
  32.         myLinedStack.push("d");
  33.         System.out.println("---stack---" + JSONObject.toJSONString(myLinedStack));
  34.         //测试弹栈
  35.         String string = myLinedStack.pop();
  36.         System.out.println("弹出的元素是：" + string);
  38.     }
  39. }

5.3 栈应用-匹配括弧

  1. 创建一个栈用来存储左括号
  2. 从左往右遍历字符串，拿到每一个字符
  3. 判断该字符是不是左括号，如果是，放入栈中存储
  4. 判断该字符是不是右括号，如果不是，继续下一次循环
  5. 如果该字符是右括号，则从栈中弹出一个元素t；
  6. 判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号
  7. 循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配 ```java package com.ycc.data.structure.test;

import com.ycc.data.structure.line.MyLinedStack;

/**

  • @author liaozx

  • @date 2020-11-24 */ public class MyBracketsMatchTest { public static void main(String[] args) {

    1.  String str = "(上海(长安)())";
    2.  boolean match = isMatch(str);
    3.  System.out.println(str + "中的括号是否匹配：" + match);

    }

    /**

    • 判断str中的括号是否匹配 *
    • @param str 括号组成的字符串

    • @return 如果匹配，返回true，如果不匹配，返回false */ public static boolean isMatch(String str) { //1.创建栈对象，用来存储左括号 //MyArrayStack chars = new MyArrayStack<>(); MyLinedStack chars = new MyLinedStack<>(); //2.从左往右遍历字符串 for (int i = 0; i < str.length(); i++) {

      1.  String currChar = str.charAt(i) + "";
      3.  //3.判断当前字符是否为左括号，如果是，则把字符放入到栈中
      4.  if (currChar.equals("(")) {
      5.      chars.push(currChar);
      6.  } else if (currChar.equals(")")) {
      7.      //4.继续判断当前字符是否是有括号，如果是，则从栈中弹出一个左括号，并判断弹出的结果是否为null,如果为null证明没有匹配的左括号，如果不为null，则证明有匹配的左括号
      8.      if (chars.isEmpty()) {
      9.          return false;
      10.      } else {
      11.          String pop = chars.pop();
      12.      }
      13.  }

      } //5.判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配 return chars.isEmpty(); } }

  1. <a name="JKQAv"></a>
  2. ## 5.4  波兰表达式求值
  3. 1.创建一个栈对象oprands存储操作数<br />2.从左往右遍历逆波兰表达式，得到每一个字符串<br />3.判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中<br />4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2<br />5.使用该运算符计算o1和o2，得到结果result<br />6.把该结果压入oprands栈中<br />7.遍历结束后，拿出栈中最终的结果返回
  4. ```java
  5. package com.ycc.data.structure.test;
  7. import com.ycc.data.structure.line.MyLinedStack;
  9. /**
  10.  * @author liaozx
  11.  * @date 2020-11-24
  12.  */
  13. public class ReversePolishNotationTest {
  14.     public static void main(String[] args) {
  15.         //中缀表达式 3*（17-15）+18/6 的逆波兰表达式如下 6+3=9
  16.         String[] expression = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
  17.         int result = calculate(expression);
  18.         System.out.println("逆波兰表达式的结果为：" + result);
  19.     }
  21.     /**
  22.      * @param expression 逆波兰表达式的数组表示方式
  23.      * @return 逆波兰表达式的计算结果
  24.      */
  25.     public static int calculate(String[] expression) {
  26.         //1.定义一个栈，用来存储操作数
  27.         MyLinedStack<Integer> oprands = new MyLinedStack<>();
  28.         //2.从左往右遍历逆波兰表达式，得到每一个元素
  29.         for (int i = 0; i < expression.length; i++) {
  30.             String curr = expression[i];
  31.             //3.判断当前元素是运算符还是操作数
  32.             Integer o1;
  33.             Integer o2;
  34.             Integer result;
  35.             switch (curr) {
  36.                 case "+":
  37.                     //4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
  38.                     o1 = oprands.pop();
  39.                     o2 = oprands.pop();
  40.                     result = o2 + o1;
  41.                     oprands.push(result);
  42.                     break;
  43.                 case "-":
  44.                     //4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
  45.                     o1 = oprands.pop();
  46.                     o2 = oprands.pop();
  47.                     result = o2 - o1;
  48.                     oprands.push(result);
  49.                     break;
  50.                 case "*":
  51.                     //4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
  52.                     o1 = oprands.pop();
  53.                     o2 = oprands.pop();
  54.                     result = o2 * o1;
  55.                     oprands.push(result);
  56.                     break;
  57.                 case "/":
  58.                     //4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
  59.                     o1 = oprands.pop();
  60.                     o2 = oprands.pop();
  61.                     result = o2 / o1;
  62.                     oprands.push(result);
  64.                     break;
  65.                 default:
  66.                     //5.操作数，把该操作数放入到栈中；
  67.                     oprands.push(Integer.parseInt(curr));
  68.                     break;
  69.             }
  71.         }
  72.         //6.得到栈中最后一个元素，就是逆波兰表达式的结果
  73.         int result = oprands.pop();
  75.         return result;
  76.     }
  77. }

5.5 波兰表达式(补充)

前缀表达式(即波兰表达式)

概念

前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。

举例说明

  • (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

前缀表达式的计算机求值

  • 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

前缀表达式求值步骤示例

(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

1)、步骤图解如下
数据结构-通识篇之线性表 - 图6
2)、步骤描述如下

  • 从右至左扫描，将6、5、4、3压入堆栈
  • 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
  • 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
  • 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

中缀表达式

概念

  • 中缀表达式是一个通用的算术或逻辑公式表示方法。

举例说明

  • 中缀表达式就是常见的运算表达式，如(3+4)×5-6

中缀表达式的计算机求值

  • 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

后缀表达式（即逆波兰表达式）

概念

  • 后缀表达式一般指逆波兰式 ，逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

举例说明

  • (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

数据结构-通识篇之线性表 - 图7

后缀表达式的计算机求值

  • 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

后缀表达式求值步骤示例

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -

1)、步骤图解如下
数据结构-通识篇之线性表 - 图8数据结构-通识篇之线性表 - 图9
2)、步骤描述如下

  • 从左至右扫描，将3和4压入堆栈；
  • 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
  • 将5入栈；
  • 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
  • 将6入栈；
  • 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

六 队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。
image.png

6.1 代码实现

顺序结构的队列

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * @author liaozx
  5.  * @description
  6.  * @create 2020-11-24
  7.  */
  8. public class MyArrayQueue<E> {
  9.     /**
  10.      * 用来保存数据的队列
  11.      */
  12.     private final MyArrayList<E> list = new MyArrayList<E>();
  13.     /**
  14.      * 表示当前栈元素个数
  15.      */
  16.     private int size;
  18.     /**
  19.      * 入队
  20.      *
  21.      * @param e
  22.      */
  23.     public void enQueue(E e) {
  24.         list.add(e);
  25.         size++;
  26.     }
  28.     /**
  29.      * 出队
  30.      *
  31.      * @return
  32.      */
  33.     public E deQueue() {
  34.         if (size > 0) {
  35.             E e = list.get(0);
  36.             list.remove(0);
  37.             return e;
  38.         } else {
  39.             throw new RuntimeException("已经到达队列顶部");
  40.         }
  41.     }
  42. }

链表结构的队列

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * @author liaozx
  5.  * @description
  6.  * @create 2020-11-24 10:57
  7.  */
  8. public class MyLinedQueue<E> {
  9.     private final MyLinedList<E> list = new MyLinedList<E>();// 用来保存数据的队列
  10.     private int size;// 表示当前栈元素个数
  12.     /**
  13.      * 入队
  14.      *
  15.      * @param e
  16.      */
  17.     public void enQueue(E e) {
  18.         list.add(e);
  19.         size++;
  20.     }
  22.     /**
  23.      * 出队
  24.      *
  25.      * @return
  26.      */
  27.     public E deQueue() {
  28.         if (size > 0) {
  29.             E e = list.get(0);
  30.             list.remove(0);
  31.             return e;
  32.         } else {
  33.             throw new RuntimeException("已经到达队列顶部");
  34.         }
  35.     }
  36. }

6.2 测试代码

  1. package com.ycc.data.structure.test;
  3. import com.ycc.data.structure.line.MyArrayQueue;
  4. import com.ycc.data.structure.line.MyLinedQueue;
  6. /**
  7.  * @author liaozx
  8.  * @date 2020/11/24
  9.  */
  10. public class MyQueueTest {
  11.     public static void main(String[] args) {
  12.         //创建队列对象
  13.         MyArrayQueue<String> myArrayQueue = new MyArrayQueue<>();
  15.         //测试队列的enqueue方法
  16.         myArrayQueue.enQueue("a");
  17.         myArrayQueue.enQueue("b");
  18.         myArrayQueue.enQueue("c");
  19.         myArrayQueue.enQueue("d");
  21.         System.out.println("-------------------------------");
  22.         //测试队列的dequeue方法
  23.         String result = myArrayQueue.deQueue();
  24.         System.out.println("出队列的元素是：" + result);
  27.         //创建队列对象
  28.         MyLinedQueue<String> myLinedQueue = new MyLinedQueue<>();
  30.         //测试队列的enqueue方法
  31.         myLinedQueue.enQueue("a");
  32.         myLinedQueue.enQueue("b");
  33.         myLinedQueue.enQueue("c");
  34.         myLinedQueue.enQueue("d");
  36.         System.out.println("-------------------------------");
  37.         //测试队列的dequeue方法
  38.         String string = myLinedQueue.deQueue();
  39.         System.out.println("出队列的元素是：" + string);
  41.     }
  42. }

七 符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。
image.png

7.1 无序符号表

7.1.1 代码实现

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * 链表结构的符号表
  5.  * 无序
  6.  *
  7.  * @author liaozx
  8.  * @date 2020/11/24
  9.  */
  10. public class MySymbolTable<Key, Value> {
  11.     //记录首结点
  12.     private Node head;
  13.     //记录符号表中元素的个数
  14.     private int current;
  16.     private class Node {
  17.         //键
  18.         public Key key;
  19.         //值
  20.         public Value value;
  21.         //下一个结点
  22.         public Node next;
  24.         public Node(Key key, Value value, Node next) {
  25.             this.key = key;
  26.             this.value = value;
  27.             this.next = next;
  28.         }
  29.     }
  31.     public MySymbolTable() {
  32.         this.head = new Node(null, null, null);
  33.         this.current = 0;
  34.     }
  36.     //获取符号表中键值对的个数
  37.     public int size() {
  38.         return current;
  39.     }
  41.     //往符号表中插入键值对
  42.     public void put(Key key, Value value) {
  43.         //符号表中已经存在了键为key的键值对，那么只需要找到该结点，替换值为value即可
  44.         Node node = head;
  45.         while (node.next != null) {
  46.             //变换node
  47.             node = node.next;
  48.             //判断n结点存储的键是否为key，如果是，则替换变换node结点的值
  49.             if (node.key.equals(key)) {
  50.                 node.value = value;
  51.                 return;
  52.             }
  53.         }
  55.         //如果符号表中不存在键为key的键值对，只需要创建新的结点，保存要插入的键值对，把新结点插入到链表的头部  head.next=新结点即可
  56.         Node newNode = new Node(key, value, null);
  57.         //头部第一个有效节点
  58.         Node oldFirst = head.next;
  59.         newNode.next = oldFirst;
  60.         head.next = newNode;
  61.         //元素个数+1；
  62.         current++;
  64.     }
  66.     //删除符号表中键为key的键值对
  67.     public void delete(Key key) {
  68.         //找到键为key的结点，把该结点从链表中删除
  69.         Node node = head;
  70.         while (node.next != null) {
  71.             //判断node结点的下一个结点的键是否为key，如果是，就删除该结点
  72.             if (node.next.key.equals(key)) {
  73.                 node.next = node.next.next;
  74.                 current--;
  75.                 return;
  76.             }
  77.             //变换node
  78.             node = node.next;
  79.         }
  80.     }
  82.     //从符号表中获取key对应的值
  83.     public Value get(Key key) {
  84.         //找到键为key的结点
  85.         Node node = head;
  86.         while (node.next != null) {
  87.             //变换n
  88.             node = node.next;
  89.             if (node.key.equals(key)) {
  90.                 return node.value;
  91.             }
  92.         }
  93.         return null;
  94.     }
  97. }

7.1.2 测试代码

  1. package com.ycc.data.structure.test;
  3. import com.ycc.data.structure.line.MySymbolTable;
  5. /**
  6.  * @author liaozx
  7.  * @date 2020/11/24
  8.  */
  9. public class MySymbolTableTest {
  10.     public static void main(String[] args) {
  11.         //创建符号表对象
  12.         MySymbolTable<Integer, String> symbolTable = new MySymbolTable<>();
  13.         //测试put方法（插入,替换）
  14.         symbolTable.put(1, "yanyulou1");
  15.         symbolTable.put(2, "yanyulou2");
  16.         symbolTable.put(3, "yanyulou3");
  18.         symbolTable.put(2, "yanyulou4");
  19.         System.out.println("替换完毕后的元素的个数为:" + symbolTable.size());
  21.         //测试get方法
  22.         System.out.println("替换完毕后，键2对应的值为:" + symbolTable.get(2));
  24.         //测试删除方法
  25.         symbolTable.delete(2);
  26.         System.out.println("删除完毕后，元素的个数:" + symbolTable.size());
  29.     }
  30. }

7.2 有序符号表

我们需要根据键的大小进行排序，插入数据时要考虑顺序

7.2.1 代码实现

  1. package com.ycc.data.structure.line;
  3. /**
  4.  * @author liaozx
  5.  * @date 2020/11/24
  6.  */
  7. public class MyOrderSymbolTable<Key extends Comparable<Key>, Value> {
  8.     //记录首结点
  9.     private Node head;
  10.     //记录符号表中元素的个数
  11.     private int current;
  13.     private class Node {
  14.         //键
  15.         public Key key;
  16.         //值
  17.         public Value value;
  18.         //下一个结点
  19.         public Node next;
  21.         public Node(Key key, Value value, Node next) {
  22.             this.key = key;
  23.             this.value = value;
  24.             this.next = next;
  25.         }
  26.     }
  28.     public MyOrderSymbolTable() {
  29.         this.head = new Node(null, null, null);
  30.         this.current = 0;
  31.     }
  33.     //获取符号表中键值对的个数
  34.     public int size() {
  35.         return current;
  36.     }
  38.     //往符号表中插入键值对
  39.     public void put(Key key, Value value) {
  40.         //定义两个Node变量，分别记录当前结点和当前结点的上一个结点
  41.         Node curr = head.next;
  42.         Node pre = head;
  43.         //1.如果key大于当前结点的key，则一直寻找下一个结点
  44.         while (curr != null && key.compareTo(curr.key) > 0) {
  45.             //变换当前结点和前一个结点即可
  46.             pre = curr;
  47.             curr = curr.next;
  48.         }
  50.         //如果当前结点curr的键和要插入的key一样，则替换
  51.         if (curr != null && key.compareTo(curr.key) == 0) {
  52.             curr.value = value;
  53.             return;
  54.         }
  56.         //如果当前结点curr的键和要插入的key不一样，把新的结点插入到curr之前
  57.         Node newNode = new Node(key, value, curr);
  58.         pre.next = newNode;
  59.         //元素的个数+1；
  60.         current++;
  62.     }
  64.     //删除符号表中键为key的键值对
  65.     public void delete(Key key) {
  66.         //找到键为key的结点，把该结点从链表中删除
  67.         Node node = head;
  68.         while (node.next != null) {
  69.             //判断n结点的下一个结点的键是否为key，如果是，就删除该结点
  70.             if (node.next.key.equals(key)) {
  71.                 node.next = node.next.next;
  72.                 current--;
  73.                 return;
  74.             }
  75.             //变换n
  76.             node = node.next;
  77.         }
  78.     }
  80.     //从符号表中获取key对应的值
  81.     public Value get(Key key) {
  82.         //找到键为key的结点
  83.         Node node = head;
  84.         while (node.next != null) {
  85.             //变换n
  86.             node = node.next;
  87.             if (node.key.equals(key)) {
  88.                 return node.value;
  89.             }
  90.         }
  91.         return null;
  92.     }
  93. }

7.2.2 测试代码

  1. package com.ycc.data.structure.test;
  3. import com.ycc.data.structure.line.MyOrderSymbolTable;
  5. /**
  6.  * @author liaozx
  7.  * @date 2020/11/24
  8.  */
  9. public class MyOrderSymbolTableTest {
  10.     public static void main(String[] args) {
  11.         //创建有序符号表对象
  12.         MyOrderSymbolTable<Integer, String> table = new MyOrderSymbolTable<>();
  13.         table.put(1, "张1");
  14.         table.put(2, "张2");
  15.         table.put(4, "张4");
  16.         table.put(7, "张7");
  17.         table.put(3, "张3");
  18.         System.out.println("table" + table);
  19.     }
  20. }

7.3 跳跃表

跳跃表（SkipList）是一种可以替代平衡树的数据结构。跳跃表让已排序的数据分布在多层次的链表结构中，默认是将 Key值升序排列的，以0-1 的随机值决定一个数据是否能够攀升到高层次的链表中。它通过容许一定的数据冗余，达到 “以空间换时间” 的目的。跳跃表的效率和AVL相媲美，查找、添加、插入、删除操作都能够在 O(LogN) 的复杂度内完成。

image.png

  • 一个跳跃表应该有若干个层（Level）链表组成；
  • 跳跃表中最底层的链表包含所有数据， 每一层链表中的数据都是有序的；
  • 如果一个元素X出现在第i层，那么编号比 i 小的层都包含元素 X；
  • 第 i 层的元素通过一个指针指向下一层拥有相同值的元素；
  • 在每一层中，-∞ 和 +∞ 两个元素都出现(分别表示 INT_MIN 和 INT_MAX)；
  • 头指针（head）指向最高一层的第一个元素；

节点模型
image.png

7.3.1 代码实现

主要实现功能:

  • get(Integer key) ： 根据 key 值查找某个元素
  • put(Integer key, Object value) ：插入一个新的元素，元素已存在时为修改操作
  • remove(Integer key)： 根据 key 值删除某个元素 ```java package com.ycc.data.structure.line;

import java.util.Random;

/**

  • 跳跃表 *
  • @author liaozx

  • @date 2020/10/24 */ public class MySkipList {

    // 节点数量 private int number; // 节点最大层数 private int height;

    // 第一个节点 private SkipListEntry head; // 最后一个节点 private SkipListEntry tail;

    private Random random;

    private class SkipListEntry {

    1.  // data
    2.  public Integer key;
    3.  public E value;
    5.  // links
    6.  public SkipListEntry up;
    7.  public SkipListEntry down;
    8.  public SkipListEntry left;
    9.  public SkipListEntry right;
    11.  // constructor
    12.  public SkipListEntry(Integer key, E value) {
    13.      this.key = key;
    14.      this.value = value;
    15.  }

    }

    public MySkipList() {

    1.  // 创建 head 节点
    2.  this.head = new SkipListEntry(Integer.MIN_VALUE, null);
    3.  // 创建 tail 节点
    4.  this.tail = new SkipListEntry(Integer.MAX_VALUE, null);
    5.  // 将 head 节点的右指针指向 tail 节点
    6.  this.head.right = tail;
    7.  // 将 tail 节点的左指针指向 head 节点
    8.  this.tail.left = head;
    10.  this.height = 0;
    11.  this.number = 0;
    12.  this.random = new Random();

    }

    public Object get(Integer key) {

    1.  SkipListEntry p = findEntry(key);
    2.  if (p.key.equals(key)) {
    3.      return p.value;
    4.  } else {
    5.      return null;
    6.  }

    }

    public Object put(Integer key, Object value) {

    1.  SkipListEntry p, q;
    2.  int i = 0;
    3.  // 查找适合插入的位子
    4.  p = findEntry(key);
    6.  // 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
    7.  if (p.key.equals(key)) {
    8.      Object oldValue = p.value;
    9.      p.value = value;
    10.      return oldValue;
    11.  }
    13.  // 如果跳跃表中不存在含有key值的节点，则进行新增操作
    14.  q = new SkipListEntry(key, value);
    15.  q.left = p;
    16.  q.right = p.right;
    17.  p.right.left = q;
    18.  p.right = q;
    20.  // 再使用随机数决定是否要向更高level攀升 ， 抛硬币， 50% 概率
    21.  while (random.nextDouble() < 0.5) {
    23.      // 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
    24.      if (i >= height) {
    25.          addEmptyLevel();
    26.      }
    28.      //从p向左扫描含有高层节点的节点
    29.      while (p.up == null) {
    30.          p = p.left;
    31.      }
    32.      p = p.up;
    34.      // 新增和q指针指向的节点含有相同key值的节点对象
    35.      // 这里需要注意的是除底层节点之外的节点对象是不需要value值的
    36.      SkipListEntry z = new SkipListEntry(key, null);
    38.      z.left = p;
    39.      z.right = p.right;
    40.      p.right.left = z;
    41.      p.right = z;
    43.      z.down = q;
    44.      q.up = z;
    46.      q = z;
    47.      i = i + 1;
    48.  }
    49.  number = number + 1;
    50.  // 返回null，没有旧节点的value值
    51.  return null;

    }

    public Object remove(Integer key) {

    1.  SkipListEntry p, q;
    3.  p = findEntry(key);
    5.  if (!p.key.equals(key)) {
    6.      return null;
    7.  }
    8.  Object oldValue = p.value;
    9.  while (p != null) {
    10.      q = p.up;
    11.      p.left.right = p.right;
    12.      p.right.left = p.left;
    13.      p = q;
    14.  }
    15.  return oldValue;

    }

  1. /**
  2.  * 创建新的空索引层
  3.  */
  4. private void addEmptyLevel() {
  6.     SkipListEntry p1, p2;
  8.     p1 = new SkipListEntry(Integer.MIN_VALUE, null);
  9.     p2 = new SkipListEntry(Integer.MAX_VALUE, null);
  11.     p1.right = p2;
  12.     p1.down = head;
  14.     p2.left = p1;
  15.     p2.down = tail;
  17.     head.up = p1;
  18.     tail.up = p2;
  20.     head = p1;
  21.     tail = p2;
  23.     height = height + 1;
  24. }
  27. private SkipListEntry findEntry(Integer key) {
  28.     // 从head头节点开始查找
  29.     SkipListEntry p = head;
  30.     while (true) {
  31.         // 从左向右查找，直到右节点的key值大于要查找的key值
  32.         while (p.right.key <= key) {
  33.             p = p.right;
  34.         }
  35.         // 如果有更低层的节点，则向低层移动
  36.         if (p.down != null) {
  37.             p = p.down;
  38.         } else {
  39.             break;
  40.         }
  41.     }
  42.     // 返回p，！注意这里p的key值是小于等于传入key的值的（p.key <= key）
  43.     return p;
  44. }

}

  1. <a name="M6f9V"></a>
  2. ### 7.3.2 测试代码
  3. ```java
  4. package com.ycc.data.structure.test;
  6. import com.ycc.data.structure.line.MySkipList;
  8. /**
  9.  * @author liaozx
  10.  * @date 2020/11/24
  11.  */
  12. public class MySkipListTest {
  13.     public static void main(String[] args) {
  14.         MySkipList mySkipList = new MySkipList();
  16.         mySkipList.put(1, "yanyu0");
  17.         mySkipList.put(2, "yanyu1");
  18.         mySkipList.put(3, "yanyu2");
  19.         mySkipList.put(4, "yanyu3");
  20.         mySkipList.put(5, "yanyu4");
  21.         mySkipList.put(6, "yanyu5");
  22.         System.out.println("mySkipList" + mySkipList);
  24.     }
  25. }