数据结构与算法（Java语言版）课件 第5、6章 链表与LinkedList类、顺序表与ArrayList类

第5章链表与LinkedList类2024/11/915.1链表的特点2024/11/92链表是由若干个节点组成，这些节点形成的逻辑结构是线性结构，节点的存储结构是链式存储，即节点的物理地址不必是依次相邻的。对于单链表，每个结点含有一个数据，并含有下一个节点的引用。对于双链表，每个节点含有一个数据，并含有上一个节点的引用和下一个结点的引用（Java实现的是双链表）2024/11/935.1链表的特点图示意的是有5个节点的双链表（省略了上一个节点的引用箭头示意）。注意，链表的节点序号是从0开始，每个节点的序号等于它前面的节点的个数。链表中的节点的物理地址不必是相邻的，因此，链表的优点是不需要占用一块连续的内存存储空间。图5.12024/11/945.1链表的特点

●删除头、尾节点的复杂度O(1)删除前面所示意5个节点的的链表的头节点(大象-节点)后的示意图。2024/11/955.1链表的特点

●查询头、尾节点的复杂度O(1)查询狮子和鳄鱼的时间复杂度都是O(1)。2024/11/965.1链表的特点

●添加头尾节点的复杂度O(1)要给图5.1所示意的链表的添加新的尾节点（企鹅-节点），根据双链表保存的尾节点的地址，找到尾节点（鳄鱼-节点），将这个尾节点中的下一个节点的引用设置成新添加的节点（企鹅-节点）的引用，将添加的新节点（企鹅-节点）中的上一个节点的引用设置成鳄鱼-节点的引用，将添加的新节点（企鹅-节点）中的下一个节点的引用设置成null，即让新添加的节点成为尾结点。2024/11/975.1链表的特点●查询中间节点的时间复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存引用链接在一起。

2024/11/985.1链表的特点●删除中间节点的复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存引用链接在一起。

删除了老虎-节点2024/11/995.1链表的特点●插入中间节点的复杂度O(n)

插入新节点后，新链表中的节点序号按新的链表长度从0开始排列。2024/11/9105.1链表的特点●插入中间节点的复杂度O(n)图5.1的链表中插入新的第2个节点（羚羊-节点）5.2创建链表2024/11/911链表由Java集合框架（JavaCollectionsFramework，JCF）中的LinkedList<E>泛型类所实现。2024/11/9125.2创建链表LinkedList<E>泛型类实现了Java集合框架中的List和Queue泛型接口。LinkedLis<E>t泛型类继承了List和Queue泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List和Queue泛型接口中的抽象方法。2024/11/9135.2创建链表例子1Example5_1.java使用LinkedList<E>泛型类声明链表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等），即指定链表中节点里的对象的类型。例如，指定E是String类型：LinkedList<String>listOne=newLinkedList<>();或LinkedList<String>listOne=newLinkedList<String>();例子1中的主类Example5_1中首先创建一个空链表listOne，然后向空链表listOne添加4个节点，随后再用listOne创建链表listTwo。修改listTwo节点的数据，并不影响listOne节点中的数据。5.3查询与相等2024/11/914查询链表节点中的数据的常用方法：

booleanequals(Objectlist)如果此链表和list长度相同，并且对应的每个节点中的对象也相等，那么方法返回true，否则返回flase。2024/11/9155.3查询与相等例子2People.javaExample5_2.java例子2中的主类Example5_2中比较了get(intindex)方法和getLast()方法的运行时间。例子2中的People类重写了booleanequals(Objecto)方法.2024/11/9165.3查询与相等例子3RandomLayMines.javaExample5_3.java

主类Example5_3使用layMines(char[][]area,intamount)方法布雷39颗。2024/11/9175.3查询与相等例子4TeamGame.javaExample5_4.java

5.4添加2024/11/918链表添加节点常用方法：

2024/11/9195.4添加例子5Example5_5.java例子5中的主类Example5_5中比较了voidaddLast(Ee)方法和voidadd(intindex,Ee)方法的运行时间。5.5删除2024/11/920链表删除节点常用方法：

