为什么需要链表？

之前我们用数组存一组整数，写起来很直接，但数组有个天生的“倔强”：它的大小在定义时就固定了。如果事先不知道要存多少数据，就得拍脑袋猜一个最大值；要么浪费内存，要么数据塞不下。而且如果要在数组中间插入或删除一个元素，往往要把后面的元素整体搬家，时间开销较大。

链表就是为了解决这些问题而生的：它不必连续占用内存，插入删除时也不需要搬动大量元素，只要改几个指针的指向即可。代价是，它无法像数组那样随机访问第 i 个元素，查找时需要从头节点一步步走。

学习目标

读完本文后，你将能够：