线性结构：链表

谁践踏了优雅 2022-10-23 14:26 139阅读 0赞

### 目录 ###

*  第一章 单向链表介绍
 *  第二章 单向链表实现
 *   *  2.01、定义链表的结点类
     *  2.02、定义链表的属性值
     *  2.03、初始化各个属性值
     *  2.04、获取链表当前大小
     *  2.05、判断链表是否为空
     *  2.06、检查下标是否合法
     *  2.07、连接链表两个结点
     *  2.08、释放链表指定结点
     *  2.09、返回链表最后结点
     *  2.10、返回链表首个结点
     *  2.11、获取指定位置结点
     *  2.12、获取位置之前结点
     *  2.13、链表尾后添加数据
     *  2.14、链表头后添加数据
     *  2.15、指定位置添加数据
     *  2.16、删除指定位置结点
     *  2.17、删除链表首个结点
     *  2.18、删除链表最后结点
     *  2.19、输出链表所有结点
     *  2.20、反转链表所有结点
     *  2.21、清空链表所有结点
     *  2.22、顺序查找数据首次出现位置
     *  2.23、逆序查找数据首次出现位置
 *  第三章 双向链表介绍
 *  第四章 双向链表实现
 *   *  4.01、且看代码如此多娇
     *  4.02、获取位置之前结点
     *  4.03、删除链表最后结点
     *  4.04、逆序查找数据首次出现位置
 *  第五章 单向循环链表介绍
 *  第六章 单向循环链表实现
 *   *  6.01、定义链表的结点类
     *  6.02、定义链表的属性值
     *  6.03、初始化各个属性值
     *  6.04、获取链表当前大小
     *  6.05、判断链表是否为空
     *  6.06、检查下标是否合法
     *  6.07、连接链表两个结点
     *  6.08、释放链表指定结点
     *  6.09、返回链表最后结点
     *  6.10、返回链表首个结点
     *  6.11、获取指定位置结点
     *  6.12、获取位置之前结点
     *  6.13、链表尾后添加数据
     *  6.14、链表头后添加数据
     *  6.15、指定位置添加数据
     *  6.16、删除指定位置结点
     *  6.17、删除链表首个结点
     *  6.18、删除链表最后结点
     *  6.19、输出链表所有结点
     *  6.20、反转链表所有结点
     *  6.21、清空链表所有结点
     *  6.22、顺序查找数据首次出现位置
     *  6.23、逆序查找数据首次出现位置
 *  第七章 双向循环链表介绍
 *  第八章 双向循环链表实现
 *   *  8.01、再看代码如此多娇
     *  8.02、获取位置之前结点
     *  8.03、删除链表最后结点
     *  8.04、逆序查找数据首次出现位置

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

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 单向链表介绍 #

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

单向链表（单链表）是链表的一种，其特点是链表的连接方向是单向的，对链表的访问要从头部开始顺序读取，`head`指针指向第一个结点又称为头结点，而终止于最后一个指向`null`的结点。链表的头结点的数据域不存储数据，而头结点的指针域指向第一个真正存储数据的结点。这里为了方便操作，我又增加了一个`last`结点，这个结点就是为了指向最后一个结点，节约操作时间，提升查询性能。

![8a3288ee73c89d181bf816e2c69e16d4.png][]

# 第二章 单向链表实现 #

## 2.01、定义链表的结点类 ##

/** * 单向链表实现代码 */
    public class SinglyLinkedList<E> { 
        //定义结点类
        public class Node { 
            E data;     //代表结点数据
            Node next;  //指向下个结点
    
            public Node(E data) { 
                this.data = data;
            }
    
            @Override
            public String toString() { 
                return "Node{data=" + data + "}";
            }
        }
    
        //下节内容写这...
    }

## 2.02、定义链表的属性值 ##

/** * 单向链表实现代码 */
    public class SinglyLinkedList<E> { 
        //省略以上代码...
    
        private Node head;  //代表链表头部
        private Node last;  //代表链表尾部
        private int size;   //代表链表长度
    
        //下节内容写这...
    }

## 2.03、初始化各个属性值 ##

![542f5a969b4f8ab97a0b583b69839106.png][]

/** * 单向链表实现代码 */
    public class SinglyLinkedList<E> { 
        //省略以上代码...
    
        public SinglyLinkedList() { 
            //头结点用于其他结点的连接，头结点的下标我们定义为-1
            this.head = new Node(null);
            //尾结点初始默认指向头结点，这样我们在添加的时候方便
            this.last = head;
            this.size = 0;
        }
    
        //下节内容写这...
    }

