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

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

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

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

--------------------

上篇：[第一章、绪论][Link 1]

## 第二章 线性结构 ##

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

--------------------

### 2.1 多项式表示 ###

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

![在这里插入图片描述][069614a603c541aab115eb70b5c6bdd2.png_pic_center]

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

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

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

*  多项式项数  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  
表示成：  
![在这里插入图片描述][44c2f8fa908f40c1a1683574ae139045.png_pic_center]

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

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

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 ，可以很简单的使用如下数组来表示

![在这里插入图片描述][e38439d9fea6434a94979113646865d3.png]

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

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

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

public class Node {
        
    
        private int coef;
        private int expon;
        private Node next;
    
        public Node(int coef,int expon) {
        
            this.coef = coef;
            this.expon = expon;
        }
    }

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 这两个多项式用指针表示如图所示：

![在这里插入图片描述][1d920105f9f741eaab4f732757d2dfd6.png]

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

--------------------

### 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\}> \\;|\\; a\_\{i\}, \\; a\_\{i+1\} \\in D, \\; i=0,...,n-2 \\right \\\} r=\{ <ai,ai\+1>∣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 线性表的顺序存储实现 ####

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

![在这里插入图片描述][bc423d036d5b44e18f6f558b67fdd9b3.png]

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

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

public class ArrLinearList<Element> {
        
    
    }

（1）初始化

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

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

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

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

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

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

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

/**
         * 通过元素 Element，查找所在位置
         * @param element 元素
         * @return 所在位置
         */
        public int indexOf(Object element) {
        
            if (element == null) {
        
                // 遍历数组
                for (int i = 0; i < size; i++) {
        
                    if (data[i] == null)
                        return i;
                }
            } else {
        
                for (int i = 0; i < size; i++) {
        
                    if (element.equals(data[i]))
                        return i;
                }
            }
            return -1;
        }

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

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

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

![在这里插入图片描述][72a8488c4a1d4d67b02d659c570b2ec4.png_pic_center]

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

![在这里插入图片描述][df331f1a33a141d1ae0dcd5b2f33eeaa.png]

/**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 如果插入元素的坐标大于线性表的大小
            if (index > size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 判断当前线性表的大小是否等于容量大小
            if (size == data.length) {
        
                // 如果插入当前元素后线性表的大小大于容器的大小，则进行扩容
                ensureCapacity();
            }
            // 判断插入位置是否小于线性表长度(头部或者中间插入)
            if (index < size) {
        
                // 先将线性表位于 index 以及之后的元素都往后挪一位
                for (int i = size; i > index; i--) {
        
                    data[i] = data[i-1];
                }
            }
            // 在 index 位序上插入元素
            data[index] = element;
            // 线性表大小加一
            size++;
        }
    
        /**
         * 自动扩容方法
         */
        public void ensureCapacity() {
        
            // 新容量的大小是原容量大小的 1.5 倍
            int newCapacity = data.length + (data.length >> 1);
            // 创建新数组
            Object[] newDate = new Object[newCapacity];
            // 将原数组中的内容复制到新数组中
            for (int i = 0; i < data.length; i++) {
        
                newDate[i] = data[i];
            }
            // 将线性表存放数据的数组指向新的数组
            data = newDate;
        }

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

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

![在这里插入图片描述][549fa8a632034457bced85ce438a494e.png_pic_center]

