关于链表的设计

Question

波波老师，你好！
学习了链表这一章节，你实现的链表，和很多标准库的链表插入删除元素不同，这些标准库插入或删除指定元素之后的元素，时间复杂度O(1)

C++STL中的单向链表forward_list
insert_after(p,t) 在迭代器p之后的位置插入元素
erase_after§ 删除p指向的位置之后的元素

Go语言双向链表"container/list"包
InsertAfter 将一个值为v的新元素插入到node后面
Remove 删除链表中的元素e,这个方法参数就是我们课程中的node

为什么你设计的链表插入和删除参数都是index，而不是参数node*这样设计？

Answer 1

liuyubobobo 2019-05-18 10:23:19

赞问题！

首先，课程中的数据结构接口的实现，是以Java为参考的，对于Java语言的LinkedList，就没有这样的接口设计，而只是add(int index, E e)。（当然还有addFirst，addLast）

具体为什么这样设计，不同的标准库，就有不同的考量了。这本身是一个设计问题，而不是一个技术问题。

首先，如果接口这样设计，确实，插入和删除是O(1)的，但关键是，找到待插入（或者待删除）的那个位置的节点（或者迭代器），还是O(n)的。所以，对于这样的接口设计，你要想真正插入到你想要的位置，其实还是O(n)。

其次，这样做的缺点，是暴露了Node的内部结构，你可以看到，我们的类设计中，Node是LinkedList的一个内部类，用户无法感知到这个Node的存在，完全不需要关心，这个链表到底是一个单链表，还是双链表，还是循环链表，甚至是更复杂的链表。对用户来说，链表就是一中存储的容器。这样设计，抽象层次更高。

但是你说的C++语言或者Go语言的设计方式，暴露了更多底层接口给用户。我不是说这样不好，但必须承认，这样做，对开发者的要求更高了，因为开发者需要理解更多的底层只是，才可以使用好这个类。同时，这样做，会让开发过程不可避免的更容易产生bug（这本身就是C++最“臭名昭著”的地方），当然，这本质上，和对开发者要求更高，是一回事儿。

当然，这样做也有好处。必须承认，在一些场景中，这个接口是有意义的。能提高某些业务场景的效率。所以，不同的语言采取了不同的设计方案。C++和Go提供这样的接口，相信是因为这两种语言本身，就是面向底层开发的吧：）

继续加油！：）

• 提问者 工头 #1

  非常感谢！