深入分析序列表和链表的Java数据结构和算法

接下来，让我们分析序列表的实现，首先声明一个序列表接口类SeqList，然后实现该接口并实现该接口方法的代码. SeqList接口代码如下:

我们创建一个ArraySeqList序列表来实现此接口.

私有最终对象[] EMPTY_ELEMENTDATA = {};

私有最终对象[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private静态最终int DEFAULT_CAPACITY = 10;

/ *** *元素数量* /

私有整数大小；

构造ArraySeqList的方法

没有参数构造方法，我们默认为空数组. 在参数构造方法中，我们创建了一个新的大小为空的空数组.

获取（int索引）分析

从序列表中获取值是一个相当简单的操作并且非常有效. 这是因为序列表使用数组作为存储数据的容器. 因此，只要传递索引值，然后直接获取数组中对应的索引值，代码实现如下:

设置（int索引，T数据）分析

替换序列表中的值也非常有效和简单. 只需根据传递的索引值找到要替换的元素，然后用传递的数据值替换相应的元素值. 代码如下:

分析加法（int索引，T数据）和加法（T数据）

在序列表中执行插入操作时，如果其内部数组的容量未达到最大值，则可以归结为两种情况: 一种是在头部或中间插入，在这种情况下，则需要移动阵列. 在数据元素中，效率很低；另一种是插入尾部，而不移动数组中的元素，效率很高.

但是，当序列表内部数组的容量达到最大值并且无法插入时，您需要申请另一个更大的数组并将所有数组元素复制到新数组. 这种时间和空间开销相对较大. 这会导致效率甚至更低.

因此，在频繁插入的情况下，序列表的插入操作不是理想的选择. 下面是当阵列容量足够时（在尾部插入相对简单，将不进行演示）在头或中部插入序列表的:

在头部或中间具有足够阵列容量的序列表插入操作的

当阵列容量不足时，在头部或中间插入序列表的操作

理解了上述序列表的插入操作之后，我们使用代码来实现插入操作，如下所示.

每次插入元素之前，我们都要判断数组是否足够. 如果数组的长度足够，请将index之后的元素向右移动一，然后将新元素添加到index位置. 元素数大小++

当数组的长度不够，并且元素数大于当前数组的长度时，我们应该扩展数组. 代码如下:

删除（int索引）实施分析

序列表的删除操作类似于先前的插入操作. 如果序列表中的元素在中间或开头删除，则删除位置之后的元素必须按顺序向前移动，这样效率较低. 如果直接在序列表的末尾将其删除，则无需移动元素，在这种情况下，删除效率很高. 如下图所示，在序列表中删除元素ai时，ai之后的元素将向前移动:

删除操作的代码如下:

删除（E e）实施分析

根据序列表中的数据查找要删除的数据元素与先前根据索引删除的序列表中的数据元素相同，因此我们只需要找到等于data的数据元素通过比较并获得以下Mark，然后调用上面实现的remove（int索引）方法进行删除. 该代码实现如下:

源代码实现: 源代码

数组的访问操作可以在恒定的时间内完成，即序列表的访问操作（获取和修改元素值）的时间为O（1）.

对于在序列表中插入或删除元素，就效率而言，这不是理想的选择. 由于插入或删除操作基于位置，因此您需要移动数组中的其他元素，因此序列表的插入或删除操作算法花费的时间主要用于移动元素. 例如，在序列表的开头插入或删除时，效率很差. 如果在前面插入或删除，则需要移动n个元素（此处假定长度为n个）；如果最后插入或删除，则需要移动的元素为0. 这里我们假设插入或删除值为第i个（0）.

也就是说，在概率相等的情况下，平均插入或删除序列表的元素需要将序列表的全部元素移动一半，其时间复杂度为O（n）. 当然，如果在插入过程中内部阵列容量不足，还会导致其他成本，例如复制元素的时间成本和创建新阵列的空间成本.

因此，一般来讲，序列表具有以下优点和缺点:

好处

将数组用作内部容器既简单又易于使用；

高效访问元素；

数组的特征是存储空间的局部性. 由于它们被定义为连续的存储块，因此任何元素及其相邻元素在物理地址上也是相邻的.

缺点

内部阵列的大小是静态的，使用前必须指定大小，如果容量不足，则需要动态扩展内部阵列的大小，这会导致额外的时间和空间开销

在内部创建数组时，提供了一个连续的空格块. 当规模较大时，可能无法分配数组所需的内存空间

序列表的插入和删除是基于位置的操作. 如果需要在数组的指定位置插入或删除元素，则可能需要移动内部数组中的其他元素，这将导致更大的时间开销和时间复杂度. 对于O（n）

通过对线性序列表的先前分析，我们知道在创建序列表时，必须分配连续的内存存储空间，并且当序列表的内部数组的容量不足时，必须创建一个new数组，然后将原来的元素复制到新数组中，这将浪费大量时间. 在插入或删除元素时，您可能需要移动数组中的元素，这也会占用一定的时间.

由于这些原因，链接列表出现了. 链表在初始化期间仅需要分配一个存储空间元素，并且插入和删除新元素也非常方便. 同时，链表可以是不连续的内存分配，不需要执行任何内存复制和重新分配操作，因此似乎序列表的缺点在链表中已成为优点，实际上，当然也是如此，链表也有缺点，主要是在访问单个元素的时间开销上. 在上面，此问题将在以后进行分析. 让我们首先通过图片了解链表的存储结构，如下所示:

从图中可以看出，线性链表的存储结构是存储具有多个具有分散地址的存储单元的数据元素. 逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元将一个地址指向该字段，并且该地址指向表示其后继位置的字段. 在链接列表中存储数据的单元称为节点. 从图中可以看出，一个节点至少包含一个数据字段和一个地址字段. 数据字段用于存储数据，地址字段用于存储前任或后继. 元素的地址.

正如我们之前所说，插入和删除链接列表非常方便. 这是因为在插入或删除过程中动态地应用和释放了链表中节点的存储空间. 无需事先为单个链表分配存储空间. 因此，避免了由于序列表中存储空间不足而导致的空间扩展和复制元素的过程，提高了操作效率和存储空间利用率.

类似地，让我们首先定义一个顶级链接列表接口: ILinkedList和存储数据的节点类Node. 此类表示最基本的存储单元. 节点代码如下:

接下来是顶层链接列表接口ILinkedList，它声明了我们需要实现的所有方法.

boolean isEmpty（）实现的分析

判断链表是否为空的依据是头节点是否为空. 当head = null时，链表是一个空链表，因此我们只需确定head节点是否为空. isEmpty方法的实现如下:

int length（）实现的分析

要获取链表的长度，我们提供了两种方法. 第一种是添加可变大小并使用它们来记录链接列表的长度.

第二种方法，因此我们只需要遍历整个链表并获取节点数即可获得链表的长度. 要遍历链表，您需要从头节点HeadNode开始. 为了不更改头节点的存储单元，声明变量p指向当前头节点和局部变量长度，然后p开始从头节点访问，并沿着下一个地址链到达后续节点直到最后一个节点一个接一个地增加，长度在每个节点之后增加一个，最后一个长度的大小就是链表的大小. 实现代码如下:

E get（int索引）实现分析

获取单链列表中元素的值是一项耗时的操作. 您需要从头节点开始遍历，直到传入值索引指向的位置为止. 查询和获取值的过程如下图所示:

代码如下:

T集（int索引，T数据）分析

根据传递的索引找到一个值，并将其替换为数据. 其实现过程的原理与get（int index）基本上相同. 找到相应值的位置并将其删除. 您可以查看是否不清楚. 查看之前的get方法图，代码实现直接在此处给出:

添加（int索引，T数据）分析

单个链表插入操作分为四种情况:

a. 在空表中插入一个新节点. 插入语句如下:

head =新节点（x，null）；

b. 在链表的开头插入一个新节点（即链表的开头）. 这时，桌子的头就是头！ = null，因此头后继节点下一个应指向新插入的节点p，而p的后继节点应指向头的原始节点，代码如下:

以上代码可以合并为以下代码:

执行过程如下:

c. 在链接列表的中间插入一个新节点p，您需要在给定的插入位置找到前一个节点，假设该节点位于最前面，然后将front的后继节点更改为指向新节点p，并在同时，新节点p的后继节点指向front的原始后继节点，即front.next，其执行过程如下图所示:

代码实现如下:

d. 在链接列表的末尾插入一个新节点（链接列表的末尾）. 在尾部插入时，还需要在插入的节点P的先前位置处找到该节点的节点前部（假定为前部）. 前端是尾部节点，而尾部节点的下一个指针是更改为指向新节点P. 新节点P的后继指针设置为null. 执行过程如下:

具体代码如下:

T remove（int索引）删除节点实现分析

在单链列表中，根据索引位置删除节点有以下三种情况，删除后返回被删除节点的数据:

a. 删除链表的头（第一个）节点. 此时，您需要删除头部所指向的节点并更新头部节点. 执行图标如下:

代码如下:

b. 删除链接列表的中间节点与添加相同. 您需要找到要删除的节点r的上一个节点的前面（假定为最前面）（假设要删除的节点是r）java带头结点的单链表，然后将front.next指向r.next删除该节点的下一个节点，即执行过程如下:

代码如下:

无效clear（）实现的分析

清空链表很简单，直接清空所有节点. 代码如下:

好的〜，已经分析了添加，删除，获取值，设置替换值以及获取单链表长度的主要方法. 其他未分析的方法相对简单. 这里我们不会一一分析它们. 最终，所有代码都将在github上向所有人共享.

带有头节点的单链表

上面分析的单链列表没有特殊的头节点. 所谓的特殊头节点是没有值的节点，即:

空列表的情况如下:

具有许多头节点的单链接列表有什么优势？通过分析没有前导节点的单链表，我们可以知道链表的插入和删除都需要区分操作位. 例如，插入操作可以分为头部插入和中间或尾部插入. 可以将其视为一种情况），如果头节点没有数据，则单链表的插入和删除不再区分操作位置，即可以将头，中和尾插入视为一种处理这种情况，因为此时头插入和头删除不需要更改头方向，所以头插入如下:

代码如下:

接下来，查看头部的删除:

代码如下:

导线节点的遍历从head.next开始:

因此，不管是插入还是删除，在头节点没有数据之后，在插入或删除时都不需要区分操作位. :

a. 一个空的单链列表只有一个节点，head.next = null.

b. 遍历的起点是p = head.next.

c. 头插入和头删除不需要更改头方向.

同时，为了使链表在尾部插入时更有效，我们可以在链表中添加一个指向尾部的尾部（上面的代码中使用了last）. ），如果我们将节点添加到尾点，则只需通过尾节点后方执行直接操作，而无需从头到尾进行遍历，带有尾节点的单链接列表如下:

直接从尾部插入的代码实现如下:

让我们看一下基于索引插入的代码实现. 由于存在头节点，因此不需要区分操作位的头，中和尾插入.

代码如下:

最后，看一下已删除代码的实现. 由于删除和插入的逻辑与不带前导节点的单链接列表的原理相同，因此在此不再赘述. 我们主要注意遍历的起始节点. 只需更改它即可.

好的〜，这是对前导节点的单链接列表的分析. 实现源代码发布在这里. 同样，稍后将在github上提供. . 下载地址位于文章末尾.

循环单链表

基于上述分析，循环单链表（Circular Single Linked List）相对简单. 所谓的圆形单链表是指链表中最后一个节点的下一个字段，指向头节点. 要形成一个环形结构，我们可以通过插图来理解它:

此时的循环单链接列表具有以下特征:

a. 当循环列表为空列表时，head指向头节点head.next = head.

b. 尾部指向后方以表示最后一个节点，然后是Rear.next = head.

在处理循环单链表时，我们只需要注意避免在遍历循环链表时进入无限循环，也就是说，在确定循环链表是否到达末尾时，先前的判断是如下:

//从head.next开始遍历

节点项目= head.next;

while（item！= null）{

item = item.next;

}

在循环单链列表中更改为以下判断:

节点p =头;

while（p！= head）{

p = p.next;

}

具体的代码实现，有关详细信息，请参见github地址.

找到CircleHeadILinkedList.java文件.

由于单链列表不是随机访问结构，所以即使单链列表在访问第一个节点时花费固定的时间，如果您需要访问第i（0）个，也就是get（i）和set（i，x）的时间复杂度为O（n）.

由于链接列表在插入和删除节点方面非常有效，因此链接列表更适合频繁插入和删除的场景. 如果它是一个单链表，则插入和删除的时间复杂度均为O（n）.

问题在于，在大多数情况下，搜索时间比移动要短得多，并且链表不需要连续的空间或扩展操作，因此即使时间复杂度为O（n），所以链表也是相对而言，更适合于插入和删除操作.

GitHup源地址

参考文章: 序列和链接列表的深入分析.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-171619-1.html