[数组 array] 连续空间存储 与 [链表 linked list] 离散空间存储 是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式，两者的特点呈现出互补的特性。
数组 array#
[数组 array] 是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。数组的长度是不可变的。
插入和删除缺点：时间复杂度高 O (n)，丢失元素、内存浪费。
典型应用：随机访问、排序和搜索、查找表、机器学习、数据结构实现。
链表 linked list#
[链表 linked list] 是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过 “引用” 相连接。
引用记录了下一个节点的内存地址。链表的设计使得各个节点可以被分散存储在内存各处。
头节点，尾节点，尾节点指向的是” 空 “。
链表因为保存引用，所以比数组占用更多的内存空间。
// **单向**链表(singly linked list)
// **典型应用：栈与队列、哈希表、图**
class ListNode {
int val;
ListNode? next;
ListNode(int x) => val = x;
}
// **双向**链表(doubly linked list)
// **典型应用（快速查找前/后元素）：高级数据结构、浏览器历史、LRU 算法。**
class ListNode {
int val;
ListNode? next;
ListNode? prev;
ListNode(int x) => val = x;
}
// **环形**链表(circular linked list)
// 和双向链表一样，区别是首尾相接
// **典型应用（周期性操作）：时间片轮转调度算法、数据缓冲区。**
class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int x) => val = x;
}