[数据结构与算法]-基本数据结构表及Java中有关表的常用方法

一.引言

记得上大二的时候，我们开始学习《数据结构》这门课。记得那本书长这个样子。

当时学习的时候，印象最深刻的就是在各种数据结构中，定义了很多方法，比如在List中定义了add,,等各种方法，但却没有给出实现。当时还一直纳闷，为啥这书只给了方法没有给里面具体实现的代码呢（可能当时老师解释过，不过因为学的时候稀里糊涂，可能就没听到）？

后来才知道，数据结构是一种抽象模型，具体的操作是不给出实现方法的（实际上也无法给出），需要开发者自行用合适的算法去实现相应的功能。这就好比告诉你一辆车需要有轮胎、底盘、发动机等，具体轮胎多大、底盘多高、发动机如何制造，这些要根据不同的车型不同的适用环境来针对性的制造。

二.抽象数据类型

抽象数据类型( data type,

ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象；在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。

在Java中，Java提供给开发者一些ADT的实现，并适当隐藏了其中的细节。开发者只需要调用API中提供的方法即可使用这些ADT操作。当然了，根据场景的不同需要，我们也可以对实现细节进行修改，来满足特殊的需要。

对于每种ADT，实际上并没有规定要求各种ADT必须要有哪些操作。ADT就是个抽象的概念，具体的处理和结构调整取决于程序设计者或者开发者。

通过阅读Java中各种ADT的实现源码，有助于我们在学习编程的过程中理解原理，同时也能学习到语言设计者缜密是编程思维。通过自主动手实践，完成ADT的实现，更有助于我们理解数据结构和编程思想，对日后的开发是有极大的帮助的。

三.表ADT 3.1数组形式

a.数组本身的容量是固定的，但在Java中，我们不需要考虑表的大小，例如。这是因为在我们需要的时候，Java自动帮我们对数组进行扩容（一般是双倍扩容）。

b.列表的遍历的时间复杂度为O(N)，查找操作为O(1)。

c.删除和插入操作在某些情况存在昂贵的开销。如果插入或删除位置0的元素，那么这将会导致后面的元素依次后移一位或者迁移一位，时间复杂度为O(N)。当然了，这是最坏的情况。如果在末端插入或者删除元素，则时间复杂度为O(1)。所以，平均来看，这两种操作都需要移动列表一半的元素，需要线性时间。

d.所以如果需要频繁查找元素，则使用数组形式的表。如果要经常插入或删除数据，则可以用另一种数据结构实现表的功能——链表（ list）。

3.2链表形式

a.链表由一系列节点组成，这些节点在内存中不一定是相连的。每个节点包含元素内容以及指向该元素后继元素的链(link)，一般称为next链。最后一个节点的next链指向null。

b.链表是用引用的形式，将各个元素连城一串。就像是寻宝游戏，从第一个线索开始，每个线索提示下一条线索。理论上，线索可以是无限的，及链表形式的表不需要考虑容量的扩容，只要内存足够大。

c.遍历链表的时间复杂度为O(N)，这和数组形式的表是一样的。查找操作的花费为O(N)，因为对于链表来讲，查找需要遍历链表来实现。不过这个复杂度是保守的，实际上，(1)、(2)、(3)……可以通过一次扫描就都查找出来。

d.插入和删除操作可以通过修改next引动来实现，不需要挪动任何元素。如图所示。

e.注意，单链表的插入和删除在没有拿到相关节点之前，我们需要遍历找到要操作的位置，所以此时时间复杂度为O(N)。如果我们已经拿到了相关节点，则插入删除的时间复杂度为O(1)。（一般资料里都只说O(1)，但是别忘了在没有拿到节点之前，是遍历找到该节点的。）

f.为了提高单链表的操作效率，一般采用双链表（ list）方式来实现表，即让每个节点持有一个指向它在表中的前驱节点的链。

四.Java API中的表

在类库中，Java语言包含一些普通数据结构的实现，该语言的这一部分通常叫做 API。表ADT是在 API中实现的数据结构之一。

1.接口

方法主要定义了以下方法。

继承了接口。实现了接口的那些类可以使用增强for循环。

2.接口

通过方法，返回一个对象，并将当前位置的概念在对象内部存储下来。

主要定义了以下方法。

3.List接口

根据前面我们提交的表的两种实现方式——数组和链表，Java中的和分别对应这两种实现方式。

4.接口

站在前人的肩膀上前行，感谢以下博客及文献的支持。