2024/11/9215.5删除例子6RandomNumber.java例子6中RandomNumber类的getRandom(intnumber,intamount)方法通过随机删除链表中的节点来得到若干个随机数。Example5_6.java例子6中的主类Exmple5_6使用RandomNumber类的getRandom(intnumber,intamount)方法模拟双色球，同时过滤一个链表。2024/11/9225.5删除例子7HandleRecurring.javaExample5_7.java有时候需要处理数组中重复的数据，即让重复的数据只保留一个。在某些场景下，数据重复属于冗余问题。冗余可能给具体的实际问题带来危害，比如，你在撰写一篇文章时，用编辑器同时打开了一个文档多次，那么有时候就会引起混乱。所以，应当只打开文档一次，以免在修改，保存文档时发生数据处理不一致的情况。例子7中，HandleRecurring类的handleRecurring(LinkedList<E>list)方法处理链表list中重复的数据，该方法返回的链表中没有重复的数据（对于重复的数据，保留其中一个）。5.6更新2024/11/923链表更新节点的常用方法：

Collections类的静态方法static<T>voidfill(List<?superT>list,Tobj)将链表list的每个节点中的对象都设置为参数obj指定的对象。2024/11/9245.6更新例子8Example5_8.java例子8的主类Example5_8使用set(intindex,Eelement)方法和fill(List<?superT>list,Tobj)方法更新链表节点中的对象。5.7链表的视图2024/11/925链表的视图是由链表中若干个节点所构成，其状态变化和链表是同步的。视图的好处是，可以将经常需要修改的节点放在一个视图中，有利于数据的一致性处理。

使用视图时，要注意视图中节点和原链表节点的对应关系。2024/11/9265.7链表的视图List<E>subList(intfromIndex,inttoIndex)方法是AbstractList类所实现的List接口中的一个方法（AbstractList类是LinkedList的间接父类）。该方法返回一个当前链表中节点序号fromIndex（含）和toIndex（不含）之间的节点构成的视图。需要特别注意的是，一旦链表添加或删除节点，就会破坏视图的索引，即会影响之前链表subList()方法返回的视图，这个视图将无法再继续被使用（如果继续使用，运行时刻会触发ConcurrentModificationException异常），链表必须用subList()方法重新返回一个新的视图。更改视图的节点（增加或删除节点）或对节点的数据的修改都会使得当前链表发生同步的改变。2024/11/9275.7链表的视图使用视图时，要注意视图中节点和原链表节点的对应关系。原链表list中狮子节点是第1个节点，但在视图listView中狮子节点是第0个节点，原链表list中老虎节点是第2个节点，但在视图listView中老虎节点是第1个节点，原链表list中猎豹节点是第3个节点，但在视图listView中猎豹节点是第2个节点。2024/11/9285.7链表的视图使用视图时，要注意视图中节点和原链表节点的对应关系。如果视图listView增加一个节点，比如尾节点：鬣狗那么原链表list会同步更新、发生变化，猎豹节点和河马节点之间多了一个鬣狗节点：2024/11/9295.7链表的视图例子9Example5_9.java例子9的主类Example5_9使用链表的视图更新链表节点中的天气信息。5.8链表的排序2024/11/930publicdefaultvoidsort(Comparator<?superE>c)方法是List接口的默认排序方法（default关键字修饰的方法），LinkedList继承了该排序方法（去掉了关键字default）。该排序方法的参数c是Comparator泛型接口，Comparator泛型接口是一个函数接口，即此接口中的抽象方法只有一个：intcompare(Ta,Tb)，此方法比较两个参数a和b的顺序，返回值是正数表示a大于b，返回负数表示a小于b,返回零表示a等于b。2024/11/9315.8链表的排序Comparator是一个函数接口，因此在使用该方法时，可以向参数c传递一个Lambda表达式，该Lambda表达式必须是2个参数，Lambda表达式中必须有return语句，返回的值是int型数据（和其代表的intcompare(Ta,Tb)方法保持一致）。例如sort((a,b)->{if(a.height>b.height)return1;elseif(a.height<b.height)return-1;elsereturn0;})

