20230303 2.0. 数组和链表

数组

数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，用数组名和下标可以唯一地确定数组元素。

链表

链表是一种重要的基础数据结构，也是实现 复杂数据结构 的重要手段。它不按照线性的顺序存储数据，而是由若干个同一结构类型的“结点”依次串接而成的，即每一个结点里保存着下一个结点的地址（指针）。

链表又分 单向链表 ，双向链表 以及 循环链表 等。

单向链表

结构

使用结构的嵌套来定义单向链表结点的数据类型

@Data
public class Node {
    private Object data;
    private Node next;
}

常见操作

1. 链表的建立

2. 插入结点

3. 删除结点

4. 遍历

双向链表

@Data
public class DNode {
    private Object data;
    private DNode next;

    private DNode previous;
}

如果将双向链表最后一个单元的Next指针指向链表的第一个单元，而第一个单元的Previous指针指向链表的最后一个单元，这样构成的链表称为 双向循环链表 。

双向链表的插入、删除和遍历基本思路与单向链表相同，但需要同时考虑前后两个指针

例题

给定一个单链表L，请设计函数Reverse将链表L就地逆转，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素……