数据结构与算法|线性结构

秒速五厘米 2024-04-22 22:01 146阅读 0赞

数据结构与算法|线性结构

  • 第二章 线性结构
    • 2.1 多项式表示
    • 2.2 什么是线性表
    • 2.3 线性表的实现方式
      • 2.3.1 线性表的顺序存储实现
      • 2.3.2 线性表的链式存储实现
          1. 单链表实现
          1. 双链表实现

上篇：第一章、绪论

第二章 线性结构

线性结构是数据结构中最基础的，也是最简单的一种数据结构，其中典型的叫做 “线性表” ，那什么是线性表呢？

2.1 多项式表示

举个简单的例子：一元多项式及其运算

在这里插入图片描述

主要运算：多项式相加、相减、相乘等，怎样用程序设计语言来表示这两个多项式以及实现对应的操作？

【分析】如何表示多项式？

对应多项式来讲，它的关键信息主要有这么几个，一个是它的项数，包括它的最高指数，另外一个是要表现多项式的每一项，而多项式的每一项的关键信息，又是每一项的系数和指数

  • 多项式项数 n n n
  • 各项系数 a i a_{i} ai 及指数 i i i

方法一：顺序存储结构直接表示

数组各分量对应多项式各项，这个分量主要表示每一项的系数，指数可以对应该分量的下标

例如： f ( x ) = 4 x 3 − 3 x 2 + 1 f(x)=4x^{3}-3x^{2}+1 f(x)=4x3−3x2+1
表示成：
在这里插入图片描述

两个多项式相加：两个数组对应分量相加

问题：那如何表示以下多项式？

f ( x ) = x + 3 x 2000 f(x)=x+3x^{2000} f(x)=x+3x2000

如果还是按照上面的顺序存储结构表示该多项式，很显然我们至少得用 2001 个分量得这样得一个数字来表示，而这 2001 个分量，其实只有 2 项是非零的，这样的一种表示方法显然会造成空间的巨大浪费，而且从 0~2001 ，很多计算都是无效的（0），那么有没有更好的方法，为什么一定要把所有零项、非零项、系数为零的，非零的，全部要表示进来呢？有没有可能只表示非零项？所以这就引入了第二种方法：顺序存储结构表示非零项

方法二：顺序存储结构表示非零项

它的基本思路是这样的，只表示非零项，每个非零项 a i x i a_{i}x^{i} aixi 涉及两个信息：系数 a i a_{i} ai 和指数 i i i，可以将一个多项式看成一个 ( a i , i ) (a_{i},i) (ai,i) 二元组合的集合。也可以用数组表示，但是与方法一不同，方法一每一个分量是系数，而现在每个分量不仅要包含系数，也要包含指数，那用什么样的数组呢？

用结构数组表示：数组分量是由系数 a i a_{i} ai、指数 i i i 组成的结构，对应一个非零项

例如： P ( x ) 1 = 9 x 12 + 15 x 8 + 3 x 2 P(x)_{1}=9x^{12}+15x^{8}+3x^{2} P(x)1=9x12+15x8+3x2 和 P ( x ) 2 = 26 x 19 − 4 x 8 − 13 x 6 + 82 P(x)_{2}=26x^{19}-4x^{8}-13x^{6}+82 P(x)2=26x19−4x8−13x6+82 ，可以很简单的使用如下数组来表示

在这里插入图片描述

比方说这个，它就是一个结构，每一个分量包含了系数和指数，这样的表示方法，显然我们只需要表示非零项就可以，很多为零的项就可以省下不写，对于前面的 f ( x ) = x + 3 x 2000 f(x)=x+3x^{2000} f(x)=x+3x2000 ，只需要用两个分量就能表示，显然节省了很多空间，只要每一项都按照指数大小有序进行存储运算起来也很方便。这种方式不仅节省空间，在效率上也是比较高的，但是还是有其它的方法来表示。

方法三：链表结构存储非零项

链表中包含每个结点存储多项式的一个非零项，包括系数和指数两个数据域以及一个指针域，把它们串起来，同样，排列的时候，仍然可以按照指数递降（或者递增）的顺序进行排列
在这里插入图片描述

  1. public class Node {
  4.     private int coef;
  5.     private int expon;
  6.     private Node next;
  8.     public Node(int coef,int expon) {
  10.         this.coef = coef;
  11.         this.expon = expon;
  12.     }
  13. }

P ( x ) 1 = 9 x 12 + 15 x 8 + 3 x 2 P(x)_{1}=9x^{12}+15x^{8}+3x^{2} P(x)1=9x12+15x8+3x2 和 P ( x ) 2 = 26 x 19 − 4 x 8 − 13 x 6 + 82 P(x)_{2}=26x^{19}-4x^{8}-13x^{6}+82 P(x)2=26x19−4x8−13x6+82 这两个多项式用指针表示如图所示：

在这里插入图片描述

由上可以看出，同样一个问题，可以用多种方式去实现，其次是有序线性序列的组织和管理。

2.2 什么是线性表

线性表（Linear List）：是具有相同数据类型的 n 个元素的有序集合。

线性表的逻辑结构表示：
( a 0 , a 1 , . . . , a i , a i + 1 , . . . , a n − 1 ) (a_{0},a_{1},…,a_{i},a_{i+1},…,a_{n-1}) (a0,a1,…,ai,ai+1,…,an−1)

线性表的基本特征：

  • 表中的元素个数 n 称为表的长度，n=0 是称为空表

  • 当 1 < i < n 1 < i <n 1<i<n 时

    • ① 第 i i i 个元素 a [ i ] a[i] a[i] 的直接前驱是 a [ i − 1 ] a[i-1] a[i−1]， a [ 0 ] a[0] a[0] 无直接前驱
    • ② 第 i i i 个元素 a [ i ] a[i] a[i] 的直接后继是 a [ i + 1 ] a[i+1] a[i+1]， a [ n − 1 ] a[n-1] a[n−1] 无直接后继
  • 所有元素的类型必须相同，且不能出现缺项
  • 每个数据元素既可以是基本的数据类型，也可以是复杂的数据类型
  • 线性表中数据元素与位置相关，即每个数据元素有唯一的序号

用图形表示的逻辑结构：

433bff81c082faad8a5200a2465e338b.png_pic_center
线性表中每个元素 a i a_{i} ai 的唯一位置通过序号或索引 i i i 表示，为了算法设计方便，将逻辑序号和存储序号统一，均假设从 0 开始，这样含 n n n 个元素的线性表的元素序号 i i i 满足 0 ≤ i ≤ n − 1 0 \le i \le n-1 0≤i≤n−1。

在 Java 语言中，接口 java.util.List<E> 用于表示线性表，ADT 定义如下：

