数据结构2

线性表

线性表：零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度。

线性表有以下几个特点

⑴ 序列——顺序性：元素具有线性顺序，第一个元素无前驱，最后一个元素无后继，其他每个元素有且仅有一个前驱和一个后继。
⑵ 有限——有限性：元素个数有限，在计算机中处理的对象都是有限的。
⑶ 相同类型——相同性：元素取自于同一个数据对象，这意味着每个元素占用相同数量的存储单元。
⑷ 元素类型不确定——抽象性：数据元素的类型是抽象的、不具体的，需要根据具体问题确定。

线性表的操作

建表（初始化）、求表长、查找、插入、删除

线性表包括顺序存储结构和链式存储结构两种，因此可以将线性表分为顺序表和链表两大类

顺序表的代表为ArrayList(源码解析传送门)

定义：线性表在顺序存储形式下构成的表。

线性表的顺序存储结构具备的两个特点

① 线性表中所有元素所占的存储空间是连续的；
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。

顺序存储结构的优缺点

优点：查询很快
缺点：插入和删除效率慢

链表的代表为LinkedList（源码传送门）

链式存储结构

链式存储结构是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。