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

本文欢迎转载，转载前请联系作者，经允许后方可转载。转载后请注明出处，谢谢！ http://blog.csdn.net/colton_null 作者：喝酒不骑马 Colton_Null from CSDN

一.引言

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

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

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

二.抽象数据类型

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

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

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

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

三.表ADT

• 表ADT，即列表在我们平日的开发中最为常见了。
• 表是由一系列按特定顺序排列的元素组成的。
• 表的实现主要有两种方式。一种是用数组实现，一种是用链表形式实现。

3.1数组形式

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

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

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

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

3.2链表形式

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

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

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

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


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

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

四.Java Collections API中的表

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

1.Collection接口

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

• size：返回集合中的项数。
• isEmpty：当且仅当集合的大小为0的时候返回true。
• contains：如果x在集合中，则返回true。（x是否属于该集合，Collection没有做规范，这需要具体实现类来决定规则）
• add：添加元素
• remove：删除元素

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

2.Iterator接口

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

主要定义了以下方法。

• next：每次执行都会调出集合当前位置元素的下一项。
• hasNext：如果存在下一项则返回true。
• remove：删除由next最新返回的项，执行后，不能再调用remove，直到对next再一次调用之后。

3.List接口

• get：根据索引获取元素
• set：替换索引上的元素
• add：添加元素到末位或者添加元素到索引位置
• remove：移除元素

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

4.ListIterator接口

• ListIterator继承了Iterator接口。
• 方法previous和hasPrevious可以完成从后向前遍历表。
• add方法是添加新元素到当前迭代器迭代的位置。
• set方式是改变被迭代器最后看到的值。

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

• 《数据结果与算法分析 机械工业出版社》