ADT List {
数据对象：
D = { a i      ∣      0 ≤ i ≤ n − 1 ,    n ≥ 0 ,    a i 为 E 类型 } D=\left \{ a_{i} \;\;|\;\; 0 \le i \le n-1, \; n \ge 0, \; a_{i} 为 E 类型 \right \} D={ ai∣0≤i≤n−1,n≥0,ai为E类型}
数据关系：
r = { < a i , a i + 1 >    ∣    a i ,    a i + 1 ∈ D ,    i = 0 , . . . , n − 2 } r=\left \{ \;|\; a_{i}, \; a_{i+1} \in D, \; i=0,…,n-2 \right \} r={ ∣ai,ai+1∈D,i=0,…,n−2}
基本运算（11个）：
List()：创建线性表
boolean add(E e)：将指定的元素追加到此列表的末尾
void add(int index, E element)：将指定的元素插入此列表中的指定位置
boolean contains(Object o)：如果此列表包含指定元素，则返回 true
E get(int index)：返回此列表中指定位置的元素
int indexOf(Object o)：返回此列表中指定位置的元素
boolean isEmpty()：如果此列表不包含元素，则返回 true
E remove(int index)：删除该列表中指定位置的元素
boolean remove(Object o)：从列表中删除指定元素的第一个出现（如果存在）
E set(int index, E element)：用指定的元素替换此列表中指定位置的元素
int size()：返回此列表中的元素数
String toString()：将线性表转换为字符串
}

以下实现方式为了避免内容过于冗余，只挑选了部分基本运算进行演示。

2.3 线性表的实现方式

2.3.1 线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

在这里插入图片描述

在 Java 中最典型的集合类 ArrayList 就是以这种方式实现的，在 ArrayList 中维护了一个 Object 类型的数组 elementData，关于 ArrayList 的源码分析可见博客：ArrayList-源码解读

当然我们也可以自己用数组去实现一个线性表，先创建一个 ArrLinearList 类，因为不知道线性表具体会存放哪种数据类型，可以泛型 Element 来表示任意类型的数据，如下：

  1. public class ArrLinearList<Element> {
  4. }

（1）初始化

既然底层是数组，那么必然要有数组类型（Object[]）的属性 data 来存放数据，通过 size 属性来记录线性表的大小。

在初始化的时候自然是要创建一个数组对象赋给 data，初始时线性表的长度 size 为 0，在 Java 可以将初始化的逻辑放在构造方法中，代码如下：

  1. public class ArrLinearList<Element> {
  4.     // 数据元素
  5.     private Object[] data;
  6.     // 线性表大小
  7.     private int size;
  8.     // 初始容量大小
  9.     private static final int INIT_CAPACITY = 10;
  11.     /**
  12.      * 无参构造方法
  13.      */
  14.     public ArrLinearList() {
  16.         init(INIT_CAPACITY);
  17.     }
  19.     /**
  20.      * 有参构造方法
  21.      * @param capacity 指定设置容量大小
  22.      */
  23.     public ArrLinearList(int capacity) {
  25.         // 如果指定的容量大小小于或等于零，则初始化容量大小为默认容量大小
  26.         if (capacity <= 0) {
  28.             capacity = INIT_CAPACITY;
  29.         }
  30.         // 初始化
  31.         init(capacity);
  32.     }
  34.     /**
  35.      * 初始化
  36.      * @param maxSize 数组的最大容量
  37.      */
  38.     private void init(int maxSize) {
  40.         // 创建一个大小为 10 的 Object 数组
  41.         data = new Object[maxSize];
  42.         // 初始化时线性表的大小为 0
  43.         size = 0;
  44.     }
  46. }

（2）根据位序 index，查询相应的元素

因为底层时数组，可以通过数组的坐标直接得到位于 index 上的元素

  1. /**
  2.      * 根据位序 index，返回相应元素
  3.      * @param index 为序
  4.      * @return 元素
  5.      */
  6.     // 压制不安全的类型转换的警告
  7.     @SuppressWarnings("unchecked")
  8.     public Element get(int index) {
  10.         // 校验坐标是否合法
  11.         if (index >= size || index < 0) {
  13.             // 位置不合法
  14.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  15.         }
  16.         return (Element) data[index];
  17.     }

（3）通过元素 Element，查找所在位置

分为两种情况，首先是当 element 为 null 时，则查询数组中第一个为 null 元素的坐标位置，如果 element 不为 null，则遍历数组，通过 equals() 方法去比较，如果相同则返回坐标位置

  1. /**
  2.      * 通过元素 Element，查找所在位置
  3.      * @param element 元素
  4.      * @return 所在位置
  5.      */
  6.     public int indexOf(Object element) {
  8.         if (element == null) {
  10.             // 遍历数组
  11.             for (int i = 0; i < size; i++) {
  13.                 if (data[i] == null)
  14.                     return i;
  15.             }
  16.         } else {
  18.             for (int i = 0; i < size; i++) {
  20.                 if (element.equals(data[i]))
  21.                     return i;
  22.             }
  23.         }
  24.         return -1;
  25.     }

（4）在指定位序 index 上插入一个新的元素

往线性表中 index 位置上添加一个元素（0 <= index <= size），分为两种情况

  • 情况一：index 等于线性表的大小，表示在末位添加元素，直接将 element 放到 index 位置上，线性表大小加一
  • 情况二：index 小于线性表的大小，则需要先将位于 index 以及之后的所有元素往后挪动一位，再将元素 element 放到 index 位置上，线性表大小加一

在这里插入图片描述

还有个需要考虑的问题就是当添加的元素数量大于 data 数组的容量时要怎么扩容，通常情况下的做法就是重新创建一个新的数组，将原数组的数据复制到新数组中，再进行元素的添加，原理如下：

在这里插入图片描述

  1. /**
  2.      * 将指定元素添加到线性表的末位
  3.      * @param element 元素
  4.      */
  5.     public void add(Element element) {
  7.         add(size, element);
  8.     }
  10.     /**
  11.      * 在指定位序上插入一个新的元素
  12.      * @param index 位序
  13.      * @param element 元素
  14.      */
  15.     public void add(int index, Element element) {
  17.         // 如果插入元素的坐标大于线性表的大小
  18.         if (index > size || index < 0) {
  20.             // 位置不合法
  21.             throw new RuntimeException("Index: "+index+", Size: "+size);
  22.         }
  23.         // 判断当前线性表的大小是否等于容量大小
  24.         if (size == data.length) {
  26.             // 如果插入当前元素后线性表的大小大于容器的大小，则进行扩容
  27.             ensureCapacity();
  28.         }
  29.         // 判断插入位置是否小于线性表长度(头部或者中间插入)
  30.         if (index < size) {
  32.             // 先将线性表位于 index 以及之后的元素都往后挪一位
  33.             for (int i = size; i > index; i--) {
  35.                 data[i] = data[i-1];
  36.             }
  37.         }
  38.         // 在 index 位序上插入元素
  39.         data[index] = element;
  40.         // 线性表大小加一
  41.         size++;
  42.     }
  44.     /**
  45.      * 自动扩容方法
  46.      */
  47.     public void ensureCapacity() {
  49.         // 新容量的大小是原容量大小的 1.5 倍
  50.         int newCapacity = data.length + (data.length >> 1);
  51.         // 创建新数组
  52.         Object[] newDate = new Object[newCapacity];
  53.         // 将原数组中的内容复制到新数组中
  54.         for (int i = 0; i < data.length; i++) {
  56.             newDate[i] = data[i];
  57.         }
  58.         // 将线性表存放数据的数组指向新的数组
  59.         data = newDate;
  60.     }

