【数据结构】双向链表插入操作的时间复杂度分析

用户头像
遇见
关注
发布于: 2020 年 04 月 22 日
【数据结构】双向链表插入操作的时间复杂度分析

假设一个双向链表有以下几个节点信息:

... <-> A <-> B <-> C <-> ...

现在要在节点 B 和节点 C 之前插入一个新的数据 X,变为下面的结构:

... <-> A <-> B <-> X <-> C <-> ...

在指定节点(节点B)后插入数据



可以对这个操作从以下几个步骤进行分析:

  1. 找到节点 B 的插入前的下一个节点,即节点 C

  2. 插入节点 X,将 prev 指针指向节点 B, next 指针指向节点 C

  3. 修改节点 B 的 next 指针指向 X

  4. 修改节点 C 的 prev 指针指向 X

其时间复杂度分别为:

  1. O(1),因为节点 B 已经存储了 节点 C 的位置

  2. O(1)

  3. O(1)

  4. O(1)

相加所得,时间复杂度为 O(1)

在指定节点(节点C)前插入数据



可以对这个操作从以下几个步骤进行分析:

  1. 找到插入前的前一个节点,即节点 B

  2. 插入新节点 X ,设置 prev 指针指向节点 B, 设置 next 指针指向节点 C

  3. 修改节点 B 的 next 指针为节点 X

  4. 修改节点 C 的 prev 指针为节点 X

其时间复杂度为:

  1. O(1),因为在插入之前,节点 C 的 prev 指针指向的就是节点 B 的位置

  2. O(1)

  3. O(1)

  4. O(1)

相加所得, 时间复杂度为 O(1)

在这里要同时注意,如果是单向链表,则时间复杂度为 O(n),分析如下:

由于单向链表的节点中只会存储后一个节点的指针,所以在第 1 步的时候,需要从链表头部遍历来找到:【next 指针指向节点 C 的节点】也就是节点 B,这一步骤的(平均)时间复杂度为O(n),所以单向链表的结构下,时间复杂度:

  1. O(n)

  2. O(1)

  3. O(1)

  4. O(1) 相加所得, O(n)



找到值等于B的节点并插入在其后面



相对于 在指定节点(节点B)后插入数据 的操作来说,多了一个查找定位节点 B 的操作,而等值查找操作在双向链表中的平均时间复杂度为 O(n), 故当前操作的时间复杂度也是 O(n)。

找到值等于C的节点并插入在其前面



相对于 在指定节点(节点C)前插入数据 的操作来说,多了一个查找定位节点 C 的操作,而等值查找操作在双向链表中的平均时间复杂度为 O(n), 故当前操作的时间复杂度也是 O(n)。



发布于: 2020 年 04 月 22 日阅读数: 54
用户头像

遇见

关注

A good code is like a story not a puzzle 2019.08.08 加入

人生是 B 和 D 之间的 C 选择。

评论

发布
暂无评论
【数据结构】双向链表插入操作的时间复杂度分析