线性表是一个由元素构成的序列,该序列有唯一的首元素和尾元素,除了首元素外,每个 元素都有唯一的前驱元素,除了尾元素外,每个元素都有唯一的后继元素,因此线性表中的元 素是有先后关系的。 线性表中的元素数据类型相同,即每个元素所占的内存空间大小必须相同。 实践中,适合用线性表存放数据的情形有很多,如26个英文字母的字母表、一个班级全部 学生的个人信息表、参加会议的人员名单等。 根据在内存中存储方式的不同,线性表可以分为顺序表和链表两种。 3.1　顺　序　表 3.1.1 顺序表的概念和操作 顺序表是元素在内存中连续存放的线性表。顺序表的最根本和最有用的性质,是每个元 素都有唯一序号,且根据序号访问(包括读取和修改)元素的时间复杂度是O(1)的。序号通常 也称为元素的“下标”。首元素的下标是0(规定为1也可以),下标为i 的元素的前驱元素如 果存在的话,下标是i-1,后继元素如果存在的话,下标是i+1。下标为i 的元素,就称为第i 个元素。 各种程序程序设计语言,如C/C++、Java等中的数组,都是顺序表。Python中的列表 (list)也是顺序表。顺序表中的元素类型是一样的。 一般来说,顺序表应当支持表3.1中的操作。 表3.1 顺序表支持的操作 序号操 作含 义时间复杂度 1 init(n) 生成一个含有n 个元素的顺序表,元素值随机O(1) 2 init(a0,a1,…,an ) 生成元素为a0,a1,…,an 的顺序表O(n) 3 length() 求表中元素个数O(1) 4 append(x) 在表的尾部添加一个元素x O(1) 5 pop() 删除表尾元素O(1) 续表 序号 6 操作 get(i) 含义 返回下标为 i 的元素 时间复杂度 O(1) 7 set(i,x) 将下标为 i 的元素设置为 x O(1) 8 find(x) 查找元素 x 在表中的位置O(n) 9 insert(i,x) 在下标为 i 处插入元素 x O(n) 10 remove(i) 删除下标为 i 的元素O(n) int(:分配一片能够放下 n 个元素的内存空间,不需要对这片空间进行初始化。这片 内存空间里原来的内容是什么,分配完还是什么,因此 n 个元素的初始值是随机无意义的。 当然,分配空间本身是需要时间的,其快慢取决于操作系统,姑且认为是O(1)的。 ia0, in) int(a1,…, n ): 和init操作相比,需要将存放n+1 个元素的内存空间初始化为a0, an a1,…,,因此复杂度(a) 为O()。 length(): 求顺序表元素个(n) 数。该操作应在O(1)时间内完成,专门维护一个记录顺序表 元素个数的变量即可做到这一点。 append(x):在顺序表尾部添加元素。这是一件比较复杂的事情。如果为顺序表分配的 内存空间刚好容纳原有的全部 n 个元素,则直接将新元素添加到末尾元素的后面是不行的, 因为末尾元素后面的内存空间有可能并非空闲,而是已经另有他用,如果鲁莽地往这部分空间 写入数据,可能导致不可预料的错误。一种解决办法是重新分配一块足以容纳n+1 个元素 的连续的内存空间,将原来的 n 个元素复制过来,然后再写入新的元素,当然还要释放原来的 空间。这样做需要用O(n)的时间来复制元素,append(x)的复杂度就是O(n)。为了避免每 次执行appnx) 可以预先为顺序表多分配一些空间, ppnx) ed(都要复制元素, 这样需要执行aed( 时,绝大多数情况下就可以直接将 x 写入原末尾元素的后面。待多余空间用完了,再次执行 d(x), 才需要重新分配一片更大的空间并执行复制元素的操作。appen 按照预先多分配空间的思想,可以引入顺序表的“容量”这个概念。顺序表的容量,是指不 需要重新分配空间就能容纳的最大元素个数。空顺序表生成时,容量可以为0,但是第一次执 行append(x)操作时,就可以多分配存储空间,例如,使其容量变为4(当然也可以是其他数 目), 这样接下来的3次append(x)操作就不需要重新分配空间。当元素个数到达容量时,再 执行append(x)操作就需要重新分配空间并进行元素的复制。重新分配空间时,新的容量自 然不能只是原容量加1,而应该增加得更多。 k 是固定值。对空表执行 一种方案是每次重新分配空间时,新容量总是等于旧容量加k, append(x)操作时即分配容量k。由于元素个数每达到 k 的倍数加1时就需要重新分配存储 空间并进行元素的复制,因此可以算出,执行 m ×k 次append(x)操作,元素个数从0增长到 m×k 的过程中,总共复制过的元素个数是: k+2k+3m-k=1+2+3+…+(1))km(m-1) k+…+(1)k(m-= 2 因此在元素总数n=m×k 的情况下,平均每次append(x)操作,需要复制m-1个元素, 2 m-1= k(m-1)= n-kn 1 所以aed(的复杂度是O()。这说 22k 2k 2k(=) -2,由于 k 是常数, ppnx) n 明扩容时新容量总是等于旧容量加 k 的办法意义不大。 还有一种方案,扩容时, 可以取1. 新容量总是旧容量的 k 倍。 k 是大于1的固定值, 2、 28 1.5、2等。假定第一次分配空间时,容量为1。由于元素个数每达到k的幂(向上取整)加1时 就需要重新分配存储空间并进行元素的复制,因此可以算出,执行km次append(x)操作,元素 个数达到km个时,总共复制过的元素个数是: 1+k+k2+…+km-1= km-1 k-1 因此在元素总数n=km 的情况下,平均每次append(x)操作,需要复制的元素个数是: km (1) n-1 1 = k-k-k-1 ppnxk) m (1)n(1)< 1) k 取1. 因 k 是常数,所以aed(操作的平均复杂度是O(的。一般来说,2左右既不 会太浪费空间,又能兼顾效率。 在上面的推导过程中,不是整数时, 不影响结论的正确性。 km 向上取整即可, pop():append(x)都能做到O(1),删除表尾元素做到O(1)当然也没有问题,一般情况 下,只需要将元素总个数的计数值减1即可。在表中空闲单元超过一定程度(如超过容量的一 半)的时候,可以为顺序表重新分配更小的容量,将原有元素复制过去。 gei)ei,:假设顺序表在内存的起始地址是s, t(和st(x)且每个元素占用的内存空间为 m 字节,则第 i 个元素的内存地址就是s+i×m ———这里的下标 i 从0开始算。由于用O(1)的 时间就能找到第 i 个元素的地址,所以读写第 i 个元素的时间,就是O(1)的,和顺序表中元素 的个数无关。 find(x):要在顺序表中查找元素x,没有什么好办法,只能从头看到尾。如果表中有x, 可能出现在头一个,也可能出现在最后一个, 平均要看( 对一个有 n 个元素的顺序表, n+1)/2 个元素才能找到x。如果表中不包含x,则要看完 n 个元素才能得到这个结论。不管哪种情 n 况,复杂度都是O()。如果找到x,则返回 x 第一次出现的下标;如果找不到x,可以返回 -1。id() 如fnx,表示从下标 i 处开始寻找x。fn还可以有功能更强的版本, id(i) 可以使得查找的复杂度变为O(on 如果顺序表中元素是排好序的,则用二分查找的办法, lg( ) 。 但那是另一回事,因为顺序表的特性并不包括元素有序。 inet(x):在下标 i 处插入元素x, sri,会导致原下标 i 处及其后面的元素都要往后移动一 个元素的位置(实际上就是把元素复制到后面的位置)。对原本有 n 个元素的顺序表来说,要 移动的元素个数是n-i, n+1)/2个, nset(i,x) n 如果 平均是(所以ir的复杂度是O()。当然, insert操作导致元素个数超过了顺序表的容量,还需要重新分配空间。 remove(i):删除下标 i 处的元素,会导致原下标i+1及后面的元素都要往前移动。类 似于inet(x), n sri,复杂度也是O()。 总之,在顺序表中进行查找,以及在中间插入、删除元素,都没有办法做到低于O(n)的复 杂度。 但是所有语言的顺序表, ei) ei, 不同语言中的顺序表,支持的操作不一样, 都支持gt(和st(x) 这两个在O(1)时间内根据下标读写元素的根本操作,这个操作,也叫“随机访问”。 Java的数组是顺序表,大小在初始化的时候就固定了且不能更改,因此只支持length()、 两种int操作以及gt(和st(x) —iigt(和st(x) iei)ei,操作——nt操作就是定义数组,ei)ei,操作 通过“[]”和下标进行。C/C++数组比Java数组还少支持了length()操作。 但是C++中有vcoJvrast等数据结构,全面支持顺序表的各种操作。 etr,aa中有AyLi 29 30 3.1.2 Java 中的顺序表 Java的数组是顺序表,但是数组不支持添加和删除元素。 Java语言中全面支持各种操作的顺序表是泛型类ArrayList和Vector。这两者都实现了 List接口。Vector支持多线程安全访问而ArrayList不支持,因此在单线程的情况下应使用 效率更高的ArrayList。目前,即便在多线程的情况下,官方也不推荐使用Vector,而是有别 的选择。 ArrayList在扩充容量时,会扩充到原容量的1.5倍。 表3.2中的方法,都是List接口的方法,所以ArrayList和Vector都支持。 表3.2 ArrayList和Vector部分常用方法 方 法功 能复杂度 booleanadd(Ee) 在尾部添加元素e,返回是否成功O(1) voidadd(intindex,Ee) 插入e,使其成为第index个元素。元素序号从0 开始算O(n) voidclear() 清空表O(1) Eremove(intindex) 删除第index个元素,并返回之O(n) booleancontains(Objecto) 判断是否含有元素o O(n) Eget(intindex) 返回第index个元素O(1) intindexOf(Objecto) 查找元素o 第一次出现的位置O(n) Eset(intindex,Ee) 将第index个元素设置为e O(1) intsize() 返回顺序表元素个数O(1) voidsort(Comparator) 排序O(nlog(n)) iteratoriterator() 返回指向第0个元素的迭代器O(1) 假设有ArrayList的对象a,删除a 中最后一个元素的做法是: a.remove(a.size()-1); 这个操作复杂度是O(1)的。 3.2　链　　表 顺序表的劣势,是在中间插入和删除元素较慢(O(n)复杂度)。另外,在一些极端情况下, 元素太多以至于找不到足够大的连续内存来存放它们,此时就无法使用顺序表。采用链接结 构的链表能够较好地解决上述问题。 链接结构是一类元素在内存中不必连续存放,可以随意分布,元素之间通过指针链接起来 的数据结构。在链接结构中,一个元素内部除了存放数据,还有一个或多个指针,指向其他元 素。“指向”的准确含义是“指出其他元素的内存地址”。链接结构中的元素,更经常被称为“结 点”。链接结构可以用来实现二叉树和树等数据结构。用链接结构实现的线性表,叫作链表。 链表有单链表、双链表、循环链表等多种形式。它们的共同特点如下。 (1)结点在内存中不需要连续存放。 (2)每个结点中都包含一个指向其后继结点的指针,不妨称其为next指针。表尾结点的 next指针设为null或做另外特殊处理。 (3)表中结点可以动态增减。增删结点时,不需要复制结点或移动结点。 31 (4)如果已经得到了指向结点p 的指针,则删除p 的后继结点,或者在p 后面插入新结 点,复杂度都是O(1)的。 链表不支持随机访问。要访问表中第i 个元素,只能从表首元素开始,顺着next指针链 一步步往后走,直到走到第i 个元素。所以访问第i 个元素这样的操作复杂度是O(n)的。 3.2.1 单链表 每个结点中只包含一个指针,该指针指向后继结点,这样的链表称为单链表。图3.1是一 个单链表的例子。 图3.1 单链表 head、tail和size是三个变量,head指向表首结点3,tail指向表尾结点13,size记录表中 结点个数。单链表的结点由数据和next指针构成。在图3.1中next指针就是两个结点之间 的箭头。只要有了指向表首结点的指针head,就可以从表首结点出发,顺着next指针链找到 全部结点。表尾结点的next指针设置为null(在图中用“^”表示)。结点中的数据,类型是相 同的。简单起见,本节假设数据是整数。 对于有head和tail指针的单链表,删除表首结点,或者在表首结点前面插入结点,复杂度 是O(1)的。在表尾后面添加结点,复杂度也是O(1)的。但是要删除表尾结点,复杂度是O(n) 的,因为需要先从表首结点出发顺着next指针链找到表尾的前驱结点。 单链表可以实现为下面程序prg0260 中的LinkList类。请注意,由于本书中还有 Python、C++版本,为了保持不同版本中相同程序的编号一致,故本书程序编号不具有连续 性。上一个程序是prg0170,并不意味着prg0180到prg0250缺失了———它们本来就不存在于 本书中。 //prg0260.java 1. import java.util.*; 2. class LinkList implements Iterable { 3. static class Node { 4. T data; Node next; 5. Node(T dt,Node nt) { data = dt;next = nt; } 6. } 7. Node head,tail; 8. int size; 9. LinkList() { head = tail = null; size = 0; } Node是内部类,用于表示链表的结点。data是数据,next是指向后继结点的指针。 链表对象初始化为一个空链表,head和tail都是null,size值为0。 实现Iterable接口,是为了支持用foreach循环遍历链表,不是必须。 遍历并输出单链表全部内容的成员函数如下。 10. void printList() { 11. Node ptr = head; 12. while (ptr != null) { 13. System.out.print(ptr.data+","); 14. ptr = ptr.next; 32 15. } 16. System.out.println(); 17. } 如果已经定位到了结点p,在结点p 后面插入新结点nd的过程如下。 (1)如图3.2所示,执行“Node nd= new Node(data,null);”,新建结点nd (假设data等于20)。 (2)如图3.3所示,执行“nd.next=p.next;”。 (3)如图3.4所示,执行“p.next= nd;”,完成插入。 图3.2 链表插入新结点步骤(1) 图3.3 链表插入新结点步骤(2) 图3.4 链表插入新结点步骤(3) 相应的成员函数如下。 18. void insert(Node p,T data) { //在结点p 后面插入数据为data 的新结点 19. Node nd = new Node(data, null); 20. if (tail == p) //新增的结点是新表尾 21. tail = nd; 22. nd.next = p.next; 23. p.next = nd; 24. ++size; 25. } 如果已经定位到了结点p,删除p 的后继结点的过程如下。 (1)如图3.5所示,初始状态,将要删除数据为5的结点。 (2)如图3.6所示,执行“p.next=p.next.next;”,完成删除。 图3.5 链表删除结点步骤(1) 图3.6 链表删除结点步骤(2) 相应的成员函数为 26. void deleteAfter(Node p) { //删除p 后面的结点 27. if (tail == p.next) //如果要删除的是表尾结点 28. tail = p; 29. p.next = p.next.next; 30. --size; 31. } 定位到了结点p,要删除结点p 是困难的,因为必须找到p 的前驱。而找前驱,就需要从 head开始往后找,这样复杂度就不是O(1)的了。 在C/C++语言中,从链表中删除结点p 后,还需要写一行代码释放结点p 占用的空间, 但是在Java或Python中,不用操心这一点。当结点p 不可能再被访问到时,Java虚拟机或 Python解释器就会释放结点p 的空间。 33 在链表前端插入一个结点的成员函数如下。 32. void pushFront(T data) { //在链表前端插入一个结点data 33. Node nd = new Node(data,head); 34. head = nd; 35. ++size; 36. if (tail == null) //如果原来链表为空 37. tail = nd; 38. } 删除链表前端元素的成员函数如下。 39. T popFront() throws RuntimeException { 40. if (head == null) //如果链表为空 41. throw new RuntimeException("Linked list is empty."); 42. else { 43. Node p = head; 44. head = head.next; 45. --size; 46. if (size == 0) 47. head = tail = null; 48. return p.data; 49. } 50. } 在链表尾部添加元素的成员函数如下。 51. void pushBack(T data) { 52. if (size == 0) 53. pushFront(data); 54. else 55. insert(tail,data); 56. } 清空链表的成员函数如下。 57. void clear() { 58. head = tail = null; 59. size = 0; 60. } Java会自动回收不再有用的链表结点的空间。 还可以为LinkList类添加iterator()方法,以及配套的MyIterator内部类,使其可以用 foreach循环遍历。 61. private class MyIterator implements Iterator { 62. Node cur; 63. MyIterator() { cur = head; } 64. public boolean hasNext() { return cur != null; } 65. public T next() { 66. T data = cur.data; 67. cur = cur.next; 68. return data; 69. } 70. } 71. public Iterator iterator() { 72. return new MyIterator(); 73. } 34 74. } //LinkList 类到此结束 75. public class prg0260{ 76. public static void main(String[] args) { 77. LinkList linkLst = new LinkList(); 78. for (int i = 0;i < 5; ++i) 79. linkLst.pushFront(i); 80. linkLst.printList(); //>>4,3,2,1,0, 81. for (Integer i:linkLst) //>>4,3,2,1,0, 82. System.out.print(i+","); 83. System.out.println(); 84. Iterator it = linkLst.iterator(); 85. while (it.hasNext()) //>>4,3,2,1,0, 86. System.out.print(it.next()+","); 87. System.out.println(); 88. LinkList.Node p = linkLst.head; 89. linkLst.insert(p,100); 90. linkLst.printList(); //>>4,100,3,2,1,0, 91. p = p.next; 92. linkLst.deleteAfter(p); 93. linkLst.printList(); //>>4,100,2,1,0, 94. } 95. } 从工程实践上来说,上面的LinkList类不完备且有缺陷,因为没有实现“隐藏”,类内部的 成员变量都暴露在外,很容易因对成员变量的误操作导致整个链表崩溃。如何在用类实现一 个数据结构时,进行“隐藏”以保护数据结构不被不小心破坏,可参看3.2.3节“双链表”。 为了避免处理在表首尾增删、空表等特殊情况,简化编程,在实现单链表时,常常设置一个 空闲的头结点,即使是空表,也包含该头结点。这样的链表称为“带头结点的链表”。如图3.7 和图3.8所示,图中数据部分为阴影的结点就是头结点。 图3.7 带头结点的空单链表 图3.8 带头结点的非空单链表 前面特意用“表首结点”来称呼链表中最靠前的存有有效数据的结点,以和这里的“头结 点”进行区分。“头结点”特指不包含有效数据的冗余结点。 带头结点的单链表的构造函数应如下编写。 LinkList() { head = tail = new Node(null,null); size = 0; } 3.2.2 循环单链表 在单链表中,若将表尾结点的next指针由null改为指向表首结点,next指针链就形成了 循环,这样的单链表称为循环单链表。在循环单链表中,可以只设置表尾指针tail,因为tail .next即是表首。只设置表首指针head则不好,因为要找到表尾需要遍历整个链表。图3.9 和图3.10则是带头结点的循环单链表。 35 图3.9 带头结点的空 单循环链表 图3.10 带头结点的非空单循环链表 循环单链表在表首或表尾添加元素,以及删除表首元素,复杂度都是O(1)的。 3.2.3 双链表 在单链表中要找结点的前驱,只能从表首开始往后找,复杂度是O(n)的。为了消除这一 不便,引入了双链表,也叫双向链表。双链表中每个结点不但有指向后继的指针next,还有指 向前驱的指针prev。一个带头结点的双链表如图3.11所示,头结点的prev为null,尾结点的 next为null。 图3.11 带头结点的双链表 下面讲述带头结点的双链表上的一些操作。 如果已经定位到了结点p,在结点p 后面插入新结点nd的过程如下。 (1)如图3.12所示,执行“Node nd= new Node(data,null,null);”,新建结 点nd。 (2)如图3.13所示,执行“nd.prev=p;nd.next=p.next;”。 图3.12 双链表插入结点步骤(1) 图3.13 双链表插入结点步骤(2) (3)如图3.14所示,若p.next不为null,则执行“p.next.prev= nd;”。 (4)如图3.15所示,执行“p.next= nd;”,插入完成。 图3.14 双链表插入结点步骤(3) 图3.15 双链表插入结点步骤(4) 注意,上面的步骤(3)和(4)的次序是一定不能颠倒的。 36 如果已经定位到了结点p,删除结点p 的过程如下。 图3.16 双链表删除结点步骤(1) (1)如图3.16所示为初始状态,将要删除结点5。 (2)如图3.17所示,执行“p.prev.next=p.next;”。 (3)如图3.18 所示,若p.next不为null,则执行 p.next.prev=p.prev;完成删除。 图3.17 双链表删除结点步骤(2) 图3.18 双链表删除结点步骤(3) 下面的程序prg0270实现了一个带头结点的双链表类BiLinkedList。该双链表类的用法 接近于Java自带的LinkedList。BiLinkedList类进行了封装和隐藏,使用者只能通过类中的 public方法来操作链表,不会破坏链表内部的结构。这部分内容的重点是封装和隐藏,而非链 表操作,对计算机专业读者也属于较高要求,非计算机专业的读者可以跳过。 在这个实现中,要访问链表元素,必须通过一个“迭代器”,即BiLinkedList类的内部类 MyIterator的对象来进行,“迭代器”包含指向链表元素的指针,因此也可以说迭代器指向链表 元素。迭代器的get()和set()方法用来访问链表元素。对迭代器i,i.next()会返回i 指向的 元素的后继的迭代器;i.remove()删除i 所指向的元素,并让i 指向被删除元素的后继;i.add(x) 将新元素x 插入到i 所指向的元素的后面。BiLinkedList类的iterator()方法返回指向第一 个元素的迭代器,由它开始就可以访问整个链表。 受篇幅所限,这个实现并不完备,没有提供由后往前遍历链表的手段,读者可以自行研究 加上。需要改写MyIterator类,如添加hasPrevious()方法和previous()方法,hasNext()方法 和next()方法可能也要改写。 //prg0270.java 带头结点的双链表 1. import java.util.*; 2. class BiLinkedList implements Iterable { 3. static class Node { 4. T data; Node prev,next; 5. Node(T dt,Node pr, Node nt) { 6. data = dt; prev = pr; next = nt; 7. } 8. } 9. private Node head,tail; 10. private int size; 11. BiLinkedList() { 12. head = tail = new Node(null,null,null); //头结点 13. size = 0; 14. } 15. private void _insert(Node p, T data) { 16. //在结点p 后面插入新结点 17. Node nd = new Node(data,p,p.next); 18. if (p.next != null) 19. p.next.prev = nd; 20. else tail = nd; //p 是原表尾 21. p.next = nd; 22. size += 1; 37 23. } 24. private Node _delete(Node p) { //删除结点p,p 一定不为null 25. Node q = p.next; //函数要返回q,即p.next 26. p.prev.next = p.next; 27. if (p.next != null) //如果p 有后继 28. p.next.prev = p.prev; 29. if (tail == p) 30. tail = p.prev; 31. size -= 1; 32. return q; 33. } 34. int size() { return size; } 35. void clear() { 36. tail = head; size = 0; 37. head.next = head.prev = null; 38. } 39. void addFirst(T data) { //在链表前端插入一个元素 40. _insert(head,data); 41. } 42. T removeFirst() { //删除链表前端元素 43. if (size == 0) 44. throw new RuntimeException("Deleting empty list."); 45. else { 46. T data = head.next.data; 47. _delete(head.next); //head 指向的是空闲的头结点 48. return data; 49. } 50. } 51. void addLast(T data) { _insert(tail,data); } 52. T removeLast() { 53. if (size == 0) 54. throw new RuntimeException("Deleting empty list."); 55. else { 56. T data = tail.data; 57. _delete(tail); 58. return data; 59. } 60. } 61. class MyIterator implements Iterator { 62. Node cur; 63. MyIterator() { cur = head.next;} //head 指向的是空闲的头结点 64. MyIterator(Node ptr) { cur = ptr; } 65. public boolean hasNext() { return cur != null; } //是否指向有效元素 66. public T next() { 67. T data = cur.data; 68. cur = cur.next; 69. return data; 70. } 71. public T get() { return cur.data; } 72. public void set(T data) { cur.data = data; } 73. public void add(T data) { _insert(cur,data); } 74. //在迭代器指向的元素后面添加元素 75. public void remove() { cur = _delete(cur); } 76. //删除迭代器指向的元素,并将迭代器指向被删除元素后面的元素 77. } 38 78. public MyIterator iterator() { //返回最靠前的元素的迭代器 79. return new MyIterator(); 80. } 81. public MyIterator iterator(int i) { 82. //返回指向第i 个元素的迭代器。i 从0 开始算 83. Node ptr = head.next; 84. for(int k=0;k ptr = head.next; 93. while (ptr!=null) { 94. if (ptr.data == val) 95. return new MyIterator(ptr); 96. ptr = ptr.next; 97. } 98. return null; 99. } 100.} 101.public class prg0270{ 102. public static void main(String[] args){ 103. BiLinkedList linkLst = new BiLinkedList<>(); 104. for (int i = 0;i < 5; ++i) 105. linkLst.addFirst(i); 106. for (Integer i:linkLst) //>>4,3,2,1,0, 107. System.out.print(i+","); 108. BiLinkedList.MyIterator it = linkLst.iterator(); 109. while (it.hasNext()) { //>>4,3,2,1,0, 110. System.out.print(it.get()+","); 111. it.next(); 112. } 113. it = linkLst.find(3); //it 指向元素3 114. it.set(30); //将it 指向的元素改为30 115. System.out.println(it.get()); //>>30 116. it.add(100); //it 指向的元素后面添加100 117. System.out.println(linkLst.size()); //>>6 118. it.remove(); //删除it 指向的元素,即30 119. System.out.println(linkLst.size()); //>>5 120. while (it.hasNext()) { //>>100,2,1,0, 121. System.out.print(it.get()+","); 122. it.remove(); 123. } 124. } 125.} 3.2.4 静态链表 可以将链表存储于顺序表中,这样的链表称为静态链表。顺序表中的每个元素,除了存放 数据的部分,还包含一个next指针,实际上是一个整数,表示链表中下一个元素在顺序表中的 下标。顺序表下标为0的元素不存放数据,其next指针指明了链表表首元素的下标。链表最 39 后一个元素的next指针为null或-1。图3.19展示了一个静态链表,链表中的元素按顺序是 78,81,92,49,52。 图3.19 静态链表 在静态链表中插入元素比较简单,将新元素添加到顺序表末尾,然后修改一些指针即可。 删除元素,只能让被删除的元素所占的单元空着,并不回收其内存空间。例如,图3.19中下标 为4、6的单元,就可能是在删除元素后留下的空白单元。删除操作会造成一些空间浪费。可 以在顺序表空白单元的比例超过某个阈值的时候重新分配一个顺序表,将原表中的内容复制 过去。一 般提到链表的时候指的都不是静态链表,本书也是如此。 ★★3.2.5 Java 中的链表 Java中的泛型类LinkedList是一个双向链表,其实现了List接口。LinkedList还实现了 Queue和Deque接口,因此还可以作为队列和双向队列使用。 LinkedList类的部分常用方法如表3.3所示。 表3.3 LinkedList部分常用方法 方 法功 能复杂度 booleanadd(Ee) 在尾部添加元素e,返回是否成功O(1) voidadd(intindex,Ee) 插入e,使其成为第index个元素。元素序号从0 开始算O(n) voidaddFirst(Ee) 将元素e 插入到表首O(1) voidaddLast(Ee) 将元素e 添加到表尾O(1) voidclear() 清空链表O(1) EremoveFirst() 删除并返回第0个元素O(1) EremoveLast() 删除并返回最后一个元素O(1) Eremove(intindex) 删除第index个元素,并返回之O(n) booleancontains(Objecto) 判断是否含有元素o O(n) Eget(intindex) 返回第index个元素O(n) EgetFirst() 返回第0个元素O(1) EgetLast() 返回最后一个元素O(1) intindexOf(Objecto) 查找元素o 第一次出现的位置O(n) Eset(intindex,Ee) 将第index个元素设置为e O(n) intsize() 返回链表元素个数O(1) voidsort(Comparator) 排序O(nlog(n)) ListIteratorlistIterator() 返回指向第0个元素的迭代器O(1) ListIterator listIterator(intindex) 返回指向第index个元素的迭代器O(n) clear方法复杂度是O(1)。清空链表后,回收每个链表结点都需要时间,这部分时间是 O(n)的。不过,回收空间是Java虚拟机的工作,一般不算作Java程序的运行时间。 需要强调的是,表3.3中带元素位置参数index的方法,例如get()、set()、remove()、第二 40 个add(),复杂度都是O(n)的———因为链表不支持随机访问,要找到位置index,就需要从链 表开头一直往后顺着next指针走到位置index。所以,遍历一个LinkedList,绝对不要使用以 下写法,因为其复杂度是O(n2)的。 List L = new LinkedList<>(); …f or(int i=0;ilistIterator(intindex)方法找到指向位置index的迭代器, 然后通过迭代器的add()和remove()方法进行插入和删除。 //prg0272.java 1. import java.util.*; 2. public class prg0272 { 3. public static void main(String[] args) { 4. LinkedList L = new LinkedList<>(); 5. for(int i=0;i<7;++i) 6. L.add(i); 7. for(Integer x:L) //遍历,输出0,1,2,3,4,5,6, 8. System.out.print(x + ","); 9. System.out.println(); 10. ListIterator it = L.listIterator(); 11. while (it.hasNext()) //遍历,输出0,1,2,3,4,5,6, 12. System.out.print(it.next()+","); 13. System.out.println(); 14. it = L.listIterator(L.size()); 15. while(it.hasPrevious()) //逆向遍历,输出6,5,4,3,2,1,0, 16. System.out.print(it.previous()+","); 17. System.out.println(); 18. it = L.listIterator(3); //it 指向第3 个元素,即3 19. it.add(100); //在元素3 前面插入100,it 还是指向3 20. it.add(200); //在元素3 前面插入200,it 还是指向3 21. for(Integer x:L) //>>0,1,2,100,200,3,4,5,6, 22. System.out.print(x + ","); 23. System.out.println(); 24. for(int i=0;i<3;++i) { //删除从3 开始的3 个元素 25. it.next(); 26. it.remove(); 27. } 28. for(Integer x:L) //>>0,1,2,100,200,6, 29. System.out.print(x + ","); 30. } 31. } 第11行:it.hasNext()返回it是否指向一个有效元素。 第12 行:it.next() 让it指向下一个元素,但是返回的是it原来指向的元素。 需要注意的是,对一个ListIterator迭代器it来说,必须在调用一次it.next() 或it.previous() 之后才可以调用it.remove(), 此时删除的是刚才调用it.next() 或it.previous() 时返回的那个 元素。而且,连续两次it.remove() 调用之间必须调用过it.next() 或it.previous() 。调用 itax) 如果没调用过i.et() tpeiu就不能调用i.emoe()。 .dd(添加元素后, tnx或i.rvos(), trv 3.3　顺序表和链表的选择 由于顺序表支持随机访问而链表不支持,所以顺序表的使用场景远远多于链表。一些老 的数据结构教材,会说在最大元素个数不能确定或者为了节约空间,不希望总按最大可能元素 个数来开设顺序表或元素需要动态增减等场合,应该使用链表。这个结论早已过时。现在除 了C语言,各种常用的语言如C++、Java、Python等都提供了能够很方便动态添加元素的顺序 表。而且说到节约空间,在Java和Python这类所有变量都是指针的语言中,相比顺序表的冗 余空间,链表元素中的next指针其实浪费了更多的空间,所以从空间的角度来说,链表相比顺 序表基本没有优势。 顺序表的元素在内存中是连续存放的,而链表的元素却不是,这会导致在现实计算机系统 中前者访问效率远好于后者。现代计算机的CPU 中都有Cache(高速缓存), 其访问速度比内 存快数倍到数十倍。当CPU 访问某内存单元时,会将该内存单元附近的一片连续内存区域 的内容读取到Cache(这叫内存预取), 下次再访问同一区域的内容时,就只需要从Cache读取 数据,不必再访问速度较慢的内存。甚至对内存的写入,也可以只暂时写入Cache,在适当时 候才写入内存。因此,遍历同样多元素的顺序表和链表,前者速度比后者快数倍甚至数十倍。 此外,链表结点的空间回收是逐个结点进行的,需要花O(n)的时间,而顺序表的空间是连续 的,回收一般只需要O(1)时间。总体来说,在绝大多数应用场景中,链表相比顺序表,无论是 编程效率、时间效率还是空间效率,都处于劣势。 与顺序表相比,链表的真正优点是在表中间插入和删除元素的复杂度是O(1)的,但前提 是已经找到了要增删元素的位置。对于常见的要在第 i 个元素处插入元素,或删除第 i 个元 素、删除等于 x 的元素这样的操作,在链表中首先要找到第 i 个元素或找到等于 x 的元素(或 它们的前驱元素), 这也要花O(的时间, n) 因此和顺序表相比没有优势。 只有在线性表的中间某个位置附近频繁地做增删操作,链表相比顺序表的优势才能体现 出来,因为只需要花一次O(时间找到这个位置, 1)的。但是现实 n) 以后多次增删就都是O( 中需要这样做的场景不多,绝大多数场景都是在表头部或尾部进行增删,如栈和队列这样的数 据结构。即便需要O(1)时间在线性表头部进行增删,也可以使用基于顺序表实现的循环双向 队列,还是没有必要用链表(有些语言的双向队列内部实现结合了顺序表和链表)。 在某些特殊的场合,可以考虑使用静态链表,有可能同时得到链表插入删除快和连续内存 访问快的优势,如第13 章介绍的基数排序。 总之,在软件开发的实践中,只要不是用C语言,哪怕是用C++语言,需要使用链表的情 况都很少。在操作系统这样的用C/C++语言实现的底层软件系统中,以及一些语言自带的库 中,链表的应用才会多些。 链表能和顺序表取得相同甚至更高地位的场景,大概就只有数据结构考试的笔试了——— 因为链表的考题容易出。甚至在OpenJudge上的机考都很难考链表,因为不能用顺序表而必 41 须用链表才能在时限内通过的考题,设计起来比较麻烦而且题目往往显得不自然,所以现成的 题目也很少。 小　　结 线性表分为顺序表和链表两种。前者元素在内存中连续存放,支持随机访问操作(O(1) 时间访问第 i 个元素), 后者元素在内存中不连续存放,不支持随机访问操作。 顺序表在尾部增删元素的复杂度是O(1), 在中间增删元素的复杂度是O()。链表在确 n 定增删位置的前提下,增删元素复杂度为O(1)。 顺序表需要预先多分配空间,才能支持O(1)时间的尾部添加元素。预分配的策略是每次 重新分配空间时,分配的容量是元素个数的 k 倍( k 是大于1的固定值) 。 为链表设置头结点可以提高编程实现的方便性 。 由于CPU 有Cache,所以遍历同样多元素的顺序表和链表,前者要快得多 。 习　　题 1. 顺序表中下标为0的元素的地址是x,每个元素占4B,则下标为20 的元素的地址是 (地址以B为单位)( )。 A.x+80 B.x+20 C.x+84 D. 无法确定 2. 以下4种操作,有几种的时间复杂度是O(1)的?( ) (1)在顺序表尾部添加一个元素 (2)找到链表的第 i 个元素 (3)求链表元素个数 (4)在链表头部插入一个元素 A.1 B.2 C.3 D.4 3. 链表不具有的特点是( )。 A. 可随机访问任意元素 B. 插入和删除不需要移动元素 C. 不必事先预分配存储空间 D. 所需空间与链表长度成正比(静态链表除外) 以下为编程题。本书编程的例题习题均可在配套网站上程序设计实习MOOC 组中与书 名相同的题集中进行提交。每道题都有编号,如P0010 、P0020 。 1. 合并有序序列(P0010):给定两个从小到大排好序的整数序列,长度分别为 m 和n,要 求用O(m+n)时间将其合并为一个新的有序序列。 2.删除链表元素(:为3.1节中的单链表程序pg0260 中的LikLit类添加一 P0020)2.rns 个方法va), 用以删除值为da的元素。如果有多个,只删除最前面的 那个。 oidremove(Tdatat 3. 约瑟夫问题(P0030):用链表模拟解决猴子选大王问题: n 个猴子编号1~n,以顺时针 顺序排成一个圆圈。从1号猴子开始顺时针方向不停报数,1号猴子报1,报 2号猴子报2,…, 到 m 的猴子出圈,下一个猴子再从1开始报。最后剩下的那只猴子是大王。求大王的编号。 42 4.颠倒链表(P0040): 写一个函数,将一个单链表颠倒过来。要求额外空间复杂度为 O(1), 即原链表以外的存储空间是O(1)的。 ★5.共享链表(P0050): 两个单链表,从某个结点开始,后面所有的结点都是两者共享的 (类似于字母Y形状) 。请设计O(n)算法求两者共享的第一个结点(n是两者中间较长的链 表的长度)。 ★★6.链表寻环(P0060):请设计时间复杂度O(n)的算法判断一个单链表是否有环。 要求额外空间复杂度O(1)。有环的意思,就是最后一个元素的next指针,指向了链表中的某 个元素。 43