（5）删除指定位序 index 的元素

在线性表中如果需要删除指定位置 index 上的元素，只需要将 index 之后的元素都向前挪动一位即可，线性表大小减一

在这里插入图片描述

  1. /**
  2.      * 删除指定位序的元素
  3.      * @param index 位序
  4.      */
  5.     public void remove(int index) {
  7.         // 如果删除元素的坐标大于等于或者小于线性表的大小
  8.         if (index >= size || index < 0) {
  10.             // 位置不合法
  11.             throw new RuntimeException("Index: "+index+", Size: "+size);
  12.         }
  13.         // 判断删除的元素是否为末端元素
  14.         if (index == size-1) {
  16.             // 删除的是最后一个元素
  17.             data[index] = null;
  18.         } else {
  20.             for (int i = index; i < size; i++) {
  22.                 data[i] = data[i+1];
  23.             }
  24.         }
  25.         // 线性表大小减一
  26.         size--;
  27.     }
  29.     /**
  30.      * 从列表中删除指定元素的第一个出现（如果存在）
  31.      * @param element 元素
  32.      */
  33.     public void remove(Element element) {
  35.         int index = indexOf(element);
  36.         if (index != -1) {
  38.             remove(index);
  39.         }
  40.     }

（6）获取线性表的长度

上述代码每增加一个元素会让 size+1，每删除一个元素 size-1，所以直接获取 size 即为线性表的大小

  1. /**
  2.      * 获取线性表大小
  3.      * @return 线性表大小
  4.      */
  5.     public int size() {
  7.         return size;
  8.     }

完整代码示例：

  1. public class ArrLinearList<Element> {
  4.     // 数据元素
  5.     private Object[] data;
  6.     // 线性表大小
  7.     private int size;
  8.     // 初始容量大小
  9.     private static final int INIT_CAPACITY = 10;
  11.     /**
  12.      * 无参构造方法
  13.      */
  14.     public ArrLinearList() {
  16.         init(INIT_CAPACITY);
  17.     }
  19.     /**
  20.      * 有参构造方法
  21.      * @param capacity 指定设置容量大小
  22.      */
  23.     public ArrLinearList(int capacity) {
  25.         // 如果指定的容量大小小于或等于零，则初始化容量大小为默认容量大小
  26.         if (capacity <= 0) {
  28.             capacity = INIT_CAPACITY;
  29.         }
  30.         // 初始化
  31.         init(capacity);
  32.     }
  34.     /**
  35.      * 初始化
  36.      * @param maxSize 数组的最大容量
  37.      */
  38.     private void init(int maxSize) {
  40.         // 创建一个大小为 10 的 Object 数组
  41.         data = new Object[maxSize];
  42.         // 初始化时线性表的大小为 0
  43.         size = 0;
  44.     }
  46.     /**
  47.      * 根据位序 index，返回相应元素
  48.      * @param index 为序
  49.      * @return 元素
  50.      */
  51.     // 压制不安全的类型转换的警告
  52.     @SuppressWarnings("unchecked")
  53.     public Element get(int index) {
  55.         // 校验坐标是否合法
  56.         if (index >= size || index < 0) {
  58.             // 位置不合法
  59.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  60.         }
  61.         return (Element) data[index];
  62.     }
  64.     /**
  65.      * 通过元素 Element，查找所在位置
  66.      * @param element 元素
  67.      * @return 所在位置
  68.      */
  69.     public int indexOf(Object element) {
  71.         if (element == null) {
  73.             // 遍历数组
  74.             for (int i = 0; i < size; i++) {
  76.                 if (data[i] == null)
  77.                     return i;
  78.             }
  79.         } else {
  81.             for (int i = 0; i < size; i++) {
  83.                 if (element.equals(data[i]))
  84.                     return i;
  85.             }
  86.         }
  87.         return -1;
  88.     }
  90.     /**
  91.      * 将指定元素添加到线性表的末位
  92.      * @param element 元素
  93.      */
  94.     public void add(Element element) {
  96.         add(size, element);
  97.     }
  99.     /**
  100.      * 在指定位序上插入一个新的元素
  101.      * @param index 位序
  102.      * @param element 元素
  103.      */
  104.     public void add(int index, Element element) {
  106.         // 如果插入元素的坐标大于线性表的大小
  107.         if (index > size || index < 0) {
  109.             // 位置不合法
  110.             throw new RuntimeException("Index: "+index+", Size: "+size);
  111.         }
  112.         // 判断当前线性表的大小是否等于容量大小
  113.         if (size == data.length) {
  115.             // 如果插入当前元素后线性表的大小大于容器的大小，则进行扩容
  116.             ensureCapacity();
  117.         }
  118.         // 判断插入位置是否小于线性表长度(头部或者中间插入)
  119.         if (index < size) {
  121.             // 先将线性表位于 index 以及之后的元素都往后挪一位
  122.             for (int i = size; i > index; i--) {
  124.                 data[i] = data[i-1];
  125.             }
  126.         }
  127.         // 在 index 位序上插入元素
  128.         data[index] = element;
  129.         // 线性表大小加一
  130.         size++;
  131.     }
  133.     /**
  134.      * 自动扩容方法
  135.      */
  136.     public void ensureCapacity() {
  138.         // 新容量的大小是原容量大小的 1.5 倍
  139.         int newCapacity = data.length + (data.length >> 1);
  140.         // 创建新数组
  141.         Object[] newDate = new Object[newCapacity];
  142.         // 将原数组中的内容复制到新数组中
  143.         for (int i = 0; i < data.length; i++) {
  145.             newDate[i] = data[i];
  146.         }
  147.         // 将线性表存放数据的数组指向新的数组
  148.         data = newDate;
  149.     }
  151.     /**
  152.      * 删除指定位序的元素
  153.      * @param index 位序
  154.      */
  155.     public void remove(int index) {
  157.         // 如果删除元素的坐标大于等于或者小于线性表的大小
  158.         if (index >= size || index < 0) {
  160.             // 位置不合法
  161.             throw new RuntimeException("Index: "+index+", Size: "+size);
  162.         }
  163.         // 判断删除的元素是否为末端元素
  164.         if (index == size-1) {
  166.             // 删除的是最后一个元素
  167.             data[index] = null;
  168.         } else {
  170.             for (int i = index; i < size; i++) {
  172.                 data[i] = data[i+1];
  173.             }
  174.         }
  175.         // 线性表大小减一
  176.         size--;
  177.     }
  179.     /**
  180.      * 从列表中删除指定元素的第一个出现（如果存在）
  181.      * @param element 元素
  182.      */
  183.     public void remove(Element element) {
  185.         int index = indexOf(element);
  186.         if (index != -1) {
  188.             remove(index);
  189.         }
  190.     }
  192.     /**
  193.      * 用指定的元素替换此列表中指定位置的元素
  194.      * @param index 指定位置
  195.      * @param element 指定元素
  196.      * @return 替换掉的元素
  197.      */
  198.     @SuppressWarnings("unchecked")
  199.     public Element set(int index, Element element) {
  201.         // 校验坐标是否合法
  202.         if (index >= size || index < 0) {
  204.             // 位置不合法
  205.             throw new RuntimeException("Index: "+index+", Size: "+size);
  206.         }
  207.         Element oldElement =(Element) data[index];
  208.         data[index] = element;
  209.         return oldElement;
  210.     }
  212.     /**
  213.      * 判断指定元素是否在线性表中
  214.      * @return true 表示存在 false 表示不存在
  215.      */
  216.     public boolean contains(Element element) {
  218.         return indexOf(element) != -1;
  219.     }
  221.     /**
  222.      * 获取线性表大小
  223.      * @return 线性表大小
  224.      */
  225.     public int size() {
  227.         return size;
  228.     }
  230.     /**
  231.      * 判断当前线性表是否为空
  232.      * @return true 表示为空 false 表示不为空
  233.      */
  234.     public boolean isEmpty() {
  236.         return size == 0;
  237.     }
  239.     /**
  240.      * 返回当前线性表的字符串表示
  241.      * @return 线性表字符串表示
  242.      */
  243.     public String toString() {
  245.        StringBuilder str = new StringBuilder("[");
  246.         for (int i = 0; i < size-1; i++) {
  248.             str.append(this.data[i]).append(",");
  249.         }
  250.         if (size > 0) {
  252.             str.append(this.data[size - 1]);
  253.         }
  254.         str.append("]");
  255.         return str.toString();
  256.     }
  257. }