2024/11/9325.8链表的排序例子10Student.java例子10的主类Example5_10分别按学生的数学和英文成绩升序排序链表、降序排序链表。Example5_10.java5.9遍历链表2024/11/933某些集合根据其数据存储结构和所具有的操作也会提供返回数据的方法，例如LinkedList类中的get(intindex)方法将返回当前链表中第index节点中的对象。LinkedList的存储结构不是顺序结构，即节点的物理地址不必是依次相邻的，因此，链表调用get(intindex)方法的速度比顺序存储结构的集合调用get(intindex)方法的速度慢。当用户需要遍历集合中的节点时，应当使用该集合提供的迭代器，而不是让集合本身来遍历其中的节点。2024/11/9345.9遍历链表单向迭代器是从链表的头节点开始，遍历到尾节点。●单向迭代器链表对象可以使用Iterator<E>iterator()方法获取一个实现Iterator接口的对象，该对象就是针对当前链表的单向迭代器。迭代器内部使用了游标技术，单向迭代器的游标的初始状态是指向链表的头节点的前面，如果游标可以向后移动（向链表的尾节点方向），单向迭代器调用hasNext()方法返回true，否则返回false。连续的调用next()方法会将游标移动到尾节点，这时游标将无法向后移动，再调用next()方法否则触发运行异常NoSuchElementException（链表是空链表，直接调用next()方法也会触发运行异常NoSuchElementException）。2024/11/9355.9遍历链表●双向迭代器链表对象可以使用ListIterator<E>listIterator()方法获取一个实现ListIterator接口的对象（ListIterator接口是Iterator的子接口），该对象就是针对当前链表的双向迭代器。双单向迭代器是双游标迭代器，一个向后游标（向链表的尾节点方向），一个向前游标（向链表的头节点方向）。双游标是同时移动，向前游标在向后游标的后面。

初始状态向后游标指向头节点的前面，向前游标指向头节点。2024/11/9365.9遍历链表●遍历与更新迭代器对链表实施的添加、删除、更新节点等操作一直等到迭代器遍历链表完毕再生效。双向迭代器调用next()或previous()方法返回节点中的数据后，迭代器紧接着调用add(Eobj)方法，可以在该节点后插入一个节点（新节点序号从当前节点开始递增），调用set(Eobj)方法可以更新该节点中的数据，调用remove()方法可以删除该节点。单向迭代器在遍历链表时也可以同时更新链表，但只能删除节点。单向迭代器调用next()方法返回节点中的数据后，迭代器紧接着调用remove()方法可以删除该节点。2024/11/9375.9遍历链表●遍历与锁定单向或双向迭代器在遍历链表时，将不允许链表本身调用方法更改链表节点的结构。单向或双向迭代器在遍历链表时，将不允许链表本身调用方法更改链表节点的结构，即不允许链表调用方法增加节点、删除节点、排序链表，但允许链表调用set(intindex，Eobj)方法更新节点中的数据，因为更新节点只是更新链表的节点中的数据，不属于更改链表的节点的结构。

在迭代器没有结束遍历之前，如果链表进行增加节点、删除节点、排序链表这些操作，程序运行时（无编译错误）将触发java.util.ConcurrentModificationException异常。程序必须等到迭代器被使用完毕，才允许链表调用add()、remove()方法添加、删除节点或排序链表。2024/11/9385.9遍历链表●for-each语句链表获得迭代器后，在使用迭代器之前又对链表进行了更新，比如添加、删除或排序链表，那么就无法再使用该迭代器遍历链表。如果想使用迭代器，就必须让链表重新返回一个新的迭代器。使用for-each语句遍历一个链表时，禁止当前链表调用add()、remove()方法添加、删除节点或排序链表，其原因是，for-each算法的内部中启用了迭代器。2024/11/9395.9遍历链表例子11例子11的主类Example5_11分别使用单向迭代器和双向迭代器遍历了链表，在遍历的过程中也更新了链表。Example5_11.java2024/11/9405.9遍历链表例子12约瑟夫问题（也称围圈留一问题）：若干个人围成一圈，从某个人开始顺时针（或逆时针）数到第3个人，该人从圈中退出，然后继续顺时针（或逆时针）数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的一个人。Example5_12.javaLeaveOneAround.java这里例子12中的LeaveOneAround类的leaveOne(LinkedList<Integer>people)方法通过遍历链表，解决约瑟夫问题：在遍历链表的过程中删除相应的节点模拟出圈的人。2024/11/9415.9遍历链表例子13一个遍历链表的方法（算法）在遍历链表时，让链表的每个节点中的对象参与某种运算，并输出运算后的结果，称这样的遍历方法为动态遍历方法。Example5_13.java●动态遍历publicdefaultvoidforEachRemaining(Consumer<?superE>action)方法是Iterator接口中的默认方法，链表返回的迭代器（单向或双向）可以使用该方法动态的遍历链表。此方法的参数类型是Consumer函数接口，该接口中的抽象方法voidaccept(Tt)的返回类型是void型。那么在调用此方法时，可以将一个Lambda表达式传递给action。2024/11/9425.9遍历链表例子14Example5_14.java●动态遍历例子14的主类Example5_14动态遍历节点中是数组的一个链表，在遍历这个链表时，让节点中的数组参与运算，计算数组的元素值之和.链表的节点中可以是任何引用型的数据，例如类，数组，接口等类型的数据。第6章顺序表与ArrayList类2024/11/9436.1顺序表的特点2024/11/944顺序表也是线性表的一种具体体现，顺序表节点形成的逻辑结构是线性结构、节点的存储结构是顺序存储，即节点的物理地址是依次相邻的。2024/11/9456.1顺序表的特点顺序表使用数组来实现，顺序表的节点的物理地址是依次相邻的，因此可以随机访问任何一个节点，不必从头节点计数查找其它节点。●查询节点

