前言
本章讲解数据结构中第一个逻辑结构——线性表
方法
1.概念
通过前面的讨论，我们知道了数据结构的基本概念和研究方向，以及算法的基本概念。
接下来我们来学习第一个逻辑结构线性表，这也是数据结构中最为简单的一种逻辑结构。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
2.线性表的基本特征
1）相同的数据类型
在线性表中，存储的是相同的数据类型，这意味着每个元素占用着相同的存储空间，方便后续的查找。
2）序列（顺序性）
线性表的数据是具有顺序性的。除最后一个元素之外，均有唯一的后继(后件)，除第一个元素之外，均有唯一的前驱(前件)。
3）有限
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
3.线性表的逻辑结构
数据结构中的元素存在一对一的相互关系；
这个已经在之前的博客中做了介绍。
4.线性表的存储结构
1）顺序存储结构
特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址
优点：
- 节省存储空间，因为分配给数据的存储单元都用来存储数据，节点间的逻辑关系没有用额外的存储空间。
- 索引查找效率高，只需要知道表头的地址就可以知道线性表中其中一个元素（下标）的地址
缺点：
- 插入和删除需要移动数据，效率低
- 必须提前分配固定数量的存储空间，如果存储元素少，将导致空间浪费
接下来我们来探究其查找算法的时间复杂度
在Java中，我们可以通过如下代码查找线性表（顺序存储结构ArrayList）指定的数据:
package com.wondersgroup.training;
import java.util.ArrayList;
import java.util.List;
public class Welcome {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
//这里假定查找指定字符串“b”
for(int i=0;i<list.size();i++){
if("b".equals(list.get(i))){//基本语句
System.out.println("找到该元素");
}
}
}
}
第一步：找出算法的基本语句，很显然就是"b".equals(list.get(i));
第二步：算出该语句的时间频度，最坏的时间频度很显然是n，因为我们最多查找n次；
第三步：算出该算法时间频度的数量级，很显然也是n；
结论：该算法时间复杂度--> T(n) = O(n)
2）链式存储结构
特点：数据元素存储空间不连续。每个结点由数据域和指针域所构成，数据域用来存储该节点的数据，指针域用来指示下一个数据所在的地址。逻辑上相邻的节点物理上不必相邻。
优点：
- 插入、删除节点比较灵活，不需要移动节点，只需要改变节点的指针域即可。（前提先定位到该元素才行）
- 有元素才会分配节点空间，不会有闲置的节点
缺点：
- 存储空间消耗大，每个节点由数据域和指针域构成。
- 查找指定节点较慢，需要从头开始连续进行查找。
在Java中，使用链式存储结构的线性表的例子为LinkedList