2.3.2 线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻，通过 “链” 建立起数据元素之间的逻辑关系。

插入、删除不需要移动数据元素，只需修改 “链” 即可。

在这里插入图片描述

链表主要可分为：单向链表、双向链表 和 循环链表，

  • 单向链表：每个节点只设置一个指向后继节点的指针成员，这样的链表成为线性单向链接表，简称单链表
    在这里插入图片描述
  • 双向链表：每个节点设置两个指针成员，分别用以指向其前驱节点和后继节点，这样的链表称之为线性双向链接表，简称双链表
    在这里插入图片描述

在 Java 中非常典型的集合类 LinkedList ，其底层使用的就是双向链表，关于 LinkedList 的源码分析可见博客：LinkedList-源码解读

同样我们也可以自己用链表结构实现一个线性表，创建一个 LinkLinearList 类，使用泛型 Element 去约束数据类型

  1. public class LinkLinearList<Element> {
  4. }
1. 单链表实现

（1）初始化

因为底层采用的是链表结构，故在该类内部定义一个内部类 Node，存放链表的节点信息，元素 data 及其后继节点 next，在 LinkLinearList 中设置属性 header 和 tail 分别记录头节点和尾节点，在构造方法中初始化线性表大小为 0

  1. public class LinkLinearList<Element> {
  4.     // 头节点
  5.     private Node<Element> header;
  6.     // 尾节点
  7.     private Node<Element> tail;
  8.     // 线性表的长度
  9.     private int size;
  11.     /**
  12.      * 节点
  13.      * @param <Element> 数据元素类型
  14.      */
  15.     public static class Node<Element> {
  18.         // 数据元素
  19.         private Element data;
  20.         // 后继节点
  21.         private Node<Element> next;
  23.     }
  25.     /**
  26.      * 无参构造方法
  27.      */
  28.     public LinkLinearList() {
  30.         // 初始化线性表的长度
  31.         size = 0;
  32.     }
  33. }

（2）根据位序 index，查询相应的元素

因为底层是链表，如果想要获取某个 index 位置上的数据，只能遍历链表，得到 index 位置上的节点，再返回节点数据

  1. /**
  2.      * 根据位序 index，返回相应元素
  3.      * @param index 为序
  4.      * @return 元素
  5.      */
  6.     public Element get(int index) {
  8.         if (index >= size) {
  10.             // 位序大于线性表的大小
  11.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  12.         }
  13.         // 返回指定位序节点下的数据元素
  14.         return findNode(index).data;
  15.     }
  17.     // 通过位序获取节点
  18.     public Node<Element> findNode(int index) {
  20.         // 目标节点
  21.         Node<Element> target = null;
  22.         // 遍历链表（可采用二分法进行优化）
  23.         Node<Element> node = header;
  24.         for (int i = 0; i < size; i++) {
  26.             if (i == index) {
  28.                 target = node;
  29.                 break;
  30.             }
  31.             node = node.next;
  32.         }
  33.         // 返回对应节点
  34.         return target;
  35.     }

（3）通过元素 Element，查找所在位置

分为两种情况，首先是当 element 为 null 时，则查询l链表中第一个为 null 元素的坐标位置，如果 element 不为 null，则遍历链表，通过 equals() 方法去比较，如果相同则返回坐标位置

  1. /**
  2.      * 通过元素 Element，查找所在位置
  3.      * @param element 元素
  4.      * @return 所在位置
  5.      */
  6.     public int indexOf(Object element) {
  8.         int index = 0;
  9.         Node<Element> node = header;
  10.         if (element == null) {
  12.             // 遍历链表
  13.             do {
  15.                 if (node.data == null)
  16.                     return index;
  17.                 index++;
  18.                 node = node.next;
  19.             } while (node != null);
  20.         } else {
  22.             // 遍历链表
  23.             do {
  25.                 if (element.equals(node.data))
  26.                     return index;
  27.                 index++;
  28.                 node = node.next;
  29.             } while (node != null);
  30.         }
  31.         return -1;
  32.     }

（4）在指定位序 index 上插入一个新的元素

在链表中添加元素可分为三种情况：

  • 情况一：末位插入，这种情况比较简单，只需要将原末端节点指向新插入的节点就行了

在这里插入图片描述

  • 情况二：头部插入，新添加的节点成为头节点，该节点的后驱节点指向原头节点

在这里插入图片描述

  • 情况三：中间插入，原位置上的前驱节点变为新插入节点的前驱节点，原节点变为新插入节点的后驱节点

