数据结构学习笔记2

每天进步一点点！开篇先聊两句，对于数据结构这本书，笔者其实已经快看完了，谦虚点说，其实挺简单的，哈哈……大家千万不要认为数据结构难，而且笔者还会结合代码来直观感受一下。这一篇记录一下笔者对线性表的一些理解。书中说一个线性表是n个具有相同特性的数据元素的有限序列。按照Java的说法，那就是同一类对象排列在一起组成的集合。

如上图所示，线性表有两种存储方式，一种是顺序存储，我们管它叫顺序表；另一种是链式存储，链式存储又细分为单链表、双链表、循环链表和静态链表，这些概念忘了不要紧，下面我们通过代码来逐个分析一下。仔细分析一下上图，我们是不是可以做一下抽象：把线性表抽象成一个接口，顺序表，单链表，双链表，循环链表，静态链表是线性表接口的实现。按照这个思路，我们来尝试实现一下。

2.顺序表：顺序存储，用一组地址连续的存储单元依次存储线性表的数据元素。通常用数组来描述顺序存储结构。我们在类中定义一个Object数组，为顺序表分配数组的长度capacity为100，并定义线性表的当前长度length，初始长度为0。

2.1初始化的时候，我们为存储元素的数组分配默认空间。2.2既然顺序存储是使用数组来实现的，那么顺序表也就自然而然的具备了数组的优点：存取数据非常方便。通过方法我们也可以看出来，存储的时候只需将对象赋值给对应下表的元素。

取出的时候，直接根据下标就可以直接取出元素，存取的时间复杂度为O(1)（注意：数组是下标是从0开始的）。

2.3下面再让我们看一下插入和删除方法。插入的时候，需要将插入位置坐标以后的元素依次向后移动（写着写着笔者发现几乎每一个都要判断index是否越界，于是抽取出判断index的方法）

删除的时候，将对应的位置坐标以后的元素依次向前移动，最后一个元素删除即可。