线性表

线性表定义

前言

1. 零个和多个数据元素的有限序列(线性表强调元素是有限的)。
2. 线性表强调元素之间是有顺序的。

注意

需要正确理解有序一词: 它是逻辑上有序而非是物理上有序。拿链表（线性表的链式存储结构）来说，在内存存储上是分散存储的，但通过指针维护元素逻辑顺序。 就是说多个元素则第一个无前驱，最后一个无后继。其他元素有且只有一个前驱和后继！

线性表存储结构分类

顺序存储结构

顺序存储结构用一段地址连续的存储单元依次存储线性表的数据元素。<br/>
数组就是线性表的顺序存储结构（内存地址连续）。

线性表的顺序存储示意图:

链表存储结构

链式存储结构内存地址并不连续，而是采用逻辑关联关系（指针）。你在内存什么位置不重要我逻辑上知道下一个是谁就行。

链式存储结构分类:

• 单链表存储结构
• 双向链表存储结构
• 静态链表存储结构
• 循环链表存储结构

总结

这一章泛泛认识下什么是线性表，线性表是一种有限且元素之间存在逻辑有序的数据结构。其中细分类又可分为:

• 顺序存储结构
• 链式存储结构

而对于顺序存储结构它逻辑和物理都是有序，当然链式就只有逻辑有序。
顺序存储结构因为内存地址连续，比如数组可通过索引直接搜索。时间复杂度就是O(1)，而链式存储结构就没有这个待遇了时间复杂度就是O(n)。