了解链接列表操作的时间复杂性对于评价其效率至关重要,本条对共同链接列表操作及其计算成本进行了明确,分步分析.

基本业务及其复杂性

链接到的列表操作包括插入,删除,以及转录. 每一个操作的时间复杂度取决于列表是单项还是双项链接,以及是否知道操作的位置.

插入操作

在链接列表开头插入节点需要持续的时间, [[FLT: 0]] O(1) [[FLT: 1]],因为它涉及更新几个指针。 然而,在某个特定位置插入该列表需要将列表转换到该位置, 需要线性时间, [[FLT: 2] O(n) ]。

删除操作

删除第一个节点是 O(1)操作,因为它只涉及指针更新. 在特定位置删除一个节点需要向该节点转弯,从而产生 O(n)的复杂性.

逆向搜索

拖动链接列表寻找特定元素或到达端点需要访问每个节点一次,导致线性时间复杂性为O(n).

  • 头部插入: O(1)
  • 位置插入: O(n)
  • 头部删除: O(1)
  • 删除位置: O(n)]
  • 倾斜/搜索:O(n)