## 2.04、获取链表当前大小 ##

//获取链表当前大小
    public int size() { 
        return size;
    }

## 2.05、判断链表是否为空 ##

//判断链表是否为空
    public boolean isEmpty() { 
        return size == 0;
    }

## 2.06、检查下标是否合法 ##

//检查下标是否合法
    public void checkIndex(int index) { 
        if (index < 0 || (size - 1) < index) { 
            throw new IndexOutOfBoundsException("链表下标越界异常，请检查链表的下标！");
        }
    }

## 2.07、连接链表两个结点 ##

//连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) { 
        if (prevNode != null) { 
            prevNode.next = nextNode;
        }
    }

## 2.08、释放链表指定结点 ##

//释放链表指定结点
    public void releaseNode(Node node) { 
        if (node != null) { 
            node.data = null;
            node.next = null;
        }
    }

## 2.09、返回链表最后结点 ##

//返回链表最后结点
    public Node getLast() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return null;
        }
        //返回链表最后结点
        return last;
    }

## 2.10、返回链表首个结点 ##

//返回链表首个结点
    public Node getFirst() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return null;
        }
        //返回链表首个结点
        return head.next;
    }

## 2.11、获取指定位置结点 ##

//获取指定位置结点
    public Node getIndex(int index) { 
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < (index + 1); i++) { 
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }

## 2.12、获取位置之前结点 ##

//获取位置之前结点
    private Node getIndexPre(int index) { 
        //检查下标是否合法
        checkIndex(index);
        //获取位置之前结点
        Node preNode = head;
        for (int i = 0; i < index; i++) { 
            preNode = preNode.next;
        }
        //返回位置之前结点
        return preNode;
    }

## 2.13、链表尾后添加数据 ##

默认为空的时候，头指针`head`和尾指针`last`均指向头结点。

![542f5a969b4f8ab97a0b583b69839106.png][]

添加数据的时候，我们直接向`last`指向结点后追加结点即可。

![e0dda085eff0f3535476d59835ea82ea.png][]

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

**方法实现：**

//链表尾后添加数据（需要考虑last指向问题）
    public void addLast(E e) { 
        //获取旧的尾结点
        Node oldLast = last;
        //创建新的尾结点
        Node newLast = new Node(e);
        //旧新两结点连接
        connectNode(oldLast, newLast);
        //修改last指向
        last = newLast;
        //使链表长度加一
        size++;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：3
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=张三}
    Node{ data=李四}
    Node{ data=王五}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=张三}
    链表的尾结点：Node{ data=王五}

## 2.14、链表头后添加数据 ##

**方法实现：**

//链表头后添加数据（不用考虑last指向问题）
    public void addFirst(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            addLast(e);
        } else { 
            //获取首个结点
            Node firNode = head.next;
            //创建新的结点
            Node newNode = new Node(e);
            //三个结点连接
            connectNode(head, newNode);
            connectNode(newNode, firNode);
            //链表长度加一
            size++;
        }
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addFirst("张三");
            linkedList.addFirst("李四");
            linkedList.addFirst("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：3
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=王五}
    Node{ data=李四}
    Node{ data=张三}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=王五}
    链表的尾结点：Node{ data=张三}

## 2.15、指定位置添加数据 ##

**方法实现：**

//指定位置添加数据（不用考虑last指向问题）
    public void addIndex(int index, E e) { 
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //当前链表长度加一
        size++;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.addIndex(0, "张三长辈");
            linkedList.addIndex(linkedList.size() - 1, "王五长辈");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：5
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=张三长辈}
    Node{ data=张三}
    Node{ data=李四}
    Node{ data=王五长辈}
    Node{ data=王五}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=张三长辈}
    链表的尾结点：Node{ data=王五}

## 2.16、删除指定位置结点 ##

**方法实现：**

//删除指定位置结点（需要考虑last指向问题）
    public void removeIndex(int index) { 
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //修改last的指向
        if (curNode == last) { 
            last = preNode;
        }
        //删除指定位置结点
        connectNode(preNode, nexNode);
        //释放链表指定结点
        releaseNode(curNode);
        //当前链表长度减一
        size--;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeIndex(0);
            linkedList.removeIndex(linkedList.size() - 1);
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：1
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=李四}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=李四}
    链表的尾结点：Node{ data=李四}