在这里插入图片描述

  1. /**
  2.      * 将指定元素添加到线性表的末位
  3.      * @param element 元素
  4.      */
  5.     public void add(Element element) {
  7.         add(size, element);
  8.     }
  10.     /**
  11.      * 在指定位序上插入一个新的元素
  12.      * @param index 位序
  13.      * @param element 元素
  14.      */
  15.     public void add(int index, Element element) {
  17.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  18.         if (!(index >= 0 && index <= size)) {
  20.             // 位置不合法
  21.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  22.         }
  23.         // 末端插入
  24.         if (index == size) {
  26.             // 原尾部节点
  27.             Node<Element> last = tail;
  28.             // 新插入节点
  29.             Node<Element> newNode = new Node<>();
  30.             // 设置节点数据
  31.             newNode.data = element;
  32.             // 尾部节点变为新插入的节点
  33.             tail = newNode;
  34.             if (last == null) {
  36.                 // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
  37.                 header = newNode;
  38.             } else {
  40.                 // 设置原尾部节点的下一个节点为新插入的节点
  41.                 last.next = newNode;
  42.             }
  43.         }
  44.         // 头部或者中间插入
  45.         else {
  47.             // 获取 index-1 位序的节点
  48.             Node<Element> beforeNode = findNode(index-1);
  49.             // 获取原 index 位序的节点
  50.             Node<Element> originNode = findNode(index);
  51.             // 新插入节点
  52.             Node<Element> newNode = new Node<>();
  53.             // 设置节点数据
  54.             newNode.data = element;
  55.             // 设置新插入的节点的 next 为原节点
  56.             newNode.next = originNode;
  57.             if (beforeNode == null) {
  59.                 // 表明在头部插入节点
  60.                 header = newNode;
  61.             } else {
  63.                 // 表明在中间插入节点，则原 index-1 位置上的节点 next 设置为当前插入的节点
  64.                 beforeNode.next = newNode;
  65.             }
  66.         }
  67.         // 线性表大小加一
  68.         size++;
  69.     }

（5）删除指定位序 index 的元素

在链表中删除指定位序的数据就是删除该位置的节点，所以在删除时要注意原节点的前驱节点 beforeNode 应该变为原节点的后驱节点 afterNode，同时也应该要注意删除的是否时头节点或者尾节点
在这里插入图片描述

  1. /**
  2.      * 删除指定位序的元素
  3.      * @param index 位序
  4.      */
  5.     public void remove(int index) {
  7.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  8.         if (!(index >= 0 && index < size)) {
  10.             // 位置不合法
  11.             throw new RuntimeException("Index: "+index+", Size: "+size);
  12.         }
  13.         // 获取 index-1 (前)位序的节点
  14.         Node<Element> beforeNode = findNode(index-1);
  15.         // 获取原 index+1 (后)位序的节点
  16.         Node<Element> afterNode = findNode(index+1);
  17.         if (beforeNode == null) {
  19.             // 如果删除的节点没有前驱节点，则说明删除的节点为头节点，则后置节点设置为头节点
  20.             header = afterNode;
  21.         } else {
  23.             // 删除的节点不是头节点，前置节点的下一个节点设置为后置节点
  24.             beforeNode.next = afterNode;
  25.         }
  26.         // 线性表大小减一
  27.         size--;
  28.     }
  30.     /**
  31.      * 从列表中删除指定元素的第一个出现（如果存在）
  32.      * @param element 元素
  33.      */
  34.     public void remove(Element element) {
  36.         int index = indexOf(element);
  37.         if (index != -1) {
  39.             remove(index);
  40.         }
  41.     }

（6）获取线性表的长度

上述代码每增加一个元素会让 size+1，每删除一个元素 size-1，所以直接获取 size 即为线性表的大小

  1. /**
  2.      * 获取线性表大小
  3.      * @return 线性表大小
  4.      */
  5.     public int size() {
  7.         return size;
  8.     }

