1 问题
链表跟数组类似，也是一个有序集合。但他们的区别在于，创建数组时需要分配一大块内存用来存储元素，而链表中的元素在内存分配上是相互独立的，元素与元素之间是通过指针或者引用连接起来的。此次实验用单链表实现栈。
2 方法
- 创建节点： _Node 类的构造函数是为了方便而设计，它允许为每个新创建的节点赋值。 由于 python 没有指针，因此一般使用类的结构实现指向关系。
- 在链表的头部插入/删除元素： 只有在链表头部才能实现有效插入和删除元素。 为避免每次返回栈的大小时，必须遍历整个列表，因此定义一个变量_size持续追踪当前元素的数量。
- 元素压栈： 当栈顶插入新元素时，调用_Node类来完成链接结构的改变。
代码清单 1
代码语言：text复制class LinkedStack:
# 创建节点
class _Node:
__slot__='_element','_next'
def __init__(self,element,next):
self._element = element
self._next = next
# 设置栈顶
def __init__(self):
self._head =None
self._size = 0
# 元素压栈
def push(self,e):
self._head = self._Node(e,self._head)
self._size = 1
ls=LinkedStack()
ls.push(1)
ls.push(2)3 结语
相比数组，链表的插入和删除效率更高，对于不需要搜索但变动频繁且无法预知数量上限的数据，更适合用链表。比如，当我们从一个数组中移除第一个元素后，需要将后面的元素在内存中的位置都往前移，这就意味着需要重新进行内存分配和内存布局，因为数组中的元素在内存上是连续的。但是对于链表，我们只需要把 head 指针/引用指向第二个元素就可以了。所以链表更适合用来做栈。