## 2.17、删除链表首个结点 ##

**方法实现：**

//删除链表首个结点（不用考虑last指向问题）
    public void removeFirst() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeFirst();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：2
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=李四}
    Node{ data=王五}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=李四}
    链表的尾结点：Node{ data=王五}

## 2.18、删除链表最后结点 ##

**方法实现：**

//删除链表最后结点（不用考虑last指向问题）
    public void removeLast() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //删除链表最后结点
        removeIndex(size - 1);
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeLast();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：2
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=张三}
    Node{ data=李四}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=张三}
    链表的尾结点：Node{ data=李四}

## 2.19、输出链表所有结点 ##

**方法实现：**

//输出链表所有结点（不用考虑last指向问题）
    public void show() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //遍历链表所有结点（除头结点）
        Node curNode = head.next;
        while (curNode != null) { 
            System.out.println(curNode);
            curNode = curNode.next;
        }
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 2.20、反转链表所有结点 ##

**方法实现：**

//反转链表所有结点（需要考虑last指向问题）
    public void reverse() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //创建一个新头结点
        Node newHead = new Node(null);
        //获取链表的首结点
        Node oldFirst = head.next;
        //遍历链表所有结点（除头结点）
        Node newFirst;
        Node tmpNode;
        Node curNode = oldFirst;
        while (curNode != null) { 
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取链表新头首个结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        }
        //老头换新头首结点
        head.next = newHead.next;
        //修改last的指向
        last = oldFirst;
        //释放临时新头结点
        releaseNode(newHead);
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.reverse();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 2.21、清空链表所有结点 ##

**方法实现：**

//清空链表所有结点（需要考虑last指向问题）
    public void clear() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //遍历链表所有结点（含头结点）
        Node tmpNode;
        Node curNode = head;
        while (curNode != null) { 
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        }
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.clear();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

==========打印链表基本信息：
    链表结点个数：0
    链表是否为空：true
    ==========打印链表所有结点：
    ==========打印链表首尾结点：
    链表的头结点：null
    链表的尾结点：null

## 2.22、顺序查找数据首次出现位置 ##

**方法实现：**

//顺序查找数据首次出现位置
    public int indexOf(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            return -1;
        }
        //判断对象是否为空
        if (e == null) { 
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = -1; i < size; i++) { 
            if (e.equals(curNode.data)) { 
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.indexOf("张三"));
            System.out.println(linkedList.indexOf("李四"));
            System.out.println(linkedList.indexOf("王五"));
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

0
    1
    2
    ==========打印链表基本信息：
    链表结点个数：3
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=张三}
    Node{ data=李四}
    Node{ data=王五}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=张三}
    链表的尾结点：Node{ data=王五}

## 2.23、逆序查找数据首次出现位置 ##

**方法实现：**

//逆序查找数据首次出现位置
    public int lastIndexOf(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            return -1;
        }
        //判断对象是否为空
        if (e == null) { 
            return -1;
        }
        //反转当前链表结点
        reverse();
        //获取指定位置结点
        int index = indexOf(e);
        //反转当前链表结点
        reverse();
        //返回数据指定位置
        return index;
    }

**方法测试：**

public class SinglyLinkedListTest { 
        public static void main(String[] args) { 
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.lastIndexOf("张三"));
            System.out.println(linkedList.lastIndexOf("李四"));
            System.out.println(linkedList.lastIndexOf("王五"));
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

2
    1
    0
    ==========打印链表基本信息：
    链表结点个数：3
    链表是否为空：false
    ==========打印链表所有结点：
    Node{ data=张三}
    Node{ data=李四}
    Node{ data=王五}
    ==========打印链表首尾结点：
    链表的头结点：Node{ data=张三}
    链表的尾结点：Node{ data=王五}

# 第三章 双向链表介绍 #

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据结点。  
![b5cf6ecd51365f4fee8773fd10b76b0b.png][]

# 第四章 双向链表实现 #

## 4.01、且看代码如此多娇 ##

我们已经学过了`单向链表`的设计和实现了，`双向链表`只需要在`单向链表`的基础上添加三行代码就能实现，你看神奇不神奇。

我们需要直接拷贝`SinglyLinkedList`为`DoublyLinkedList`，然后拷贝`SinglyLinkedListTest`为`DoublyLinkedListTest`，并修改相对应的构造方法名称。

第一处：修改节点类，添加`prev`指针域。

//定义结点类
    public class Node { 
        Node prev;  //指向上个结点 +
        E data;     //代表结点数据
        Node next;  //指向下个结点
    
