【永利皇宫】JAVA数据结构之链表,Java数据结构和算法

  链表应该是继数组之后应用最广的通用存储结构,链表的机制灵活,用途广泛,适用于许多通用的数据库,也可取代数组作为其他的存储结构的基础,如栈和队列,除非需要频繁地通过下标访问数据,否则在很多使用数组的地方都可以使用链表来代替。

Q: 为什么要引入链表的概念?它是解决什么问题的?

A: 数组作为数据存储结构有一定的缺陷,在无序数组中,搜索是低效的;而在有序数组中,插入效率又很低;不管在哪一个数组中删除效率都很低;况且一个数组创建后,它的大小是不可改变的。

A: 在本篇中,我们将学习一种新的数据结构 ——
链表,它可以解决上面的一些问题,链表可能是继数组之后第二种使用最广泛的通用存储结构了。

  接下来本篇博文会讲解到单链表,双端链表,有序链表,双向链表,和有迭代器的链表。(迭代器是用来随机访问链表元素的一种方法)

Q: 结点?

A: 在链表中,每个数据项都被包含在“结点”中,可以使用Node,
或者Entry等名词来表示结点,本篇使用Entry来表示。每个Entry对象中包含一个对下一个结点引用的字段(通常叫做next),单链表中每个结点的结构图如下: 
永利皇宫 1 
定义单链表结点的类定义如下:

class Entry<E> {
    E mElement;
    Entry<E> mNext;

    public Entry(E element, Entry<E> next) {
        mElement = element;
        mNext = next;
    }
}

  链表的实现一般需要用到两个类,链表对象(包含对第一个链表节点的引用),链表节点(所有保存的数据,和对下一个链表节点的引用)。这种 方式可以称作自引式,由于其中包含一个和自己相同类型的字段(这里的字段是包含对下一个节点的引用,相当于一个内存地址,而不是具体的对象。若是简单类型这里就是实实在在的值,而不是内存地址)

Q: 单链表?

A: 构成链表的结点只有一个指向后继结点的指针域。

永利皇宫 2

Q: 单链表的Java实现?

A: 示例:SingleLinkedList.java

A: LinkedList类只包含一个数据项mHeader,叫做表头:即对链表中第一个节点的引用。它是唯一的链表需要维护的永久信息,用以定位所有其他的链接点。从mHeader出发,沿着链表通过每个结点的mNext字段,就可以找到其他的结点。

A: addFirst()方法 —— 作用是在表头插入一个新结点。 

永利皇宫 3

A: removeFirst()方法 ——
是addFirst()方法的逆操作,它通过把mHeader重新指向第二个结点,断开了和第一个结点的连接。 
永利皇宫 4 
在C++中,从链表取下一个结点后,需要考虑如何释放这个结点。它仍然在内存中的某个地方,但是现在没有任何指针指向它,将如何处理它呢?在Java中,垃圾回收(GC)将在未来的某个时刻销毁它,现在这不是程序员操心的工作。 
注意,removeFirst()方法假定链表不是空的,因此调用它之前,应该首先调用empty()方法核实这一点。

  我们要使用链表实现栈,就必须要实现1.在链表头插入一个数据项,2.在链表头删除一个数据项,3.遍历链表显示他的内容。

Q: 如何查找和删除指定的结点?

A: indexOf(Object)方法 ——
返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回
-1。

get(int)方法 —— 返回此列表中指定位置处的元素。

A: remove(Object) ——
从此列表中移除首次出现的指定元素(如果存在)。 
先搜索要删除的结点,如果找到了,必须把前一个结点和后一个结点连起来,知道前一个结点的唯一方法就是拥有一个对它的引用previous(每当current变量赋值为current.next之前,先把previous变量赋值为current)。 
永利皇宫 5

A: 示例: SingleLinkedList.java

  双端链表:与传统的链表非常相似,但他有一个新的特性:即链表有对最后一个链节点的引用,就像对第一个链节点的引用一样,这样就可以高效地在链表尾部加入一个元素,从而不用遍历整个链表。(注意和后面讨论到的双向链表进行区分)

Q: 双端链表?

A: 双端链表(double-ended list
)是在上边的单链表基础上加了一个表尾,即对最后一个结点的引用。如下图: 
永利皇宫 6

A: 对最后一个结点的引用允许像表头一样,在表尾直接插入一个结点。当然,仍然可以在普通的单链表的表尾插入一个结点,方法是遍历整个链表直到到达表尾,但是这种方法效率很低。

永利皇宫 7永利皇宫 8

Q: 双端链表的Java实现?

A: 示例: DoubleEndedList.java

A: DoubleEndedList有两个项,header和tailer,一个指向链表中的第一个结点,另一个指向最后一个结点。

A: 如果链表中只有一个结点,header和last都指向它。如果没有结点,两个都为null值。

A: 如果链表只有一个结点,删除时tailer必须被赋值为null。

A: addLast()方法 —— 在表尾插入一个新结点。

  双端链表的插入和删除和普通链表类似,插入的时候需要注意链表为空的情况,双端链表为空的时候需要将first和last都指向新的链节点,如果链表只有一个链节点那么从表头删除也是一种特殊情况,last必须被赋值为null值。但是双端链表也不能很好地解决我们删除链表最后一个链节点,因为我们没有指向链表倒数第二个节点的引用,当然也可以遍历链表找到倒数第二个链节点,但效率不高,为解决这样的问题,接下来我们介绍“双向链表”。