完整代码示例：

  1. public class LinkLinearList<Element> {
  4.     // 头节点
  5.     private Node<Element> header;
  6.     // 尾节点
  7.     private Node<Element> tail;
  8.     // 线性表的长度
  9.     private int size;
  11.     /**
  12.      * 节点
  13.      * @param <Element> 数据元素类型
  14.      */
  15.     public static class Node<Element> {
  18.         // 数据元素
  19.         private Element data;
  20.         // 后继节点
  21.         private Node<Element> next;
  23.     }
  25.     /**
  26.      * 无参构造方法
  27.      */
  28.     public LinkLinearList() {
  30.         // 初始化线性表的长度
  31.         size = 0;
  32.     }
  34.     /**
  35.      * 根据位序 index，返回相应元素
  36.      * @param index 为序
  37.      * @return 元素
  38.      */
  39.     public Element get(int index) {
  41.         if (index >= size) {
  43.             // 位序大于线性表的大小
  44.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  45.         }
  46.         // 返回指定位序节点下的数据元素
  47.         return findNode(index).data;
  48.     }
  50.     // 通过位序获取节点
  51.     public Node<Element> findNode(int index) {
  53.         // 目标节点
  54.         Node<Element> target = null;
  55.         // 遍历链表（可采用二分法进行优化）
  56.         Node<Element> node = header;
  57.         for (int i = 0; i < size; i++) {
  59.             if (i == index) {
  61.                 target = node;
  62.                 break;
  63.             }
  64.             node = node.next;
  65.         }
  66.         // 返回对应节点
  67.         return target;
  68.     }
  70.     /**
  71.      * 通过元素 Element，查找所在位置
  72.      * @param element 元素
  73.      * @return 所在位置
  74.      */
  75.     public int indexOf(Object element) {
  77.         int index = 0;
  78.         Node<Element> node = header;
  79.         if (element == null) {
  81.             // 遍历链表
  82.             do {
  84.                 if (node.data == null)
  85.                     return index;
  86.                 index++;
  87.                 node = node.next;
  88.             } while (node != null);
  89.         } else {
  91.             // 遍历链表
  92.             do {
  94.                 if (element.equals(node.data))
  95.                     return index;
  96.                 index++;
  97.                 node = node.next;
  98.             } while (node != null);
  99.         }
  100.         return -1;
  101.     }
  103.     /**
  104.      * 将指定元素添加到线性表的末位
  105.      * @param element 元素
  106.      */
  107.     public void add(Element element) {
  109.         add(size, element);
  110.     }
  112.     /**
  113.      * 在指定位序上插入一个新的元素
  114.      * @param index 位序
  115.      * @param element 元素
  116.      */
  117.     public void add(int index, Element element) {
  119.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  120.         if (!(index >= 0 && index <= size)) {
  122.             // 位置不合法
  123.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  124.         }
  125.         // 末端插入
  126.         if (index == size) {
  128.             // 原尾部节点
  129.             Node<Element> last = tail;
  130.             // 新插入节点
  131.             Node<Element> newNode = new Node<>();
  132.             // 设置节点数据
  133.             newNode.data = element;
  134.             // 尾部节点变为新插入的节点
  135.             tail = newNode;
  136.             if (last == null) {
  138.                 // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
  139.                 header = newNode;
  140.             } else {
  142.                 // 设置原尾部节点的下一个节点为新插入的节点
  143.                 last.next = newNode;
  144.             }
  145.         }
  146.         // 头部或者中间插入
  147.         else {
  149.             // 获取 index-1 位序的节点
  150.             Node<Element> beforeNode = findNode(index-1);
  151.             // 获取原 index 位序的节点
  152.             Node<Element> originNode = findNode(index);
  153.             // 新插入节点
  154.             Node<Element> newNode = new Node<>();
  155.             // 设置节点数据
  156.             newNode.data = element;
  157.             // 设置新插入的节点的 next 为原节点
  158.             newNode.next = originNode;
  159.             if (beforeNode == null) {
  161.                 // 表明在头部插入节点
  162.                 header = newNode;
  163.             } else {
  165.                 // 表明在中间插入节点，则原 index-1 位置上的节点 next 设置为当前插入的节点
  166.                 beforeNode.next = newNode;
  167.             }
  168.         }
  169.         // 线性表大小加一
  170.         size++;
  171.     }
  173.     /**
  174.      * 删除指定位序的元素
  175.      * @param index 位序
  176.      */
  177.     public void remove(int index) {
  179.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  180.         if (!(index >= 0 && index < size)) {
  182.             // 位置不合法
  183.             throw new RuntimeException("Index: "+index+", Size: "+size);
  184.         }
  185.         // 获取 index-1 (前)位序的节点
  186.         Node<Element> beforeNode = findNode(index-1);
  187.         // 获取原 index+1 (后)位序的节点
  188.         Node<Element> afterNode = findNode(index+1);
  189.         if (beforeNode == null) {
  191.             // 如果删除的节点没有前驱节点，则说明删除的节点为头节点，则后置节点设置为头节点
  192.             header = afterNode;
  193.         } else {
  195.             // 删除的节点不是头节点，前置节点的下一个节点设置为后置节点
  196.             beforeNode.next = afterNode;
  197.         }
  198.         // 线性表大小减一
  199.         size--;
  200.     }
  202.     /**
  203.      * 从列表中删除指定元素的第一个出现（如果存在）
  204.      * @param element 元素
  205.      */
  206.     public void remove(Element element) {
  208.         int index = indexOf(element);
  209.         if (index != -1) {
  211.             remove(index);
  212.         }
  213.     }
  215.     /**
  216.      * 用指定的元素替换此列表中指定位置的元素
  217.      * @param index 指定位置
  218.      * @param element 指定元素
  219.      * @return 替换掉的元素
  220.      */
  221.     public Element set(int index, Element element) {
  223.         // 校验坐标是否合法
  224.         if (index >= size || index < 0) {
  226.             // 位置不合法
  227.             throw new RuntimeException("Index: "+index+", Size: "+size);
  228.         }
  229.         Node<Element> node = findNode(index);
  230.         Element oldElement = node.data;
  231.         // 重置数据
  232.         node.data = element;
  233.         return oldElement;
  234.     }
  236.     /**
  237.      * 判断指定元素是否在线性表中
  238.      * @return true 表示存在 false 表示不存在
  239.      */
  240.     public boolean contains(Element element) {
  242.         return indexOf(element) != -1;
  243.     }
  245.     /**
  246.      * 获取线性表大小
  247.      * @return 线性表大小
  248.      */
  249.     public int size() {
  251.         return size;
  252.     }
  254.     /**
  255.      * 判断当前线性表是否为空
  256.      * @return true 表示为空 false 表示不为空
  257.      */
  258.     public boolean isEmpty() {
  260.         return size == 0;
  261.     }
  263.     /**
  264.      * 返回当前线性表的字符串表示
  265.      * @return 线性表字符串表示
  266.      */
  267.     public String toString() {
  269.         StringBuilder str = new StringBuilder("[");
  270.         if (size > 0) {
  272.             // 遍历链表
  273.             Node<Element> cursor = header;
  274.             str.append(cursor.data);
  275.             while (cursor.next != null) {
  277.                 cursor = cursor.next;
  278.                 str.append(",").append(cursor.data);
  279.             }
  280.         }
  281.         str.append("]");
  282.         return str.toString();
  283.     }
  284. }
2. 双链表实现

之前提到过 LinkedList 的底层就是使用双向链表实现的，与单向链表不同，双向链表的节点不仅需要记录后继节点，也需要记录前驱节点，实现方法基本类似。

（1）初始化

因为要记录前驱节点，所以相比单向链表多了一个 prev 属性来记录前驱节点，其余属性与单向链表相同

  1. public class DoubleLinkList<Element> {
  4.     // 头节点
  5.     private Node<Element> header;
  6.     // 尾节点
  7.     private Node<Element> tail;
  8.     // 线性表的长度
  9.     private int size;
  11.     /**
  12.      * 节点
  13.      * @param <Element> 数据元素类型
  14.      */
  15.     public static class Node<Element> {
  18.         // 数据元素
  19.         private Element data;
  20.         // 前驱节点
  21.         private Node<Element> prev;
  22.         // 后继节点
  23.         private Node<Element> next;
  25.     }
  27.     /**
  28.      * 无参构造方法
  29.      */
  30.     public DoubleLinkList() {
  32.         // 初始化线性表的长度
  33.         size = 0;
  34.     }
  36. }

（2）根据位序 index，查询相应的元素

与单链表的逻辑差不都，都是对链表进行遍历，但是双链表不仅可以正向遍历，也能反向遍历

  1. /**
  2.      * 根据位序 index，返回相应元素
  3.      * @param index 为序
  4.      * @return 元素
  5.      */
  6.     public Element get(int index) {
  8.         if (index >= size) {
  10.             // 位序大于线性表的大小
  11.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  12.         }
  13.         // 返回指定位序节点下的数据元素
  14.         return findNode(index).data;
  15.     }
  18.     // 通过位序获取节点
  19.     public Node<Element> findNode(int index) {
  21.         // 二分法查找
  22.         Node<Element> node;
  23.         if (index < (size >> 1)) {
  25.             node = header;
  26.             for (int i = 0; i < index; i++) {
  28.                 node = node.next;
  29.             }
  30.         } else {
  32.             node = tail;
  33.             for (int i = size -1; i > index; i--) {
  35.                 node = node.prev;
  36.             }
  37.         }
  38.         return node;
  39.     }

（3）通过元素 Element，查找所在位置

  1. /**
  2.      * 通过元素 Element，查找所在位置
  3.      * @param element 元素
  4.      * @return 所在位置
  5.      */
  6.     public int indexOf(Object element) {
  8.         int index = 0;
  9.         Node<Element> node = header;
  10.         if (element == null) {
  12.             // 遍历链表
  13.             do {
  15.                 if (node.data == null)
  16.                     return index;
  17.                 index++;
  18.                 node = node.next;
  19.             } while (node != null);
  20.         } else {
  22.             // 遍历链表
  23.             do {
  25.                 if (element.equals(node.data))
  26.                     return index;
  27.                 index++;
  28.                 node = node.next;
  29.             } while (node != null);
  30.         }
  31.         return -1;
  32.     }

