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

第5章链表与LinkedList类2024/11/91

5.1链表的特点2024/11/92链表是由若干个节点组成，这些节点形成的逻辑结构是线性结构，节点的存储结构是链式存储，即节点的物理地址不必是依次相邻的。对于单链表，每个结点含有一个数据，并含有下一个节点的引用。对于双链表，每个节点含有一个数据，并含有上一个节点的引用和下一个结点的引用（Java实现的是双链表）

2024/11/935.1链表的特点图示意的是有5个节点的双链表（省略了上一个节点的引用箭头示意）。注意，链表的节点序号是从0开始，每个节点的序号等于它前面的节点的个数。链表中的节点的物理地址不必是相邻的，因此，链表的优点是不需要占用一块连续的内存存储空间。图5.1

2024/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）中的LinkedListE泛型类所实现。

2024/11/9125.2创建链表LinkedListE泛型类实现了Java集合框架中的List和Queue泛型接口。LinkedLisEt泛型类继承了List和Queue泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List和Queue泛型接口中的抽象方法。

2024/11/9135.2创建链表例子1Example5_1.java使用LinkedListE泛型类声明链表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等），即指定链表中节点里的对象的类型。例如，指定E是String类型：LinkedListStringlistOne=newLinkedList();或LinkedListStringlistOne=newLinkedListString();例子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链表添加节