对于大量的输入数据，链表的线性访问时间太慢，不宜使用。

链表

基本概念

• A linked list consists of a sequence of links.

• Each link (also called a node) stores
• data（储存的对象）
• link to the next node（对下一个节点的引用）

• The main problem with arrays is that in order to move an item from one slot to another it has to be copied, pasted and deleted, which is time-consuming and wastes space.
• Linked lists avoid all of these problems because they can adapt their ordering by changing the items they point to.
• 向链表插入或删除一项的操作不需要移动很多的项，而只涉及常数个节点链的改变。

从链表中删除

向链表插入

双链表

基本概念

• 在经典的链表中，每个节点均存储到其下一节点的链，而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息。
• 删除最后一项比较复杂，因为必须找出指向最后节点的项，把它的 next 链改成 null，然后再更新持有最后节点的链。

• 双向链表的一个节点有两个方向，分别储存当前节点的前驱节点和后续节点。节点的删除只需要指定前驱节点，或者后续节点就可以进行删除操作；但是缺点也很明显，每次添加节点时都需要 2 个指向，额外增加了内存空间消耗。

算法应用

合并两个有序链表

Leetcode 21 & 2022 CS211 Final Exam