数据结构 | 其二 链表
2018-09-19 本文已影响0人
cengel
2.1 单向链表
单向链表
2.2 双端链表
双端链表
双端链表与单链表的区别在于它不只第一个链结点有引用，还对最后一个链结点有引用
2.3 有序链表
在链表中保持数据有序是很有用的，具有这个特性的链表叫作“有序链表”
通常，有序链表的删除只限于最大值或最小值，不过，有时候也会查找和删除某一特定点，但这种操作对于有序链表来说效率不高
有序链表优于有序数组的地方在于插入的效率更高（不需要像数组那样移动元素），另外链表可以灵活地扩展大小，而数组的大小是固定的。但是这种效率的提高和灵活的优势是以算法的复杂为代价的
2.4 双向链表
传统链表存在着一个潜在的问题，就是没有反向引用，由上一个链结点跳到下一个链结点很容易，而从下一个链结点跳到上一个链结点很困难.
- 优点： 双向链表允许反向查找和遍历
- 缺点： 双向链表的插入和删除会变得更复杂，因为同时要处理双倍的指针变化
双向链表
双向链表示意图.png
