对于一个能够保存键值插入顺序的字典，是如何实现的？
主要有两点：
一个双向链表，用来记录字典的键值的插入顺序
一个键和链表节点的映射，主要用来删除键的时候，找到键对应的节点
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)