        public Node(E data) { 
            this.data = data;
        }
    
        @Override
        public String toString() { 
            return "Node{data=" + data + "}";
        }
    }

第二处：修改连接处，添加指向上个结点。

//连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) { 
        if (prevNode != null) { 
            prevNode.next = nextNode;
        }
        if (nextNode != null) {          // +
            nextNode.prev = prevNode;   // +
        }                               // +
    }

第三处：修改释放处，添加释放`prev`指针域。

//释放链表指定结点
    public void releaseNode(Node node) { 
        if (node != null) { 
            node.prev = null;   // +
            node.data = null;
            node.next = null;
        }
    }

到此，`双向链表`的设计和实现就学完了，但是既然存在`双向链表`，那么肯定还有一些方法可以简化，接下来，我们需要对一些特殊的方法进行优化。

## 4.02、获取位置之前结点 ##

//获取位置之前结点
    private Node getIndexPre(int index) { 
        return getIndex(index).prev;
    }

## 4.03、删除链表最后结点 ##

//删除链表最后结点（需要考虑last指向问题）
    public void removeLast() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //获取链表最后节点
        Node lastNode = last;
        //删除链表最后结点
        Node prevNode = lastNode.prev;
        prevNode.next = null;
        //释放最后节点指向
        releaseNode(lastNode);
        //修改last的指向
        last = prevNode;
        //让链表的长度减一
        size--;
    }

## 4.04、逆序查找数据首次出现位置 ##

//逆序查找数据首次出现位置
    public int lastIndexOf(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            return -1;
        }
        //判断对象是否为空
        if (e == null) { 
            return -1;
        }
        //获取指定位置结点
        Node curNode = last;
        for (int i = 0; curNode != null; i++) { 
            if (e.equals(curNode.data)) { 
                return i;
            }
            curNode = curNode.prev;
        }
        //没有找到返回负一
        return -1;
    }

# 第五章 单向循环链表介绍 #

单向循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

![fbc5435a50b79631f5b1a37438d00dcf.png][]

# 第六章 单向循环链表实现 #

## 6.01、定义链表的结点类 ##

/** * 单向循环链表实现代码 */
    public class SinglyCircularLinkedList<E> { 
        //定义结点类
        public class Node { 
            E data;     //代表结点数据
            Node next;  //指向下个结点
    
            public Node(E data) { 
                this.data = data;
            }
    
            @Override
            public String toString() { 
                return "Node{data=" + data + "}";
            }
        }
    
        //下节内容写这...
    }

## 6.02、定义链表的属性值 ##

/** * 单向循环链表实现代码 */
    public class SinglyCircularLinkedList<E> { 
        //省略以上代码...
        
        private Node head;  //代表链表头部
        private Node last;  //代表链表尾部
        private int size;   //代表链表长度 
    
        //下节内容写这...
    }

## 6.03、初始化各个属性值 ##

/** * 单向链表实现代码 */
    public class SinglyLinkedList<E> { 
        //省略以上代码...
    
        public SinglyCircularLinkedList() { 
            //头结点应该指向第一个结点，现在没有，所以为null
            this.head = null;
            //尾结点应该指向最后的结点，现在没有，所以为null
            this.last = null;
            this.size = 0;
        }
    
        //下节内容写这...
    }

## 6.04、获取链表当前大小 ##

//获取链表当前大小
    public int size() { 
        return size;
    }

## 6.05、判断链表是否为空 ##

//判断链表是否为空
    public boolean isEmpty() { 
        return size == 0;
    }

## 6.06、检查下标是否合法 ##

## 6.07、连接链表两个结点 ##

//连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) { 
        if (prevNode != null) { 
            prevNode.next = nextNode;
        }
    }

## 6.08、释放链表指定结点 ##

//释放链表指定结点
    public void releaseNode(Node node) { 
        if (node != null) { 
            node.data = null;
            node.next = null;
        }
    }

## 6.09、返回链表最后结点 ##

## 6.10、返回链表首个结点 ##

//返回链表首个结点
    public Node getFirst() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return null;
        }
        //返回链表首个结点
        return head;
    }

## 6.11、获取指定位置结点 ##

//获取指定位置结点
    public Node getIndex(int index) { 
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < index; i++) { 
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }

## 6.12、获取位置之前结点 ##