/**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 如果删除元素的坐标大于等于或者小于线性表的大小
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 判断删除的元素是否为末端元素
            if (index == size-1) {
        
                // 删除的是最后一个元素
                data[index] = null;
            } else {
        
                for (int i = index; i < size; i++) {
        
                    data[i] = data[i+1];
                }
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }

（6）获取线性表的长度

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

/**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }

完整代码示例：

public class ArrLinearList<Element> {
        
    
        // 数据元素
        private Object[] data;
        // 线性表大小
        private int size;
        // 初始容量大小
        private static final int INIT_CAPACITY = 10;
    
        /**
         * 无参构造方法
         */
        public ArrLinearList() {
        
            init(INIT_CAPACITY);
        }
    
        /**
         * 有参构造方法
         * @param capacity 指定设置容量大小
         */
        public ArrLinearList(int capacity) {
        
            // 如果指定的容量大小小于或等于零，则初始化容量大小为默认容量大小
            if (capacity <= 0) {
        
                capacity = INIT_CAPACITY;
            }
            // 初始化
            init(capacity);
        }
    
        /**
         * 初始化
         * @param maxSize 数组的最大容量
         */
        private void init(int maxSize) {
        
            // 创建一个大小为 10 的 Object 数组
            data = new Object[maxSize];
            // 初始化时线性表的大小为 0
            size = 0;
        }
    
        /**
         * 根据位序 index，返回相应元素
         * @param index 为序
         * @return 元素
         */
        // 压制不安全的类型转换的警告
        @SuppressWarnings("unchecked")
        public Element get(int index) {
        
            // 校验坐标是否合法
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            return (Element) data[index];
        }
    
        /**
         * 通过元素 Element，查找所在位置
         * @param element 元素
         * @return 所在位置
         */
        public int indexOf(Object element) {
        
            if (element == null) {
        
                // 遍历数组
                for (int i = 0; i < size; i++) {
        
                    if (data[i] == null)
                        return i;
                }
            } else {
        
                for (int i = 0; i < size; i++) {
        
                    if (element.equals(data[i]))
                        return i;
                }
            }
            return -1;
        }
    
        /**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 如果插入元素的坐标大于线性表的大小
            if (index > size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 判断当前线性表的大小是否等于容量大小
            if (size == data.length) {
        
                // 如果插入当前元素后线性表的大小大于容器的大小，则进行扩容
                ensureCapacity();
            }
            // 判断插入位置是否小于线性表长度(头部或者中间插入)
            if (index < size) {
        
                // 先将线性表位于 index 以及之后的元素都往后挪一位
                for (int i = size; i > index; i--) {
        
                    data[i] = data[i-1];
                }
            }
            // 在 index 位序上插入元素
            data[index] = element;
            // 线性表大小加一
            size++;
        }
    
        /**
         * 自动扩容方法
         */
        public void ensureCapacity() {
        
            // 新容量的大小是原容量大小的 1.5 倍
            int newCapacity = data.length + (data.length >> 1);
            // 创建新数组
            Object[] newDate = new Object[newCapacity];
            // 将原数组中的内容复制到新数组中
            for (int i = 0; i < data.length; i++) {
        
                newDate[i] = data[i];
            }
            // 将线性表存放数据的数组指向新的数组
            data = newDate;
        }
    
        /**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 如果删除元素的坐标大于等于或者小于线性表的大小
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 判断删除的元素是否为末端元素
            if (index == size-1) {
        
                // 删除的是最后一个元素
                data[index] = null;
            } else {
        
                for (int i = index; i < size; i++) {
        
                    data[i] = data[i+1];
                }
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }
    
        /**
         * 用指定的元素替换此列表中指定位置的元素
         * @param index 指定位置
         * @param element 指定元素
         * @return 替换掉的元素
         */
        @SuppressWarnings("unchecked")
        public Element set(int index, Element element) {
        
            // 校验坐标是否合法
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            Element oldElement =(Element) data[index];
            data[index] = element;
            return oldElement;
        }
    
        /**
         * 判断指定元素是否在线性表中
         * @return true 表示存在 false 表示不存在
         */
        public boolean contains(Element element) {
        
            return indexOf(element) != -1;
        }
    
        /**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }
    
        /**
         * 判断当前线性表是否为空
         * @return true 表示为空 false 表示不为空
         */
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        /**
         * 返回当前线性表的字符串表示
         * @return 线性表字符串表示
         */
        public String toString() {
        
           StringBuilder str = new StringBuilder("[");
            for (int i = 0; i < size-1; i++) {
        
                str.append(this.data[i]).append(",");
            }
            if (size > 0) {
        
                str.append(this.data[size - 1]);
            }
            str.append("]");
            return str.toString();
        }
    }

--------------------

