数组仿真链表的优化

在上面的程序中，每次加入一个新值都要在数组当中寻找一个空位来储存数据，这样做会有一个问题，就是当链表中加入了n个元素时，每一次都会用线性的时间复杂度去寻找空位，造成了很大的时间上的浪费，因此需要进行优化（本节内容涉及堆栈的应用，请在学完本书第二章的内容后再研究本节内容）。

用一个堆栈记录所有没有被加入到链表中的数组元素下标，栈的元素可以初始化为1…MAXN-1，以方便使用。每次对链表进行删除操作时，再将删除的数组元素所对应的数组下标入栈，下次再添加新元素进链表时，只需取出栈顶的数组下标即可，因为这个下标对应的数组元素显然是空的。

这个优化方法将O（n）寻找空位的过程直接变成了O（1）。