前情回顾
我们已经实现了单向链表的创建、向链表 push 数据，顺便实现了检查链表是否为空的工具函数。
create_chain() -> chain_entry
push_chain(chain, data)
is_chain_empty(chain) -> data
关于节点的所有函数，都只能由链表相关的函数调用，否则可能造成链表的 entry 数据错误。
最后一击
今天我们要完成单向链表的最后一个关键功能：删除。与插入的时候类似，我们还是针对链表的第一个元素删除，这样的效率最高。我们会将链表的第一个节点从链表中剔除，并将其数据返回给调用者。
我们同样考虑 chain_entry、第一、第二节点的情况。
为了将 first_node 从链表中剔除，实际上只要将 first_node 与 chain_entry 和 second_node 之间的联系断掉，并将 second_node 设置为 chain_entry 的下一节点即可：
- chain_entry 的下一节点设置为 second_node。
- first_node 的 next_node 设置为 None，断开其与 second_node 之间的关联。
步骤二不是必须的，但是，当一个节点与链表脱离的时候，最好将其与其他有效节点之间的所有连接断开，避免之后错误的将这个自由节点当作有效节点，误操作链上数据。
另外一个特别注意的点是，如果单向链表已经是空的，没有任何元素，就应当直接退出函数，而不是尝试对 None 进行节点操作。
下面是所有代码，注意 pop_chain 是新增的函数，实现非常简单：
#encoding=utf-8
def create_node(data = None, next = None):
return {'data' : data, 'next' : next}
def set_next_node(cur_node, next_node):
cur_node['next'] = next_node
# 顺便实现获取下一个节点的函数
def get_next_node(cur_node):
return cur_node['next']
def create_chain():
entry = create_node() # 默认 data 是 None，所以不填参数也可以
# 为了方便，我们为 entry 增加一个 length 字段，保存链表的长度，刚开始是 0
entry['length'] = 0
return entry
# 获取链表长度
def get_chain_length(entry):
return entry['length']
# 链表是否为空
def is_chain_empty(entry):
return get_chain_length(entry) == 0
# 获取节点数据
def get_node_data(node):
return node['data']
# 向链表增加数据
def push_chain(entry, data):
new_node = create_node(data)
# 为了清晰，我们单独把第一个节点保存在 first_node
first_node = get_next_node(entry)
set_next_node(new_node, first_node)
set_next_node(entry, new_node)
# 别忘了增加链表节点计数
entry['length'] += 1
# 从链表头部弹出数据
def pop_chain(entry):
if is_chain_empty(entry):
return None
head = entry
first_node = get_next_node(head)
second_node = get_next_node(first_node)
set_next_node(entry, second_node)
set_next_node(first_node, None)
# 切记，更新链表长度
entry['length'] -= 1
return first_node['data']
# 遍历链表，便于我们查看链表内容
def chain_all(entry):
node = entry
while get_next_node(node):
node = get_next_node(node)
print(get_node_data(node))
# 一段简单的测试，
chain = create_chain()
push_chain(chain, "hello")
push_chain(chain, "world")
push_chain(chain, "!")
print("length: {}".format(get_chain_length(chain)))
print("all chain nodes data:")
chain_all(chain)
# 下面是对弹出数据的测试
print("now pop data!")
while not is_chain_empty(chain):
data = pop_chain(chain)
print('----pop node data: {}-----'.format(data))
print('****see the chain nodes ******')
chain_all(chain)
百闻不如一见，百见不如动手！自己试试看！
总结
Python 实现链表，只是为了练习 Python 的基本用法，为了照顾初学者，这里没有用到面向对象特性。
有同学会问，是不是后面要用到链表，就这样实现呢？不是的。基本的链表等数据结构不需要自行实现，包括其他高级数据结构和算法，绝大多数情况下，都有第三方实现，或者语言本身就提供了支持。实际应用中，要尽量使用知名的第三方库，只要仔细阅读它的使用文档，就可以保证不会出重大错误。不重复造轮子，站在巨人的肩膀上，是编程的诀窍之一。
有了这几节的基础，下一节，我会快速的给出一种使用面向对象的实现，你只需要熟悉基本的 class 用法和面向对象概念就可以看懂。你会发现面向对象是对面向过程的高层次抽象，内在里有千丝万缕的练习，面向对象也没有想象的那么难以理解，反而能为我们提供不少便利。
