本篇文章给大家带来的内容是关于python实现有序字典的详细介绍（附代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
对于一个能够保存键值插入顺序的字典，是如何实现的？
主要有两点：
一个双向链表，用来记录字典的键值的插入顺序
一个键和链表节点的映射，主要用来删除键的时候，找到键对应的节点
python代码实现
class Link:
__slots__ = 'prev', 'next', 'key'
class OrderDict:
def __init__(self):
self.root = Link()
self.map = {}
self._node_map = {}
self.root.next = self.root
self.root.prev = self.root
def __setitem__(self, key, value):
if key in self._node_map:
self.map[key] = value
else:
root = self.root
last = root.prev
link = Link()
link.prev, link.next, link.key = last, root, key
last.next = link
root.prev = link
self._node_map[key] = link
self.map[key] = value
def __getitem__(self, item):
return self.map[item]
def __delitem__(self, key):
del self.map[key]
link = self._node_map.pop(key)
link_prev, link_next = link.prev, link.next
link_prev.next, link_next.prev = link_next, link_prev
link.prev, link.next = None, None
def pop(self):
"""
LIFO
:return:
"""
if not self._node_map:
raise KeyError('dict is empty')
root = self.root
link = root.prev
link_prev = link.prev
link_prev.next = root
root.prev = link_prev
link.prev, link.next = None, None
self._node_map.pop(link.key)
return self.map.pop(link.key)
def __iter__(self):
root = self.root
curr = root.next
while curr != root:
yield curr.key
curr = curr.next
def values(self):
root = self.root
curr = root.next
while curr != root:
yield self.map[curr.key]
curr = curr.next
def __str__(self):
root = self.root
curr = root.next
out = []
while curr != root:
out.append((curr.key, self.map[curr.key]))
curr = curr.next
return str(out)
if __name__ == '__main__':
d = OrderDict()
d['a'] = '1'
d['b'] = '2'
d['c'] = 'c'
print(d)
【相关推荐：python教程】
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
