线性表分成顺序表和链式表，而这两者是最基本的数据结构。

顺序表

一、什么是顺序表

顺序表，指的是由数组构成的内存中连续片段的数据存储方式

这个顺序体现在两点：

• 使用该结构时，具有明显的顺序感
• 在基本的实现上，使用了数组的结构，所以在实现上是在内存中连续的片段

二、有什么优缺点？

为什么数组的查找快

因为在创建数组的时候，会创建一个起始指针，而对于一般语言而言，数组确定，数组的元素的类型也已经确定。故每个元素占用的大小也已经确定。则：

假如我要取到 int 类型的第十个元素，即 起始地址 + 10 * 4，往该地址里面取数据即可存取

所以数组在读和改的操作上的复杂度是O(1)
在删和增的复杂度是O(2N)，涉及到一次读和一次写（差），所以避免使用数组来进行增删的操作

三、而顺序表在与查找排序上的算法有:

• 冒泡排序（衍生开来的希尔排序）
• 插入排序
• 选择排序
• 归并排序

链式表

一、链式表是什么

链式表是对于指针的灵活运用，链式表的关键其实是每个节点，最关键的是头节点。

链式表，一般分为单向链表、双向链表和循环链表。

首先，单向链表每个节点的元素如下
Node{
String data;
Node next;
}

单向链表的结构如下

单向链表 {
Node head;
int size;
}

值得一提的是，头指针一般会指向空指针，可以思考一下这样做的目的是什么？

防止在删除操作的时候会把头指针也删掉，而链表遍历的基础就是头指针，头指针删除，链表也无法继续新增及遍历

那么双向链表就是Node如下的结构
Node{
String data;
Node next;
Node prev;
}

而循环链表只是对于单向链表或双向链表的一种特殊实现

即，单链表的最后一个节点的next指向了头结点

那么，如何判断一个链表是循环链表

1. 最后一个元素的next指向了head
2. 同一个元素遍历到了两次

二、链式表的优缺点

每个节点除了存入关键信息以外，还会有一个 prev 和 next 指针，用于指向前一个和下一个元素

所以在一条链式表增删改查的复杂度是O(N)

三、链式表可以干什么

1. 做一些不确定元素总数的存储
2. 做一些经常需要增删操作的存储
3. 做一些通过next遍历的事情