Q: 链表的效率?

A: 在表头插入和删除速度很快,仅需要改变一两个引用值,所以花费O(1)的时间。

A: 查找、删除和在指定结点的前面插入都需要搜索链表中一半的结点,需要O(N)次比较,在数组中执行这些操作也需要O(N)次比较。但是链表仍然要快一些,因为插入和删除结点时,链表不需要移动任何东西。

A: 链表比数组还有一个优点是,链表需要多少内存就可以用多少内存,不像数组在创建时大小就固定了。

A: 向量是一种可扩展的数组,它可以通过可变长度解决这个问题,但是它经常只允许以固定的增量扩展(比如快要溢出的时候,就增加1倍的数组容量)。这个解决方案在内存使用效率上来说还是要比链表低。

  双向链表:传统链表进行反向遍历是很困难的,双向链表在于每个链节点存在两个指向其他链节点的引用,这样就可以正向和反向遍历整个链表

Q: 用链表实现的栈?

A: 示例:Stack.java

A: 栈的使用者不需要知道栈用的是链表还是数组实现。
因此Stack类的测试用例在这两个上是没有分别的。

永利皇宫 9

Q: 用链表实现的队列?

A: 示例:Queue.java

A: 展示了一个用双端链表实现的队列。

  双向链表的缺点是每次插入和删除需要处理四个链节点的引用而不是两个,每个链节点多了一个链节点的引用,链节点所占的空间变大。双向链表可以从任何一头插入或删除,可用来作为双端队列的基础

Q: 什么时候应该使用链表而不是数组来实现栈和队列呢?

A: 这一点要取决于是否能精准地预测栈或队列需要容纳的数据量。如果这一点不是很清楚的话,链表就比数组表现出更好的适用性。两者都很快,所以速度可能不是考虑的重点。

永利皇宫 10永利皇宫 11

Q: 什么是抽象数据类型(ADT)?

A: 简单来说,它是一种考虑数据结构的方式:着重于它做了什么,而忽略它是怎么做的。

A: 栈和队列都是ADT的例子,前面已经看到栈和队列既可以用数组实现,也可以使用链表实现,而对于使用它们的用户完全不知道具体的实现细节(用户不仅不知道方法是怎样运行,也不知道数据是如何存储的)。

A: ADT的概念在软件设计过程中很重要,如果需要存储数据,那么就要从它的实际操作上开始考虑,比如,是存取最后一个插入的数据项?还是第一个?是特定值的项?还是在特定位置上的项?回答这些问题会引出ADT的定义。

A: 只有在完整定义ADT后,才应该考虑细节问题。

A: 通过从ADT规范中剔除实现的细节,可以简化设计过程,在未来的某个时刻,易于修改实现。如果用户只接触ADT接口,应该可以在不“干扰”用户代码的情况下修改接口的实现。

A: 当然,一旦设计好ADT,必须仔细选择内部的数据结构,以使规定的操作的效率尽可能高。例如随机存取元素a,那么用链表表示就不够好,因为对链表来说,随机访问不是一个高效的操作,选择数据会得到更好的效果。

 

Q: 有序链表?

A: 在有序链表中,数据是按照关键值有序排列的,有序链表的删除常常是只限于删除在表头的最小(或最大)的节点。

A: 一般,在大多数需要使用有序数组的场合也可以使用有序链表。有序链表的优势在于插入的速度,因为元素不需要移动,而且链表可以随时扩展所需内存,数组只能局限于一个固定大小的内存。

A: 示例:SortedLinkedList.java

A: 当算法找到要插入的位置,用通常的方式插入数据项:把新节点的next字段指向下一个节点,然后把前一个结点的next字段指向新节点。然而,需要考虑一些特殊情况:节点有可能插在表头,或者表尾。

 

Q: 有序链表的效率?

A: 在有序链表插入或删除某一项最多需要O(N)次比较(平均N/2),因为必须沿着链表一步一步走才能找到正确的位置。然而,可以在O(1)的时间内找到或删除最小值,因为它总在表头。

A: 如果一个应用频繁地存取最小项,且不需要快速地插入,那么有序链表是一个有效的方案选择,例如,优先级队列可以用有序链表来实现。

 

Q: 链表插入排序(List Insertion Sort)?

A: 有序链表可以用于一种高效的排序机制。假设有一个无序数组,如果从这个数组中取出数据,然后一个一个地插入有序链表,它们自动地按照顺序排列。然后把它们从有序链表删除,重新放入数组,那么数组就排好序了。

A: 本质上与基于数组的插入排序是一样的,都是O(N2)的比较次数,只是说对于数组会有一半已存在的数据会涉及移动,相当于N2/4次移动,相比之下,链表只需2
* N次移动:一次是从数组到链表,一次是从链表到数组。

A: 不过链表插入有一个缺点:就是它要开辟差不多两倍的空间。

A: 示例: LinkedListSort.java

网站地图xml地图