赞
踩
因为顺序表(此处,也就是数组)的内存空间是连续的,并且存储的数据属于相同数据类型。 因此,我们可以通过数组的“首地址+索引”就能快速的找到数组中对应索引的元素值,从而得出数 组的优点:查找快。
索引操作数组原理:数组首地址 + 存放数据的字节数*索引。
需求:删除数组{11, 22, 33, 44, 55, 66}索引为 2 的元素,删除后的数组为:{11, 22, 44, 55, 66}。
实现步骤:
(1) 把删除索引之后的元素往前挪动一位(从前往后)。
(2) 把数组的最后一个元素设置为默认值。
需求:在数组{11, 22, 44, 55, 66}索引为 2 的位置插入元素 33,插入后的数组为:{11, 22, 33, 44, 55, 66}。
实现步骤:
(1) 先检查数组是否需要扩容。如果数组的空间长度和数组添加元素个数相等,则需做扩容操作。
(2) 把插入索引及其之后的元素往后挪动一位(从后往前挪动)。
(3) 把插入的元素赋值到插入索引的位置中。
优点:无须关心表中元素之间的关系,所以不用增加额外的存储空间;可以根据索引快速地操作表 中任意位置的元素,并且操作任何一个元素的耗时都是一样。
缺点:插入和删除操作需要移动大量元素。使用前需事先分配好内存空间,当线性表长度变化较大 时,难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费,分配的空间过小,难以 适应问题的需求。
单链表采用的是链式存储结构,使用一组地址任意的存储单元来存放数据元素。在单链表中, 存储的每一条数据都是以节点来表示的,每个节点的构成为:元素(存储数据的存储单元) + 指 针(存储下一个节点的地址值),单链表的节点结构如下图所示:
另外,单链表中的开始节点,我们又称之为首节点;单链表中的终端节点,我们又称之为尾节 点。如下图所示:
在线性表中,每个节点都有一个唯一的序号,该序号是从 0 开始递增的。通过序号获取单链表 的节点时,我们需要从单链表的首节点开始,从前往后循环遍历,直到遇到查询序号所对应的节点 时为止。
以下图为例,我们需要获得序号为 2 的节点,那么就需要依次遍历获得“节点 11”和“节点 22”, 然后才能获得序号为 2 的节点,也就是“节点 33”。
因此,在链表中通过序号获得节点的操作效率是非常低的,查询的时间复杂度为 O(n)。
根据序号删除节点的操作,我们首先应该根据序号获得需要删除的节点,然后让“删除节点的 前一个节点”指向“删除节点的后一个节点”,这样就实现了节点的删除操作。
以下图为例,我们需要删除序号为 2 的节点,那么就让“节点 22”指向“节点 44”即可,这样 就删除了序号为 2 的节点,也就是删除了“节点 33”。
通过序号来插入节点,时间主要浪费在找正确的删除位置上,故时间复杂度为 O(n)。但是,单 论删除的操作,也就是无需考虑定位到删除节点的位置,那么删除操作的时间复杂度就是 O(1)。
根据序号插入节点的操作,我们首先应该根据序号找到插入的节点位置,然后让“插入位置的 上一个节点”指向“新插入的节点”,然后再让“新插入的节点”指向“插入位置的节点”,这样 就实现了节点的插入操作。
以下图为例,我们需要在序号为 2 的位置插入元素值“00”,首先先把字符串“00”封装为一 个节点对象,然后就让“节点 22”指向“新节点 00”,最后再让“节点 00”指向“节点 33”,这 样就插入了一个新节点。
通过序号来插入节点,时间主要浪费在找正确的插入位置上,故时间复杂度为 O(n)。但是,单 论插入的操作,也就是无需考虑定位到插入节点的位置,那么插入操作的时间复杂度就是 O(1)。
(1) 存储方式比较:
(2) 时间性能比较:
(3) 空间性能比较:
双链表也叫双向链表,它依旧采用的是链式存储结构。在双链表中,每个节点中都有两个指针, 分别指向直接前驱节点(保存前一个节点的地址值)和直接后继节点(保存后一个节点的地址值), 如下图所示。
所以,从双链表中的任意一个节点开始,都可以很方便地访问它的直接前驱节点和直接后继节 点,如下图所示。
逻辑上没有区别,他们均是完成线性表的内容,主要的区别是结构上的构造有所区别。
(1) 单链表
对于一个节点,有储存数据的 data 和指向下一个节点的 next。也就是说,单链表的遍历操作都 得通过前节点—>后节点。
(2) 双链表
对于一个节点,有储存数据的 data 和指向下一个节点的 next,还有一个指向前一个节点的 pre。 也就是说,双链表不但可以通过前节点—>后节点,还可以通过后节点—>前节点。
环形链表依旧采用的是链式存储结构,它的特点就是设置首节点和尾节点相互指向,从而实现 让整个链表形成一个环。在我们实际开发中,常见的环形链表有:
在单链表中,尾节点的指针指向了首节点,从而整个链表形成一个环,如下图所示:
在双链表中,尾节点的指针指向了首节点,首节点的指针指向了尾节点,从而整个链表形成一 个环,如下图所示:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。