第 3 章《链表》勘误

21 页

表 3-1 中, listSetDupMethodlistGetDupMethodlistSetFreeMethodlistGetFreelistSetMatchMethodlistGetMatchMethod 这三组函数关于时间复杂度的描述有误, 以下是修正后的表格:

函数

作用

时间复杂度

listSetDupMethod

将给定的函数设置为链表的节点值复制函数。

O(1)

listGetDupMethod

返回链表当前正在使用的节点值复制函数。

复制函数可以通过链表的 dup 属性直接获得, O(1)

listSetFreeMethod

将给定的函数设置为链表的节点值释放函数。

O(1)

listGetFree

返回链表当前正在使用的节点值释放函数。

释放函数可以通过链表的 free 属性直接获得, O(1)

listSetMatchMethod

将给定的函数设置为链表的节点值对比函数。

O(1)

listGetMatchMethod

返回链表当前正在使用的节点值对比函数。

对比函数可以通过链表的 match 属性直接获得, O(1)

感谢 袁文清 反馈这个错误。

22 页

表 3-1 中, listDelNode 的复杂度应该为 O(1) 而不是 O(N) , 以下是修正之后的表格:

函数

作用

时间复杂度

listDelNode

从链表中删除给定节点。

O(1)

感谢 skycpp 反馈这个问题。