//获取位置之前结点
    private Node getIndexPre(int index) { 
        //检查下标是否合法
        checkIndex(index);
        //获取首结点前结点
        if (index == 0) { 
            return last;
        }
        //获取位置之前结点
        Node preNode = head;
        for (int i = 0; i < (index - 1); i++) { 
            preNode = preNode.next;
        }
        //返回位置之前结点
        return preNode;
    }

## 6.13、链表尾后添加数据 ##

默认为空的时候，头指针`head`和尾指针`last`均指向`null`。

![000619a19f6e0c29b1877e13ebb22178.png][]

若是为空的时候，添加完数据应该自己指向自己，自我成环。

![40657f33d134cf0b8d46b837c4a8e6dc.png][]

非空添加数据，我们直接向`last`指向结点后追加结点即可。

![423794a736a7c41c0930b340d3993c64.png][]

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

**方法实现：**

//链表尾后添加数据
    public void addLast(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            //创建新的结点
            Node newNode = new Node(e);
            //修改头尾指向
            head = newNode;
            last = newNode;
            //自己连接自己
            connectNode(newNode, newNode);
        } else { 
            //获取last结点
            Node oldLast = last;
            //创建新的结点
            Node newLast = new Node(e);
            //修改last指向
            last = newLast;
            //头尾连接成环
            connectNode(oldLast, newLast);
            connectNode(newLast, head);
        }
        //链表链表长度加一
        size++;
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.14、链表头后添加数据 ##

**方法实现：**

