单向链表基本操作的时间复杂度分析

添加操作

  • 在链表尾部添加(addLast())需要从头遍历,时间复杂度为O(n)
  • 在链表头部添加(addFirst()),时间复杂度为O(1)
  • 在链表任意位置添加(add(int index,E e)),平均情况下为O(n/2)=O(n)
addLast()
addFirst()
add(int index,E e)

删除操作

  • 删除链表最后一个元素(removeLast()),需要遍历找到最后元素的前一个元素,故时间复杂度为O(n)
  • 删除链表的第一个元素(removeFirst()),时间复杂度为O(1)
  • 删除链表中任意位置节点(remove(index)),平均情况下时间复杂度为O(n/2)=O(n)
removeLast()
removeFirst()
remove(int index)

修改操作

由于链表不支持随机访问,需要从头开始寻找直到找到需要修改的节点,故时间复杂度为O(n)

set(int index,E e)

查找操作

由于链表不支持随机访问,需要从头开始寻找直到找到需要的节点,故时间复杂度为O(n)

get(int index)
contains(E e)

从上不难看出,关于链表的添加操作、删除操作、修改操作、查找操作的时间复杂度均为O(n),但是如果只对链表头进行添加操作、删除操作、查找操作那么它的的时间复杂度为均O(1)。同时在元素的前一个元素已知的情况下,能在 O(1) 时间内删除或者添加元素,当然也取决于是单链表还是双链表,在双链表中,如果已知该元素的后一个元素,同样可以在 O(1) 时间内删除或者添加该元素。