关于链表remove 时间复制度问题

[liyuanzhou92]

你好，
对于链表remove时间复杂度有些疑问
我认为无论是单链表、双链表，删除一个元素的时间复杂度都是O(n)，因为都需要遍历整个链表；
删除一个node时间复杂度都是O(1)，因为都只需要将前后两个node相连，
为什么lru_cache 不用单链表要用双链表呢？

[PegasusWang]

对于单链表或者双链表，这里如果需要查找节点的话删除的复杂度都是 O(n)的，因为你只能从头到尾顺序查找。但是对于双链表，如果已经知道了一个节点的情况下，你就可以直接通过连接该节点前后节点的方式使用O(1)的方式删除该节点了。在 lru_cache里，你要删除一个节点的时候是知道这个节点值的，所以可以直接用O(1)的时间删除，并不需要从头到位查找这个节点。