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

... <-> 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)。