2024/11/9466.1顺序表的特点和链表不同，顺序表没有单独添加头节点的操作，但是有添加尾节点的操作。●添加节点

2024/11/9476.1顺序表的特点

●删除节点

6.2创建顺序表2024/11/948顺序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型类所实现。2024/11/9496.2创建顺序表ArrayList<E>泛型类的实列使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。ArrayList<E>泛型类实现了Java集合框架中的List泛型接口(和链表不同，没有实现Queue泛型接口)。ArrayList<E>泛型类继承了List泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List泛型接口中的抽象方法。2024/11/9506.2创建顺序表顺序表可以使用add(Eobj)方法向顺序表依次增加节点。创建空顺序表，使用ArrayList<E>泛型类声明顺序表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定顺序表中节点（对象）的类型。例如，指定E是String类型：ArrayList<String>arrlistOne=newArrayList<>();或ArrayList<String>arrlistOne=newArrayList<String>();例子1Example6_1.java例子1中的主类Example6_1中首先创建一个空顺序表arrlistOne，然后向空链表arrlistOne添加3个节点，随后再用arrlistOne中的节点创建顺序表arrlistTwo。修改arrlistTwo的节点，并不影响arrlistOne的节点.6.3顺序表常用方法2024/11/951voidadd(intindex,Ee)向顺序表的index指定位置添加一个新的节点e（时间复杂度O(n)）。publicbooleancontains(Objectobj)判断顺序表中是否有对象obj，如果有节点是对象obj返回true，否则返回false(时间复杂度O(n))。

Eremove(intindex)返回顺序表的第index节点，并删除顺序表的第index节点（时间复杂度O(n)）。booleanremove(Objecto)删除顺序表中首次出现是obj的节点，删除成功返回true，否则返回false（时间复杂度O(n)）。2024/11/9526.3

顺序表常用方法例子2Example6_2.java例子2中的主类Example6_2中比较了顺序表的get(intindex)方法和链表的get(intindex)方法的运行耗时，可以看出顺序表的耗时明显小于链表的耗时。2024/11/9536.3顺序表常用方法例子3Example6_3.java例子3的主类Example6_3使用了顺序表的一些常用方法.booleanremoveIf(Predicate<?superE>filter)删除满足filter给出的条件的全部节点（时间复杂度O(n)）。Predicate是一个函数接口，其中唯一的抽象方法是booleantest(Tt)，在使用removeIf(Predicate<?superE>filter)方法时，可以将一个Lambda表达式传递给参数filter，该Lambda表达式的有一个参数，类型和节点类型一致，Lambda表达式的返回值类型是boolean型。6.4遍历顺序表2024/11/954ArrayList的存储结构是顺序结构，即节点的物理地址是依次相邻的，因此，顺序表完全可以调用get(intindex)方法来遍历节点。迭代器分单向迭代器和双向迭代器，对于线性表，单向迭代器只能向尾节点方向依次遍历节点（称向后遍历），双向迭代器可以向尾节点方向依次遍历节点，也可以向头节点方向依次遍历节点（称向前遍历）。有关向迭代器和双向迭代器的详细知识点参看第5章的5.9节。2024/11/9556.4遍历顺序表例子4Example6_4.java例子4中的主类Example6_4中使用双向迭代器遍历一个顺序表，该顺序表的每个节点是一个小写英文字母。双向迭代器在遍历节点的过程中，动态添加新的节点，当向后遍历时（尾部节点方向），在当节点的遍历方向的前面（尾节点方向）依次插入2个新节点，一个新节点是当前节点的ASCII的值（即在UNICODE表中的顺序位置），另一个新节点是当前节点的大写字母。2024/11/9566.4遍历顺序表例子5Example6_5.javaArrayList类提供的publicvoidforEach(Consumer<?superE>action)方法的参数类型是Consumer函数接口，该接口中的抽象方法voidaccept(Tt)的返回类型是void型。那么在调用forEach(Consumer<?superE>action)方法时，可以将一个Lambda表达式传递给action例子5的主类Example6_5动态遍历节点是Integer对象的一个顺序表，在遍历这个顺序表时，让节点Integer对象参与运算，输出Integer对象的二进制、八进制和十六进制。6.5顺序表与筛选法2024/11/957筛法的算法从2开始：2是素数，把素数2保存，然后把2后面所有能被2整除的数都划去。数字2后面第1个没划去的数是素数3，把素数3保存，然后再把3后面所有能被3整除的数都划去。3后面第1个没划去的数是素数5，把素数5保存，然后再把5后面所有能被5整除的数都划去。……按照筛法，每次留下的数字中的第1个数字一定是素数，如此继续进行，就会把不超过N的全部合数都筛掉，保存的就是不超过N的全部素数。2024/11/9586.5顺序表与筛选法例子6PrimeFilter.java

