什么是链表
链表是程序中最常用的数据结构之一。今天我们只用函数，不用对象实现单向链表。
程序处理的数据，很多属于序列，将这些有顺序的数据组织在一起，除了使用连续的数组外，还可以将数据分散储存在不连续的若干区域，并在他们之间建立联系表达先后关系，这就是链表。
常用链表可以分为单向链表和双向链表。我们先了解单向列表。
单向链表
链表中的数据，保存在“链”的一环上，这一环称之为链表的节点：Node。 单向链表，是指一个节点，只能找到下一个节点，但是找不到前一个节点。 怎么理解呢？我们生活中经常会有这样的情况，很多粉丝认识明星，但是明星不一定认识所有的粉丝。这种情况，我们就说，粉丝可以找到明星，但是明星找不到特定的粉丝——不认识！这就是一种典型的单向关系。 每个人都有偶像，这个明星曾经因为某个偶像，走上了艺术道路，偶像又不一定认识这个明星，这又是一个单向关系。 如果将他们三人的关系表示如下图，就是单向链表。
如果我们只认识某粉丝，我们就可以通过粉丝找到明星，再找到明星的偶像（如果明星和偶像都乐意见我们的话）。
单向链表的局限也很明显（我们会在双向链表改进这一局限），如果我们认识明星，是找不到某个粉丝的，因为粉丝太多啦！他根本不认识这些粉丝。
也正因为此，链表的“头”部非常重要，只有从头部，我们才能遍历整个链表。由于单向链表不允许节点知道前一个节点，也就意味着如果从链表中某个节点开始遍历，总会丢失这个节点之前的信息。一定要记住，擒贼先擒王，抓住链表的头部，就抓住了整个单向链表。
节点
刚才我们已经从比较宏观的层面，了解了单向链表的构成，下来我们深入到更细节的层面，看看构成单向链表的基石——节点，是怎样的。
单向链表中的节点，至少需要做到以下工作：
- 保存数据，也就是载荷数据，英文是 payload，这是链表中真正有用的数据。
- 记录下一节点的信息，当然，对于单向链表的最后一个节点，它是没有下一个节点的，这一部分应当为 None。
单向链表的结构看起来应该是这样：
可以看到，一个节点是 数据 和 下一节点++引用++^1^ 的打包。可以再回顾下 Python 的基本数据类型：
- number
- string
- tuple
- list
- dic
- set
共 6 种，其中前三种是不可变类型，后三种是可变类型。理论上 list 和 dic 都可以表示节点的结构：
- node = [data, next]
- node = {'data' : data, 'next' : next}
我们将采用 dic 来表示节点，因为我们可以用 node['data'] 而非 node[0] 来获取其中的数据，可读性更好。
大量的节点中，包含 ‘data’、’next‘ 字符串作为字典的 key，不会消耗内存吗？ 不会，python 对不可变类型数据做了优化，相同的值，实际上是同一个对象的引用。
我们编写第一个函数，用于创建一个节点
def create_node(data = None, next = None):
return {'data' : data, 'next' : next}
如果有多个节点，它们看起来会是这样：
下一节我们再研究，如何将这些节点串联成单向链表。
引用^1^ 在 python 中，所有的变量，都是值的引用。如果有 C/C++ 编程经验的同学，可以将所有的变量理解为 void * 类型，它们都指向对应类型的 对象（python3 中）。所以节点里所谓的“下一个节点的引用”，直接使用下一节点赋值到“下一个节点”就可以了。