#### 2.3.2 线性表的链式存储实现 ####

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

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

![在这里插入图片描述][8ec123c556bc4a5abe08fda33f608f74.png]

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

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

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

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

public class LinkLinearList<Element> {
        
    
    }

--------------------

##### 1. 单链表实现 #####

（1）初始化

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

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

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

/**
         * 根据位序 index，返回相应元素
         * @param index 为序
         * @return 元素
         */
        public Element get(int index) {
        
            if (index >= size) {
        
                // 位序大于线性表的大小
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 返回指定位序节点下的数据元素
            return findNode(index).data;
        }
    
        // 通过位序获取节点
        public Node<Element> findNode(int index) {
        
            // 目标节点
            Node<Element> target = null;
            // 遍历链表（可采用二分法进行优化）
            Node<Element> node = header;
            for (int i = 0; i < size; i++) {
        
                if (i == index) {
        
                    target = node;
                    break;
                }
                node = node.next;
            }
            // 返回对应节点
            return target;
        }

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

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

/**
         * 通过元素 Element，查找所在位置
         * @param element 元素
         * @return 所在位置
         */
        public int indexOf(Object element) {
        
            int index = 0;
            Node<Element> node = header;
            if (element == null) {
        
                // 遍历链表
                do {
        
                    if (node.data == null)
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            } else {
        
                // 遍历链表
                do {
        
                    if (element.equals(node.data))
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            }
            return -1;
        }

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

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

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

![在这里插入图片描述][cb60aa5a6df749668b399766746b8f07.png]

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

![在这里插入图片描述][40ec84d791a8419b8137e46b43871952.png]

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

![在这里插入图片描述][99a5b64325494b46abd09928631028a1.png]

/**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index <= size)) {
        
                // 位置不合法
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 末端插入
            if (index == size) {
        
                // 原尾部节点
                Node<Element> last = tail;
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 尾部节点变为新插入的节点
                tail = newNode;
                if (last == null) {
        
                    // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
                    header = newNode;
                } else {
        
                    // 设置原尾部节点的下一个节点为新插入的节点
                    last.next = newNode;
                }
            }
            // 头部或者中间插入
            else {
        
                // 获取 index-1 位序的节点
                Node<Element> beforeNode = findNode(index-1);
                // 获取原 index 位序的节点
                Node<Element> originNode = findNode(index);
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 设置新插入的节点的 next 为原节点
                newNode.next = originNode;
                if (beforeNode == null) {
        
                    // 表明在头部插入节点
                    header = newNode;
                } else {
        
                    // 表明在中间插入节点，则原 index-1 位置上的节点 next 设置为当前插入的节点
                    beforeNode.next = newNode;
                }
            }
            // 线性表大小加一
            size++;
        }

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

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

/**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index < size)) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 获取 index-1 (前)位序的节点
            Node<Element> beforeNode = findNode(index-1);
            // 获取原 index+1 (后)位序的节点
            Node<Element> afterNode = findNode(index+1);
            if (beforeNode == null) {
        
                // 如果删除的节点没有前驱节点，则说明删除的节点为头节点，则后置节点设置为头节点
                header = afterNode;
            } else {
        
                // 删除的节点不是头节点，前置节点的下一个节点设置为后置节点
                beforeNode.next = afterNode;
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }

（6）获取线性表的长度

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

/**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }

完整代码示例：

public class LinkLinearList<Element> {
        
    
        // 头节点
        private Node<Element> header;
        // 尾节点
        private Node<Element> tail;
        // 线性表的长度
        private int size;
    
        /**
         * 节点
         * @param <Element> 数据元素类型
         */
        public static class Node<Element> {
        
    
            // 数据元素
            private Element data;
            // 后继节点
            private Node<Element> next;
    
        }
    
        /**
         * 无参构造方法
         */
        public LinkLinearList() {
        
            // 初始化线性表的长度
            size = 0;
        }
    
        /**
         * 根据位序 index，返回相应元素
         * @param index 为序
         * @return 元素
         */
        public Element get(int index) {
        
            if (index >= size) {
        
                // 位序大于线性表的大小
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 返回指定位序节点下的数据元素
            return findNode(index).data;
        }
    
        // 通过位序获取节点
        public Node<Element> findNode(int index) {
        
            // 目标节点
            Node<Element> target = null;
            // 遍历链表（可采用二分法进行优化）
            Node<Element> node = header;
            for (int i = 0; i < size; i++) {
        
                if (i == index) {
        
                    target = node;
                    break;
                }
                node = node.next;
            }
            // 返回对应节点
            return target;
        }
    
        /**
         * 通过元素 Element，查找所在位置
         * @param element 元素
         * @return 所在位置
         */
        public int indexOf(Object element) {
        
            int index = 0;
            Node<Element> node = header;
            if (element == null) {
        
                // 遍历链表
                do {
        
                    if (node.data == null)
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            } else {
        
                // 遍历链表
                do {
        
                    if (element.equals(node.data))
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            }
            return -1;
        }
    
        /**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index <= size)) {
        
                // 位置不合法
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 末端插入
            if (index == size) {
        
                // 原尾部节点
                Node<Element> last = tail;
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 尾部节点变为新插入的节点
                tail = newNode;
                if (last == null) {
        
                    // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
                    header = newNode;
                } else {
        
                    // 设置原尾部节点的下一个节点为新插入的节点
                    last.next = newNode;
                }
            }
            // 头部或者中间插入
            else {
        
                // 获取 index-1 位序的节点
                Node<Element> beforeNode = findNode(index-1);
                // 获取原 index 位序的节点
                Node<Element> originNode = findNode(index);
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 设置新插入的节点的 next 为原节点
                newNode.next = originNode;
                if (beforeNode == null) {
        
                    // 表明在头部插入节点
                    header = newNode;
                } else {
        
                    // 表明在中间插入节点，则原 index-1 位置上的节点 next 设置为当前插入的节点
                    beforeNode.next = newNode;
                }
            }
            // 线性表大小加一
            size++;
        }
    
        /**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index < size)) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 获取 index-1 (前)位序的节点
            Node<Element> beforeNode = findNode(index-1);
            // 获取原 index+1 (后)位序的节点
            Node<Element> afterNode = findNode(index+1);
            if (beforeNode == null) {
        
                // 如果删除的节点没有前驱节点，则说明删除的节点为头节点，则后置节点设置为头节点
                header = afterNode;
            } else {
        
                // 删除的节点不是头节点，前置节点的下一个节点设置为后置节点
                beforeNode.next = afterNode;
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }
    
        /**
         * 用指定的元素替换此列表中指定位置的元素
         * @param index 指定位置
         * @param element 指定元素
         * @return 替换掉的元素
         */
        public Element set(int index, Element element) {
        
            // 校验坐标是否合法
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            Node<Element> node = findNode(index);
            Element oldElement = node.data;
            // 重置数据
            node.data = element;
            return oldElement;
        }
    
        /**
         * 判断指定元素是否在线性表中
         * @return true 表示存在 false 表示不存在
         */
        public boolean contains(Element element) {
        
            return indexOf(element) != -1;
        }
    
        /**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }
    
        /**
         * 判断当前线性表是否为空
         * @return true 表示为空 false 表示不为空
         */
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        /**
         * 返回当前线性表的字符串表示
         * @return 线性表字符串表示
         */
        public String toString() {
        
            StringBuilder str = new StringBuilder("[");
            if (size > 0) {
        
                // 遍历链表
                Node<Element> cursor = header;
                str.append(cursor.data);
                while (cursor.next != null) {
        
                    cursor = cursor.next;
                    str.append(",").append(cursor.data);
                }
            }
            str.append("]");
            return str.toString();
        }
    }

--------------------

##### 2. 双链表实现 #####

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

（1）初始化

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

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

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

/**
         * 根据位序 index，返回相应元素
         * @param index 为序
         * @return 元素
         */
        public Element get(int index) {
        
            if (index >= size) {
        
                // 位序大于线性表的大小
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 返回指定位序节点下的数据元素
            return findNode(index).data;
        }
    
    
        // 通过位序获取节点
        public Node<Element> findNode(int index) {
        
            // 二分法查找
            Node<Element> node;
            if (index < (size >> 1)) {
        
                node = header;
                for (int i = 0; i < index; i++) {
        
                    node = node.next;
                }
            } else {
        
                node = tail;
                for (int i = size -1; i > index; i--) {
        
                    node = node.prev;
                }
            }
            return node;
        }

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

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

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

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

![cb11ca9c7cdb4dc7a1d4825be84421c0.png][]

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

![3c4379c731b848158ee9960818ba23f4.png][]

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

![83cc1a7ab2ed410a954cd48e921fa291.png][]

/**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index <= size)) {
        
                // 位置不合法
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 末端插入
            if (index == size) {
        
                // 原尾部节点
                Node<Element> last = tail;
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 尾部节点变为新插入的节点
                tail = newNode;
                if (last == null) {
        
                    // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
                    header = newNode;
                } else {
        
                    // 设置原尾部节点的下一个节点为新插入的节点
                    last.next = newNode;
                    // 设置新插入节点的前驱节点为原尾部节点
                    newNode.prev = last;
                }
            }
            // 头部或者中间插入
            else {
        
                // 获取原 index 位序的节点
                Node<Element> originNode = findNode(index);
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 设置新插入的节点的 next 为原节点
                newNode.next = originNode;
                // 新插入节点的 prev 为原节点的前驱节点
                newNode.prev = originNode.prev;
                // 判断原节点是否为头节点
                if (originNode.prev == null) {
        
                    // 是，则表明在头部插入节点，新节点成为头节点
                    header = newNode;
                } else {
        
                    // 原节点的前驱节点的后继节点为新插入的节点
                    originNode.prev.next = newNode;
                }
                // 原节点的前驱节点设置为新插入的节点
                originNode.prev = newNode;
            }
            // 线性表大小加一
            size++;
        }

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

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

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

![93cd514d5ccf43e7819954b531b3774d.png][]

/**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index < size)) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 获取 index 处的节点
            Node<Element> node = findNode(index);
            // 获取该节点的前驱节点
            Node<Element> prevNode = node.prev;
            // 获取该节点的后继节点
            Node<Element> nextNode = node.next;
            if (prevNode == null) {
        
                // 如果前驱节点为空，则说明删除的节点为头节点，则后继节点设置为头节点
                header = nextNode;
                nextNode.prev = null;
            } else if (nextNode == null) {
        
                // 如果后继节点为空，则说明删除的节点为尾节点，则前驱节点设置为为节点
                tail = node.prev;
                prevNode.next = null;
            } else {
        
                // 删除的节点不是头节点，则原前驱节点的下一个节点设置为原后继节点
                prevNode.next = nextNode;
                // 原后继节点的上一个节点设置为原前驱节点
                nextNode.prev = prevNode;
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }

（6）获取线性表的长度

/**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }

完整代码示例：

public class DoubleLinkList<Element> {
        
    
        // 头节点
        private Node<Element> header;
        // 尾节点
        private Node<Element> tail;
        // 线性表的长度
        private int size;
    
        /**
         * 节点
         * @param <Element> 数据元素类型
         */
        public static class Node<Element> {
        
    
            // 数据元素
            private Element data;
            // 前驱节点
            private Node<Element> prev;
            // 后继节点
            private Node<Element> next;
    
        }
    
        /**
         * 无参构造方法
         */
        public DoubleLinkList() {
        
            // 初始化线性表的长度
            size = 0;
        }
    
        /**
         * 根据位序 index，返回相应元素
         * @param index 为序
         * @return 元素
         */
        public Element get(int index) {
        
            if (index >= size) {
        
                // 位序大于线性表的大小
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 返回指定位序节点下的数据元素
            return findNode(index).data;
        }
    
    
        // 通过位序获取节点
        public Node<Element> findNode(int index) {
        
            // 二分法查找
            Node<Element> node;
            if (index < (size >> 1)) {
        
                node = header;
                for (int i = 0; i < index; i++) {
        
                    node = node.next;
                }
            } else {
        
                node = tail;
                for (int i = size -1; i > index; i--) {
        
                    node = node.prev;
                }
            }
            return node;
        }
    
        /**
         * 通过元素 Element，查找所在位置
         * @param element 元素
         * @return 所在位置
         */
        public int indexOf(Object element) {
        
            int index = 0;
            Node<Element> node = header;
            if (element == null) {
        
                // 遍历链表
                do {
        
                    if (node.data == null)
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            } else {
        
                // 遍历链表
                do {
        
                    if (element.equals(node.data))
                        return index;
                    index++;
                    node = node.next;
                } while (node != null);
            }
            return -1;
        }
    
        /**
         * 将指定元素添加到线性表的末位
         * @param element 元素
         */
        public void add(Element element) {
        
            add(size, element);
        }
    
        /**
         * 在指定位序上插入一个新的元素
         * @param index 位序
         * @param element 元素
         */
        public void add(int index, Element element) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index <= size)) {
        
                // 位置不合法
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
            // 末端插入
            if (index == size) {
        
                // 原尾部节点
                Node<Element> last = tail;
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 尾部节点变为新插入的节点
                tail = newNode;
                if (last == null) {
        
                    // 如果原尾部节点为空，则表示当前链表没有元素，新插入的节点既是头节点也是尾节点
                    header = newNode;
                } else {
        
                    // 设置原尾部节点的下一个节点为新插入的节点
                    last.next = newNode;
                    // 设置新插入节点的前驱节点为原尾部节点
                    newNode.prev = last;
                }
            }
            // 头部或者中间插入
            else {
        
                // 获取原 index 位序的节点
                Node<Element> originNode = findNode(index);
                // 新插入节点
                Node<Element> newNode = new Node<>();
                // 设置节点数据
                newNode.data = element;
                // 设置新插入的节点的 next 为原节点
                newNode.next = originNode;
                // 新插入节点的 prev 为原节点的前驱节点
                newNode.prev = originNode.prev;
                // 判断原节点是否为头节点
                if (originNode.prev == null) {
        
                    // 是，则表明在头部插入节点，新节点成为头节点
                    header = newNode;
                } else {
        
                    // 原节点的前驱节点的后继节点为新插入的节点
                    originNode.prev.next = newNode;
                }
                // 原节点的前驱节点设置为新插入的节点
                originNode.prev = newNode;
            }
            // 线性表大小加一
            size++;
        }
    
        /**
         * 删除指定位序的元素
         * @param index 位序
         */
        public void remove(int index) {
        
            // 校验插入位置是否合法：位置范围必须在 0 <= index <= size 这个区间内
            if (!(index >= 0 && index < size)) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            // 获取 index 处的节点
            Node<Element> node = findNode(index);
            // 获取该节点的前驱节点
            Node<Element> prevNode = node.prev;
            // 获取该节点的后继节点
            Node<Element> nextNode = node.next;
            if (prevNode == null) {
        
                // 如果前驱节点为空，则说明删除的节点为头节点，则后继节点设置为头节点
                header = nextNode;
                nextNode.prev = null;
            } else if (nextNode == null) {
        
                // 如果后继节点为空，则说明删除的节点为尾节点，则前驱节点设置为为节点
                tail = node.prev;
                prevNode.next = null;
            } else {
        
                // 删除的节点不是头节点，则原前驱节点的下一个节点设置为原后继节点
                prevNode.next = nextNode;
                // 原后继节点的上一个节点设置为原前驱节点
                nextNode.prev = prevNode;
            }
            // 线性表大小减一
            size--;
        }
    
        /**
         * 从列表中删除指定元素的第一个出现（如果存在）
         * @param element 元素
         */
        public void remove(Element element) {
        
            int index = indexOf(element);
            if (index != -1) {
        
                remove(index);
            }
        }
    
        /**
         * 用指定的元素替换此列表中指定位置的元素
         * @param index 指定位置
         * @param element 指定元素
         * @return 替换掉的元素
         */
        public Element set(int index, Element element) {
        
            // 校验坐标是否合法
            if (index >= size || index < 0) {
        
                // 位置不合法
                throw new RuntimeException("Index: "+index+", Size: "+size);
            }
            Node<Element> node = findNode(index);
            Element oldElement = node.data;
            // 重置数据
            node.data = element;
            return oldElement;
        }
    
        /**
         * 判断指定元素是否在线性表中
         * @return true 表示存在 false 表示不存在
         */
        public boolean contains(Element element) {
        
            return indexOf(element) != -1;
        }
    
        /**
         * 获取线性表大小
         * @return 线性表大小
         */
        public int size() {
        
            return size;
        }
    
        /**
         * 判断当前线性表是否为空
         * @return true 表示为空 false 表示不为空
         */
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        /**
         * 返回当前线性表的字符串表示
         * @return 线性表字符串表示
         */
        public String toString() {
        
            StringBuilder str = new StringBuilder("[");
            if (size > 0) {
        
                // 遍历链表
                Node<Element> cursor = header;
                str.append(cursor.data);
                while (cursor.next != null) {
        
                    cursor = cursor.next;
                    str.append(",").append(cursor.data);
                }
            }
            str.append("]");
            return str.toString();
        }
    }

--------------------

上篇：[第一章、绪论][Link 1]

[Link 1]: https://blog.csdn.net/xhmico/article/details/123224653
[069614a603c541aab115eb70b5c6bdd2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/bde40ad993754857bdaca3dd30ecfefa.png
[44c2f8fa908f40c1a1683574ae139045.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/214ff3bd3ede453d81bc32fbac10e7ea.png
[e38439d9fea6434a94979113646865d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/7ecd6e945fc046bbbe89cc611f9e6f9d.png
[cfd10399c14b4507828752f423ed0ced.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/daace742a03743fbadf4d68034b8a4d5.png
[1d920105f9f741eaab4f732757d2dfd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/59b81b10c07e4b2d9d9c94c3dbf71b4a.png
[433bff81c082faad8a5200a2465e338b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d429f952626e4befbe5cc556be266fee.png
[bc423d036d5b44e18f6f558b67fdd9b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/609d8ef1336446efae05caf1745ebf19.png
[ArrayList-]: https://blog.csdn.net/xhmico/article/details/129879366
[72a8488c4a1d4d67b02d659c570b2ec4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/f66627f588ca437bbfac30cf7f921507.png
[df331f1a33a141d1ae0dcd5b2f33eeaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/2bf7d1d029584948a0017b55ffe041fc.png
[549fa8a632034457bced85ce438a494e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/3355a88976994929989b307ba83c3696.png
[8ec123c556bc4a5abe08fda33f608f74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/bf8ac5645bd04ae1a2ea8d0ddb81c11b.png
[d80ade5863dabd8a535399ed81f6fb5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/8feea5250f9d4937a6b1a6faf4c4561e.png
[acb9465d10cf8775a72f8f7932464ee5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/3efeb480ed664683a2e54797289b7425.png
[LinkedList-]: https://blog.csdn.net/xhmico/article/details/129909648
[cb60aa5a6df749668b399766746b8f07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/13679814514f46a8bd4fb3b1bf8242c7.png
[40ec84d791a8419b8137e46b43871952.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/2975e85701ab42dcb455b655e92a3c97.png
[99a5b64325494b46abd09928631028a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/17b5dd3a56904a7e9660f53a59e075d7.png
[50cc5c0ff15c4aacadd3820eb51cc3a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b276d32bcb524bd3bec3dd06a8c01dfd.png
[cb11ca9c7cdb4dc7a1d4825be84421c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/8409884cf4144e9885d769cfe94ed6dd.png
[3c4379c731b848158ee9960818ba23f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b8a0dd5feac047b786c09649c941960c.png
[83cc1a7ab2ed410a954cd48e921fa291.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/859b6b8271cb4830b1622ac78f6450e2.png
[93cd514d5ccf43e7819954b531b3774d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/3ed13dc062554066a5d210a11f263f5e.png