（4）在指定位序 index 上插入一个新的元素

在双向链表中添加元素也可分为三种情况：

  • 情况一：末位插入，新插入的节点 NodeX 成为链表的尾节点，新节点的前驱节点 prev 指向原链表的尾节点Node... ，原链表的尾节点 Node... 的后驱节点 next 指向新插入的节点 NodeX

cb11ca9c7cdb4dc7a1d4825be84421c0.png

  • 情况二：头部插入，新插入的节点 NodeX 变成了头节点，所以 NodeX 的 Next 要指向原头节点 Node1，NodeX 的 prev 为 null

3c4379c731b848158ee9960818ba23f4.png

  • 情况三：中间插入，新插入的节点 NodeX 的前驱节点为原指定节点的前驱节点，原指定位置上的节点变成了新插入节点的后驱节点了

83cc1a7ab2ed410a954cd48e921fa291.png

  1. /**
  2.      * 将指定元素添加到线性表的末位
  3.      * @param element 元素
  4.      */
  5.     public void add(Element element) {
  7.         add(size, element);
  8.     }
  10.     /**
  11.      * 在指定位序上插入一个新的元素
  12.      * @param index 位序
  13.      * @param element 元素
  14.      */
  15.     public void add(int index, Element element) {
  17.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  18.         if (!(index >= 0 && index <= size)) {
  20.             // 位置不合法
  21.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  22.         }
  23.         // 末端插入
  24.         if (index == size) {
  26.             // 原尾部节点
  27.             Node<Element> last = tail;
  28.             // 新插入节点
  29.             Node<Element> newNode = new Node<>();
  30.             // 设置节点数据
  31.             newNode.data = element;
  32.             // 尾部节点变为新插入的节点
  33.             tail = newNode;
  34.             if (last == null) {
  36.                 // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
  37.                 header = newNode;
  38.             } else {
  40.                 // 设置原尾部节点的下一个节点为新插入的节点
  41.                 last.next = newNode;
  42.                 // 设置新插入节点的前驱节点为原尾部节点
  43.                 newNode.prev = last;
  44.             }
  45.         }
  46.         // 头部或者中间插入
  47.         else {
  49.             // 获取原 index 位序的节点
  50.             Node<Element> originNode = findNode(index);
  51.             // 新插入节点
  52.             Node<Element> newNode = new Node<>();
  53.             // 设置节点数据
  54.             newNode.data = element;
  55.             // 设置新插入的节点的 next 为原节点
  56.             newNode.next = originNode;
  57.             // 新插入节点的 prev 为原节点的前驱节点
  58.             newNode.prev = originNode.prev;
  59.             // 判断原节点是否为头节点
  60.             if (originNode.prev == null) {
  62.                 // 是，则表明在头部插入节点，新节点成为头节点
  63.                 header = newNode;
  64.             } else {
  66.                 // 原节点的前驱节点的后继节点为新插入的节点
  67.                 originNode.prev.next = newNode;
  68.             }
  69.             // 原节点的前驱节点设置为新插入的节点
  70.             originNode.prev = newNode;
  71.         }
  72.         // 线性表大小加一
  73.         size++;
  74.     }

（5）删除指定位序 index 的元素

删除链表头部节点也需要分为两种情况去看待：

  • 集合大小 = 1 时，此时删除第一个节点之后，链表就没有节点了，所以链表的头节点和尾节点都需要设置为 null
  • 集合大小 > 1 时，原头节点 Node1 的后驱节点 Next 指向 null，而它的下一个节点 Node2 变成头节点，Node2 的 前驱节点 Pre 指向 null

93cd514d5ccf43e7819954b531b3774d.png

  1. /**
  2.      * 删除指定位序的元素
  3.      * @param index 位序
  4.      */
  5.     public void remove(int index) {
  7.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  8.         if (!(index >= 0 && index < size)) {
  10.             // 位置不合法
  11.             throw new RuntimeException("Index: "+index+", Size: "+size);
  12.         }
  13.         // 获取 index 处的节点
  14.         Node<Element> node = findNode(index);
  15.         // 获取该节点的前驱节点
  16.         Node<Element> prevNode = node.prev;
  17.         // 获取该节点的后继节点
  18.         Node<Element> nextNode = node.next;
  19.         if (prevNode == null) {
  21.             // 如果前驱节点为空，则说明删除的节点为头节点，则后继节点设置为头节点
  22.             header = nextNode;
  23.             nextNode.prev = null;
  24.         } else if (nextNode == null) {
  26.             // 如果后继节点为空，则说明删除的节点为尾节点，则前驱节点设置为为节点
  27.             tail = node.prev;
  28.             prevNode.next = null;
  29.         } else {
  31.             // 删除的节点不是头节点，则原前驱节点的下一个节点设置为原后继节点
  32.             prevNode.next = nextNode;
  33.             // 原后继节点的上一个节点设置为原前驱节点
  34.             nextNode.prev = prevNode;
  35.         }
  36.         // 线性表大小减一
  37.         size--;
  38.     }
  40.     /**
  41.      * 从列表中删除指定元素的第一个出现（如果存在）
  42.      * @param element 元素
  43.      */
  44.     public void remove(Element element) {
  46.         int index = indexOf(element);
  47.         if (index != -1) {
  49.             remove(index);
  50.         }
  51.     }

（6）获取线性表的长度

  1. /**
  2.      * 获取线性表大小
  3.      * @return 线性表大小
  4.      */
  5.     public int size() {
  7.         return size;
  8.     }

