【007-week1】均摊时间复杂度和链式栈的实现

[v1xingyue]

讨论两个知识点。

• 均摊时间复杂度的一个应用

讨论一下golang 中变长数组(切片的实现)。
初始化一定容量 cap (实际空间) 的数组，里边实际的数据长度为len。 当 len 达到 cap 时，会扩展成为2 * cap 的空间, 会形成一个 cap 规模的数据迁移。 也是均摊时间复杂度的一个应用。
一个x 的搬移，会紧跟 x 个复杂度为1 的插入。 所以 均摊时间复杂度为 O(2n) 。

• 一个链式栈的实现:

考虑到栈结构的特殊性，先插入先出。
一般的单链表插入数据，是往尾节点插入数据。出栈操作为移除尾节点，将数据指针前移，因为，为单链表，则需要从头到尾遍历 一遍才可以找到头指针。
或者把单链表改成多链表。但是，改成双链表，又会增加一些操作复杂度。

所以考虑从头部插入数据的方法来实现操作，每次插入数据，生成一个新的节点作为链表的头结点。 头结点的next 指针指向原来的头结点。

[HongChao6]

标题看着好难受啊，能把【 加上么

[tolookme]

理论联系实践！