两年前第一次接触数据结构与算法，草草了解过基础后就再也没有碰过它。这篇回忆录是关于链表的，我想写下与链表有关的那些事。
链表是我接触的第二个数据结构（第一个当然是数组）。还记得在高中的机房里，没有事情可做，就用C语言写链表打发时间。记得当时使用链表做的第一个小游戏是贪吃蛇。因为贪吃蛇的蛇是链式结构，所以很自然想到用链表，实际上，也可以用数组来做，不过C语言没有vector，使用原生数组是一件麻烦事。
来谈谈链表这种数据结构本身吧。 在我的印象里，链表是tree的一个特例。 当tree只有左子树或者右子树时，tree就成了一个链表。 而tree又是graph的一个特例（逐渐偏离😛）。 tree是自相似的，所以链表也是自相似的。
自相似是什么意思呢？它是说一个对象由更小规模的自己组成。 举个例子，tree由一个根节点+左右子树（又是tree呢）组成。 一个链表由一个节点+剩余节点构成的链表组成。 简单来讲，就是套娃。
处理自相似结构的最佳工具当然是递归啦，因为递归正是利用问题的自相似结构来求解问题。 而tree和链表天然就是自相似的，有什么理由不用递归来解决呢？ 我很喜欢递归，因为递归的代码总是优雅简洁又极具可读性。 不过递归调用的开销较大，所以通常不会轻易地使用递归，除非问题难以用循环求解， 且呈现出明显的自相似结构，才会使用递归。 tree问题通常使用递归求解，因为用循环来处理较为困难且不具有可读性。 链表问题因为结构简单，可以使用循环求解也可以使用递归，对于容易的问题， 递归并不比循环优雅，所以通常用循环。
实际上递归是归纳法在计算机科学中的应用。（逐渐偏离。。。😛）。如果会归纳法，那么递归只是知识的迁移。 用递归解决问题总是简单易懂的。 举个例子，在链表中查找某个值，只需要： 如果当前节点的值是要查找的值，那么就找到了，返回一个true。 如果链表中没有节点，那么就没找到，返回一个false。 如果当前节点的值不是要查找的值，那么就去剩下的部分找， 对剩下部分构成的链表重复上面的步骤并将对剩下部分执行上面步骤后的结果作为最终结果返回。 链表最常见的实现是将节点用指针或引用串起来的。教材上讲的也是这个。
嗯，到这里，关于链表的回忆就结束了，它不是什么复杂的数据结构，跟数组一样简洁、朴素， 但对于我，它却比其他数据结构更值得回忆。 要说原因的话，我想是我忘不了那些在学校的机房悠闲写代码的美好时刻。