Example6_6.java

例子6主类Example6_6使用ArrayList<Integer>primeFilter(intn)方法输出200内的全部素数，以及200以内孪生素数。6.6顺序表与全排列2024/11/959

2024/11/9606.6顺序表与全排列例子7FullPermutatio.javaExample6_7.java

●递归法求全排列2024/11/9616.6顺序表与全排列例子8Example6_8.java●数字填空

例子8中的主类Example6_8，使用全排列的办法给出了所有满足九宫格填数字要求的8种方案。如果考虑旋转、镜像相同的属于同一种，那么这8种方案都是一样的。

2024/11/9626.6顺序表与全排列●迭代法求全排列对于字符1，2，3，5，6，7，8组成的全排列，按字典序，最小的是12345678，最大的是87654321。从最小的全排列（或最大的全排列）开始，按着字典序依次寻找下一个全排列，一直到找到最大的（最小的）全排列为止，就可以给出全部的全排列。这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。①寻找正序相邻对在全排列的相邻对中找到最后一对“正序相邻对”（小的在前、大的在后）。2024/11/9636.6顺序表与全排列●迭代法求全排列这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。②寻找最小字符

对于：58，找到的字符是6。字符6以后的字符（假如有的话）都比字符5小2024/11/9646.6顺序表与全排列这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。③最小字符与pairLast的首字符互换

2024/11/9656.6顺序表与全排列34587621的下一个全排列：34612578。④反转子序列

例子9DictionaryPermutatio.javaExample6_9.java6.7顺序表与组合2024/11/966

2024/11/9676.7顺序表与组合●迭代求组合和排列不同，[1,2,3]和[1,3,2]是不同的排列，是相同的组合。因此，表示组合时可以让组合里的数字都是升序的。

该组合中的每个数，按顺序存放到一个顺序表list中。

得到下一个组合[1,4,5]2024/11/9686.7顺序表与组合●迭代求组合例子10Combination.javaExample6_10.java例子10中Combination类的方法C(intn,intr,List<Integer>start)返回组合start的下一个组合.例子10中的主类Example6_10使用Combination类的方法输出从7个数中取5个数的全部组合.2024/11/9696.7顺序表与组合●递归求组合例子11RecurrenceCom.javaExample6_11.java参考递归求杨辉三角形（见第3章例子9），可以写出递归求组合的算法（作者反复画递归图，找出了递归的规律，见RecurrenceCom类.

2024/11/9706.7顺序表与组合●组合与砝码称重例子12Weight.javaExample6_12.java有n多个重量不同的砝码各一枚，比如，4个重量不同的砝码：1克，3克，5克和8克。能称出多少种重量。有些组合可能称出相同的重量，比如用一个5克的砝码可以称出5克重量，用1个2克砝码和1个3克砝码，同样也可以称出5克重量。遍历全部的组合，发现能称出相同的重量的组合（即方案）时，保留一个即可。

如果允许砝码放在天秤的两端（允许放在被称重的物体一端），那么就把另一端（被称重的物体一端）的砝码拿回到放置砝码的一端、并变成“负码”（重量是负数），就将问题转化为砝码只放天秤一端的情况。6.8顺序表与记录2024/11/971有时候，需要将一维数组，比如一个记录学生成绩的一维数组，看作一个整体，称作一条记录（如果学过数据库，相当于表中的一条记录）。借助顺序表，可以批量处理记录，比如，排序纪录。2024/11/9726.8顺序表与记录●顺序表与一维数组例子13Example6_13.javaArrays类的静态方法：static<T>List<T>asList(T...a)返回一个顺序表。该方法是可变参数，可以把若干个类型相同的对象放入一个顺序表，也可以把一个数组放入一个顺序表。顺序表调用public<T>T[]toArray(T