但是需要注意的是，由于我们对链表进行了封装，客户端无法感知到内部节点的存在，因此也就无法获取到内部节点的引用。所以，链表的插入，删除操作其实并不纯粹，而总是会伴随着基于下标的随机访问或者特定元素的查找，这会把大量的时间消耗在遍历查询中。

　　总体来说：

　　1.?链表的增加、删除操作在头部、尾部的执行由于避免了大量的查询，因此效率非常高(时间复杂度为O(1))。但是在链表较为居中位置的执行效率却不尽如人意(时间复杂度为O(n))。

　　2.?链表的随机修改、查询操作，其时间复杂度为O(n)。相比向量，链表随机查询、修改的效率较差。

　　针对链表的上述特性可以发现，许多只在头尾处频繁操作的场合，链表的表现很好，可以考虑通过链表来实现(例如：栈，队列等)。　

6.链表总结

　　到这里，我们已经完成了一个很基础的链表数据结构。虽然比较简单，但已经有一个基本的框架，读者完全可以在理解思路的基础之上进行各个维度的优化。

　　链表作为基础的数据结构之一，其原理是值得学习和了解的。因为，许多算法和高级的数据结构都依赖于链表或者链表的其它变种实现(跳跃表等)；其次链表这种"将数据存放在节点中，并且维护节点之间关系"的设计思想也存在于很多高级数据结构之中(树、图等)，对链表的掌握是理解一些更复杂数据结构的基础。

　　代码在我的 github上：https://github.com/1399852153/DataStructures?，这篇文章还存在许多不足之处，请多指教。

?

?

?

?

?

?

?

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!