//链表头后添加数据
    public void addFirst(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            addLast(e);
            return;
        } else { 
            //获取head结点
            Node oldHead = head;
            //创建新的结点
            Node newHead = new Node(e);
            //修改head指向
            head = newHead;
            //头尾连接成环
            connectNode(last, newHead);
            connectNode(newHead, oldHead);
        }
        //链表链表长度加一
        size++;
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addFirst("张三");
            linkedList.addFirst("李四");
            linkedList.addFirst("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.15、指定位置添加数据 ##

**方法实现：**

//指定位置添加数据
    public void addIndex(int index, E e) { 
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //修改head的指向
        if (curNode == head) { 
            head = newNode;
        }
        //当前链表长度加一
        size++;
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.addIndex(0, "张三长辈");
            linkedList.addIndex(linkedList.size() - 1, "王五长辈");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.16、删除指定位置结点 ##

**方法实现：**

//删除指定位置结点
    public void removeIndex(int index) { 
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //如果只有一个结点
        if (size == 1) { 
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else { 
            //修改head的指向
            if (curNode == head) { 
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) { 
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeIndex(0);
            linkedList.removeIndex(linkedList.size() - 1);
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.17、删除链表首个结点 ##

**方法实现：**

//删除链表首个结点
    public void removeFirst() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeFirst();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.18、删除链表最后结点 ##

**方法实现：**

//删除链表最后结点
    public void removeLast() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //删除链表最后结点
        removeIndex(size - 1);
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeLast();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            for (int i = 0; i < linkedList.size(); i++) { 
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.19、输出链表所有结点 ##

**方法实现：**

//输出链表所有结点
    public void show() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //遍历链表所有结点
        Node curNode = head;
        do { 
            System.out.println(curNode);
            curNode = curNode.next;
        } while (curNode != head);
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.20、反转链表所有结点 ##

**方法实现：**

//反转链表所有结点
    public void reverse() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //创建一个临时节点
        Node newHead = new Node(null);
        //循环遍历圆环结点
        Node newFirst;
        Node tmpNode;
        Node curNode = head;
        do { 
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取临时结点首结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        } while (curNode != head);
        //交换旧头尾指向
        tmpNode = head;
        head = last;
        last = tmpNode;
        //首尾相连成圆环
        connectNode(last, newHead.next);
        //释放新建临时节点
        releaseNode(newHead);
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.reverse();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.21、清空链表所有结点 ##

**方法实现：**

//清空链表所有结点
    public void clear() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //遍历链表所有结点
        Node tmpNode;
        Node curNode = head;
        do { 
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        } while (curNode != head);
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.clear();
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.22、顺序查找数据首次出现位置 ##

**方法实现：**

//顺序查找数据首次出现位置
    public int indexOf(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            return -1;
        }
        //判断对象是否为空
        if (e == null) { 
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < size; i++) { 
            if (e.equals(curNode.data)) { 
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.indexOf("张三"));
            System.out.println(linkedList.indexOf("李四"));
            System.out.println(linkedList.indexOf("王五"));
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

## 6.23、逆序查找数据首次出现位置 ##

**方法实现：**

**方法测试：**

public class SinglyCircularLinkedListTest { 
        public static void main(String[] args) { 
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.lastIndexOf("张三"));
            System.out.println(linkedList.lastIndexOf("李四"));
            System.out.println(linkedList.lastIndexOf("王五"));
    
            System.out.println("==========打印链表基本信息：");
            System.out.println("链表结点个数：" + linkedList.size());
            System.out.println("链表是否为空：" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点：");
            linkedList.show();
            System.out.println("==========打印链表首尾结点：");
            System.out.println("链表的头结点：" + linkedList.getFirst());
            System.out.println("链表的尾结点：" + linkedList.getLast());
        }
    }

**运行结果：**

# 第七章 双向循环链表介绍 #

双向循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，头结点的指针域指向最后一个结点，整个链表形成一个环。

![b74f8b7e15450cad12d71a88bfa23573.png][]

# 第八章 双向循环链表实现 #

## 8.01、再看代码如此多娇 ##

我们已经学过了`单向循环链表`的设计和实现了，`双向循环链表`只需要在`单向循环链表`的基础上添加三行代码就能实现，你看神奇不神奇。

我们需要直接拷贝`SinglyCircularLinkedList`为`DoublyCircularLinkedList`，然后拷贝`SinglyCircularLinkedListTest`为`DoublyCircularLinkedListTest`，并修改相对应的构造方法名称。

第一处：修改节点类，添加`prev`指针域。

第二处：修改连接处，添加指向上个结点。

第三处：修改释放处，添加释放`prev`指针域。

到此，`双向循环链表`的设计和实现就学完了，但是既然存在`双向循环链表`，那么肯定还有一些方法可以简化，接下来，我们需要对一些特殊的方法进行优化。

## 8.02、获取位置之前结点 ##

//获取位置之前结点
    private Node getIndexPre(int index) { 
        return getIndex(index).prev;
    }

## 8.03、删除链表最后结点 ##

//删除链表最后结点
    public void removeLast() { 
        //判断链表是否为空
        if (isEmpty()) { 
            return;
        }
        //获取位置之前结点
        Node preNode = last.prev;
        //获取指定位置结点
        Node curNode = last;
        //获取位置之后结点
        Node nexNode = last.next;
        //如果只有一个结点
        if (size == 1) { 
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else { 
            //修改head的指向
            if (curNode == head) { 
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) { 
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }

## 8.04、逆序查找数据首次出现位置 ##

//逆序查找数据首次出现位置
    public int lastIndexOf(E e) { 
        //判断链表是否为空
        if (isEmpty()) { 
            return -1;
        }
        //判断对象是否为空
        if (e == null) { 
            return -1;
        }
        //获取指定位置结点
        Node curNode = last;
        for (int i = 0; i < size; i++) { 
            if (e.equals(curNode.data)) { 
                return i;
            }
            curNode = curNode.prev;
        }
        //没有找到返回负一
        return -1;
    }

[8a3288ee73c89d181bf816e2c69e16d4.png]: /images/20221023/0558f2d5aaa0494a9bf13a61a9788ad7.png
[542f5a969b4f8ab97a0b583b69839106.png]: /images/20221023/3cd65ece621749bfbf4c5ac114f5500a.png
[e0dda085eff0f3535476d59835ea82ea.png]: /images/20221023/eefaeee7fae447f5b2b7fac8838856b7.png
[b5cf6ecd51365f4fee8773fd10b76b0b.png]: /images/20221023/1350af10459a4cfbbf1eb932e9772881.png
[fbc5435a50b79631f5b1a37438d00dcf.png]: /images/20221023/ae9ba0df8e794e9f9d090b42ec9ebf08.png
[000619a19f6e0c29b1877e13ebb22178.png]: /images/20221023/a3d25d48387947d283d2fb9f361960a0.png
[40657f33d134cf0b8d46b837c4a8e6dc.png]: /images/20221023/049a9084b73b431dac97fb62175e1f7d.png
[423794a736a7c41c0930b340d3993c64.png]: /images/20221023/c12e0e34235545858bf0855f77603d3f.png
[b74f8b7e15450cad12d71a88bfa23573.png]: /images/20221023/60a1933e732e4de28ddabb9c61aae3e8.png