最近在复习数据结构中的线性表，下面总结一下顺序表和链表的区别。
1. 顺序表
线性表的顺序存储称为顺序表，顺序表使得逻辑地址连续的元素在物理地址上也连续。
1.1 存储结构
最常用的存储结构是一维数组。
一维数组可以是静态分配，例如：int arr[3]={1,2,3}。这种分配方式，数组的大小和空间是事先固定了，要避免查询修改数据时的访问越界和溢出问题。
一维数组也可以是动态分配，使用 new 和 delete 来实现动态内存分配和释放。在C++中，推荐使用标准模板库 vector 容器来动态存储线性表。（vector是一个动态数组，它可以自动调整大小，并且在插入和删除元素时会自动处理内存分配和释放。）
1.2 顺序表特点
顺序表最主要的特点是随机访问，即通过首地址和元素符号可在时间为O(1)内找到指定的元素。
顺序表存储密度高，每个节点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
1.3 顺序表应用场景
- 用于快速排序和归并排序的存储容器。
2.链表
链表通过指针链接的方式建立起元素之间的逻辑关系，对于逻辑上相邻的元素，物理地址之间不一定相邻。相比于顺序表的插入和存储需要移动大量元素，链表插入和删除元素不需要移动元素，只需要修改指针，但是也失去顺序表可随机存取的优点。
2.1 存储结构
实现链表的过程中，需要编程定义链表节点。常见的链表结构有以下几种：
- 单链表。单链表的链表节点存放元素自身信息和一个指向其后继节点的指针。通常而言，单链表会增加一个头节点（并不存储元素相关信息），以方便运算的实现。
- 双链表。双链表的链表节点存放元素自身信息、指向后继节点的指针、指向前驱节点的指针，
- 循环链表。循环链表是单链表的扩展，单链表最后一个节点的指针不是NULL，而改为指向头节点，整个链表形成一个环。
- 静态链表。借助数组来描述链式存储结构称为静态链表。所以静态链表也需要分配较大的连续空间（使用数组），并且插入和删除不需要移动元素。
