数据结构之【动态数组】

1. 线性表

概念：线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表有：数组、链表、栈、队列、字符串……

特点：

1. 保存在这个结构中的元素都是相同的数据类型。
2. 元素之间线性排列，元素之间在逻辑上是连续的。

线性表最大的特点是有明确的索引下标的概念。

2. 动态数组

动态数组产生的由来：

由于原始数组存在定长问题，因此需要将原始数组进行扩充，将原始数组封装到一个类中，让他具备可扩展的能力。

对使用者而言，无需关心数组的长度问题，提供给用户的是一个动态数组，用户只需要使用提供的数组进行增删改查即可，无需关心数组越界问题。

本质：将原始的数组封装到类中，对用户淡化数组长度的概念，当长度不够时，内部进行扩容操作。

动态数组=基本数组封装在类中+对外提供一系列的方便进行增删改查的方法。

（1） 为什么定义接口（定义线性表接口Seqlist）？

定义线性表的规范：一个类能称之为是线性表的子类，应该具备类似的行为（都是保存单个元素的集合，集合中元素的类型都是相同的，元素之间逻辑上连续）

定义接口的好处：可以以非常低的成本来更换具体的子类。

举例说明：

如果有一个动态数组类，实现增删改查方法，同时也有一个新的链表类，也具有增删改查的方法。对用户来说，则需要了解各个类的具体的增删改查方法，使用成本很高。

但是定义Seqlist线性表接口，数组、链表、字符串、栈、队列，只要是线性表接口的子类，均具有相同的方法，用户只需要了解接口中的方法类型，更换子类0成本。