完整代码示例：

  1. public class DoubleLinkList<Element> {
  4.     // 头节点
  5.     private Node<Element> header;
  6.     // 尾节点
  7.     private Node<Element> tail;
  8.     // 线性表的长度
  9.     private int size;
  11.     /**
  12.      * 节点
  13.      * @param <Element> 数据元素类型
  14.      */
  15.     public static class Node<Element> {
  18.         // 数据元素
  19.         private Element data;
  20.         // 前驱节点
  21.         private Node<Element> prev;
  22.         // 后继节点
  23.         private Node<Element> next;
  25.     }
  27.     /**
  28.      * 无参构造方法
  29.      */
  30.     public DoubleLinkList() {
  32.         // 初始化线性表的长度
  33.         size = 0;
  34.     }
  36.     /**
  37.      * 根据位序 index，返回相应元素
  38.      * @param index 为序
  39.      * @return 元素
  40.      */
  41.     public Element get(int index) {
  43.         if (index >= size) {
  45.             // 位序大于线性表的大小
  46.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  47.         }
  48.         // 返回指定位序节点下的数据元素
  49.         return findNode(index).data;
  50.     }
  53.     // 通过位序获取节点
  54.     public Node<Element> findNode(int index) {
  56.         // 二分法查找
  57.         Node<Element> node;
  58.         if (index < (size >> 1)) {
  60.             node = header;
  61.             for (int i = 0; i < index; i++) {
  63.                 node = node.next;
  64.             }
  65.         } else {
  67.             node = tail;
  68.             for (int i = size -1; i > index; i--) {
  70.                 node = node.prev;
  71.             }
  72.         }
  73.         return node;
  74.     }
  76.     /**
  77.      * 通过元素 Element，查找所在位置
  78.      * @param element 元素
  79.      * @return 所在位置
  80.      */
  81.     public int indexOf(Object element) {
  83.         int index = 0;
  84.         Node<Element> node = header;
  85.         if (element == null) {
  87.             // 遍历链表
  88.             do {
  90.                 if (node.data == null)
  91.                     return index;
  92.                 index++;
  93.                 node = node.next;
  94.             } while (node != null);
  95.         } else {
  97.             // 遍历链表
  98.             do {
  100.                 if (element.equals(node.data))
  101.                     return index;
  102.                 index++;
  103.                 node = node.next;
  104.             } while (node != null);
  105.         }
  106.         return -1;
  107.     }
  109.     /**
  110.      * 将指定元素添加到线性表的末位
  111.      * @param element 元素
  112.      */
  113.     public void add(Element element) {
  115.         add(size, element);
  116.     }
  118.     /**
  119.      * 在指定位序上插入一个新的元素
  120.      * @param index 位序
  121.      * @param element 元素
  122.      */
  123.     public void add(int index, Element element) {
  125.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  126.         if (!(index >= 0 && index <= size)) {
  128.             // 位置不合法
  129.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
  130.         }
  131.         // 末端插入
  132.         if (index == size) {
  134.             // 原尾部节点
  135.             Node<Element> last = tail;
  136.             // 新插入节点
  137.             Node<Element> newNode = new Node<>();
  138.             // 设置节点数据
  139.             newNode.data = element;
  140.             // 尾部节点变为新插入的节点
  141.             tail = newNode;
  142.             if (last == null) {
  144.                 // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
  145.                 header = newNode;
  146.             } else {
  148.                 // 设置原尾部节点的下一个节点为新插入的节点
  149.                 last.next = newNode;
  150.                 // 设置新插入节点的前驱节点为原尾部节点
  151.                 newNode.prev = last;
  152.             }
  153.         }
  154.         // 头部或者中间插入
  155.         else {
  157.             // 获取原 index 位序的节点
  158.             Node<Element> originNode = findNode(index);
  159.             // 新插入节点
  160.             Node<Element> newNode = new Node<>();
  161.             // 设置节点数据
  162.             newNode.data = element;
  163.             // 设置新插入的节点的 next 为原节点
  164.             newNode.next = originNode;
  165.             // 新插入节点的 prev 为原节点的前驱节点
  166.             newNode.prev = originNode.prev;
  167.             // 判断原节点是否为头节点
  168.             if (originNode.prev == null) {
  170.                 // 是，则表明在头部插入节点，新节点成为头节点
  171.                 header = newNode;
  172.             } else {
  174.                 // 原节点的前驱节点的后继节点为新插入的节点
  175.                 originNode.prev.next = newNode;
  176.             }
  177.             // 原节点的前驱节点设置为新插入的节点
  178.             originNode.prev = newNode;
  179.         }
  180.         // 线性表大小加一
  181.         size++;
  182.     }
  184.     /**
  185.      * 删除指定位序的元素
  186.      * @param index 位序
  187.      */
  188.     public void remove(int index) {
  190.         // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
  191.         if (!(index >= 0 && index < size)) {
  193.             // 位置不合法
  194.             throw new RuntimeException("Index: "+index+", Size: "+size);
  195.         }
  196.         // 获取 index 处的节点
  197.         Node<Element> node = findNode(index);
  198.         // 获取该节点的前驱节点
  199.         Node<Element> prevNode = node.prev;
  200.         // 获取该节点的后继节点
  201.         Node<Element> nextNode = node.next;
  202.         if (prevNode == null) {
  204.             // 如果前驱节点为空，则说明删除的节点为头节点，则后继节点设置为头节点
  205.             header = nextNode;
  206.             nextNode.prev = null;
  207.         } else if (nextNode == null) {
  209.             // 如果后继节点为空，则说明删除的节点为尾节点，则前驱节点设置为为节点
  210.             tail = node.prev;
  211.             prevNode.next = null;
  212.         } else {
  214.             // 删除的节点不是头节点，则原前驱节点的下一个节点设置为原后继节点
  215.             prevNode.next = nextNode;
  216.             // 原后继节点的上一个节点设置为原前驱节点
  217.             nextNode.prev = prevNode;
  218.         }
  219.         // 线性表大小减一
  220.         size--;
  221.     }
  223.     /**
  224.      * 从列表中删除指定元素的第一个出现（如果存在）
  225.      * @param element 元素
  226.      */
  227.     public void remove(Element element) {
  229.         int index = indexOf(element);
  230.         if (index != -1) {
  232.             remove(index);
  233.         }
  234.     }
  236.     /**
  237.      * 用指定的元素替换此列表中指定位置的元素
  238.      * @param index 指定位置
  239.      * @param element 指定元素
  240.      * @return 替换掉的元素
  241.      */
  242.     public Element set(int index, Element element) {
  244.         // 校验坐标是否合法
  245.         if (index >= size || index < 0) {
  247.             // 位置不合法
  248.             throw new RuntimeException("Index: "+index+", Size: "+size);
  249.         }
  250.         Node<Element> node = findNode(index);
  251.         Element oldElement = node.data;
  252.         // 重置数据
  253.         node.data = element;
  254.         return oldElement;
  255.     }
  257.     /**
  258.      * 判断指定元素是否在线性表中
  259.      * @return true 表示存在 false 表示不存在
  260.      */
  261.     public boolean contains(Element element) {
  263.         return indexOf(element) != -1;
  264.     }
  266.     /**
  267.      * 获取线性表大小
  268.      * @return 线性表大小
  269.      */
  270.     public int size() {
  272.         return size;
  273.     }
  275.     /**
  276.      * 判断当前线性表是否为空
  277.      * @return true 表示为空 false 表示不为空
  278.      */
  279.     public boolean isEmpty() {
  281.         return size == 0;
  282.     }
  284.     /**
  285.      * 返回当前线性表的字符串表示
  286.      * @return 线性表字符串表示
  287.      */
  288.     public String toString() {
  290.         StringBuilder str = new StringBuilder("[");
  291.         if (size > 0) {
  293.             // 遍历链表
  294.             Node<Element> cursor = header;
  295.             str.append(cursor.data);
  296.             while (cursor.next != null) {
  298.                 cursor = cursor.next;
  299.                 str.append(",").append(cursor.data);
  300.             }
  301.         }
  302.         str.append("]");
  303.         return str.toString();
  304.     }
  305. }

上篇：第一章、绪论

发表评论

表情：
评论列表 （有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读