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

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

文章插图
当时学习的时候，印象最深刻的就是在各种数据结构中，定义了很多方法，比如在List中定义了add,,等各种方法，但却没有给出实现。当时还一直纳闷，为啥这书只给了方法没有给里面具体实现的代码呢（可能当时老师解释过，不过因为学的时候稀里糊涂，可能就没听到）？
后来才知道，数据结构是一种抽象模型，具体的操作是不给出实现方法的（实际上也无法给出），需要开发者自行用合适的算法去实现相应的功能。这就好比告诉你一辆车需要有轮胎、底盘、发动机等，具体轮胎多大、底盘多高、发动机如何制造，这些要根据不同的车型不同的适用环境来针对性的制造。
二.抽象数据类型
抽象数据类型( data type,
ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象；在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。
在Java中，Java提供给开发者一些ADT的实现，并适当隐藏了其中的细节。开发者只需要调用API中提供的方法即可使用这些ADT操作。当然了，根据场景的不同需要，我们也可以对实现细节进行修改，来满足特殊的需要。
对于每种ADT，实际上并没有规定要求各种ADT必须要有哪些操作。ADT就是个抽象的概念，具体的处理和结构调整取决于程序设计者或者开发者。
【[数据结构与算法]-基本数据结构表及Java中有关表的常用方法】通过阅读Java中各种ADT的实现源码，有助于我们在学习编程的过程中理解原理，同时也能学习到语言设计者缜密是编程思维。通过自主动手实践，完成ADT的实现，更有助于我们理解数据结构和编程思想，对日后的开发是有极大的帮助的。
三.表ADT3.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）方式来实现表，即让每个节点持有一个指向它在表中的前驱节点的链。

文章插图

文章插图
四.JavaAPI中的表
在类库中，Java语言包含一些普通数据结构的实现，该语言的这一部分通常叫做 API 。表ADT是在 API中实现的数据结构之一。
1.接口
方法主要定义了以下方法。
继承了接口。实现了接口的那些类可以使用增强for循环。
2.接口
通过方法，返回一个对象，并将当前位置的概念在对象内部存储下来。
主要定义了以下方法。
3.List接口
根据前面我们提交的表的两种实现方式——数组和链表，Java中的和分别对应这两种实现方式。
4.接口
站在前人的肩膀上前行，感谢以下博客及文献的支持。