前言
今天我们来分析下链表这种数据结构，因为链表和树这种数据结构有很大关系，也方便为以后分析树这种数据结构打下基础。好的，废话不多说，我准备分五个层次分析
- 先看下collection模块中的有序字典（OrderDict）
- 用代码实现下 单链表，循环单链表，双链表、循环单链表
- 分析下四种链表的优缺点
- 看几道LeetCode 链表题
- 最后分析下OrderDict数据结构的具体分析
OrderDict源码如下
# OrderDict
class OrderedDict(dict):
def __init__(self, *args, **kwds):
# 不能直接添加tuble的参数>1，有的话就抛出异常
if len(args) > 1:
raise TypeError('expected at most 1 arguments, got %d' % len(args))
try:
# 根节点，也就是常说的头节点，这里是不变的
self.__root
except AttributeError:
# 根节点初始化
self.__root = root = [] # sentinel node
# 这里可以看出是个循环双端链表.节点的结构是[PREV, NEXT, KEY]
root[:] = [root, root, None]
self.__map = {}
self.__update(*args, **kwds)
# 这里是对字典赋值的时候调用
def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
# 如果key值不在链表中,在这里我觉得最好用纸画个图，不然有点绕。
if key not in self:
# 向链表中插入新的key 节点
root = self.__root
last = root[0]
# 向链表中插入新的key 节点
last[1] = root[0] = self.__map[key] = [last, root, key]
# 使用继承的dict 功能来来保存key 和对应的value 的映射关系
dict_setitem(self, key, value)
def __delitem__(self, key, dict_delitem=dict.__delitem__):
dict_delitem(self, key)
# 先从映射关系中根据key 找到key节点，然后再删除双端循环列表对应的key 节点
link_prev, link_next, key = self.__map.pop(key)
link_prev[1] = link_next
link_next[0] = link_prev
def __iter__(self):
# 迭代，使用生成器，只需要读取链表的后驱节点，使用生长期的方式节省内存
'od.__iter__() <==> iter(od)'
root = self.__root
curr = root[1]
while curr is not root:
yield curr[2]
curr = curr[1]
def __reversed__(self):
# 翻转链表，只需要读取链表的前驱节点就翻转了，使用生成器的方式节省内存
'od.__reversed__() <==> reversed(od)'
root = self.__root
curr = root[0]
while curr is not root:
yield curr[2]
curr = curr[0]
# 这里借用__map的clear。直接将key，value值全部清除掉，最后在使用dict.clear清除实例
def clear(self):
'od.clear() -> None. Remove all items from od.'
try:
for node in self.__map.itervalues():
del node[:]
root = self.__root
root[:] = [root, root, None]
self.__map.clear()
except AttributeError:
pass
dict.clear(self)
def popitem(self, last=True):
# 这里pop 键值对，当last=True时就pop最后一个节点，当last=False就pop 头节点。最后返回键值对
if not self:
raise KeyError('dictionary is empty')
root = self.__root
if last:
link = root[0]
link_prev = link[0]
link_prev[1] = root
root[0] = link_prev
else:
link = root[1]
link_next = link[1]
root[1] = link_next
link_next[0] = root
key = link[2]
# del 删除对应的键值对， del 删除是不然值 pop删除是会返回删除的值的
del self.__map[key]
value = dict.pop(self, key)
return key, value
# -- the following methods do not depend on the internal structure --
# 返回keys值。注意是list
def keys(self):
'od.keys() -> list of keys in od'
return list(self)
def values(self):
# 这里就是迭代将value值都返回 放到list 中
'od.values() -> list of values in od'
return [self[key] for key in self]
def items(self):
# 这里就是迭代将dict 的键值对返回 放到list 中
'od.items() -> list of (key, value) pairs in od'
return [(key, self[key]) for key in self]
def iterkeys(self):
'od.iterkeys() -> an iterator over the keys in od'
return iter(self)
def itervalues(self):
'od.itervalues -> an iterator over the values in od'
for k in self:
yield self[k]
def iteritems(self):
'od.iteritems -> an iterator over the (key, value) items in od'
for k in self:
yield (k, self[k])
# 更新
def update(*args, **kwds):
'''od.update(E, **F) -> None. Update od from dict/iterable E and F.
If E is a dict instance, does: for k in E: od[k] = E[k]
If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
Or if E is an iterable of items, does: for k, v in E: od[k] = v
In either case, this is followed by: for k, v in F.items(): od[k] = v
'''
if len(args) > 2:
raise TypeError('update() takes at most 2 positional '
'arguments (%d given)' % (len(args),))
elif not args:
raise TypeError('update() takes at least 1 argument (0 given)')
self = args[0]
# Make progressively weaker assumptions about "other"
other = ()
if len(args) == 2:
other = args[1]
# 这边用了好多自省
if isinstance(other, dict):
for key in other:
self[key] = other[key]
elif hasattr(other, 'keys'):
for key in other.keys():
self[key] = other[key]
else:
for key, value in other:
self[key] = value
for key, value in kwds.items():
self[key] = value
# 让子类重写更新而不中断
__update = update # let subclasses override update without breaking __init__
# 标记、该Object 实例在python 中是独一无二的
__marker = object()
# 将key对应的value 值返回
def pop(self, key, default=__marker):
'''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
If key is not found, d is returned if given, otherwise KeyError is raised.
'''
if key in self:
result = self[key]
del self[key]
return result
if default is self.__marker:
raise KeyError(key)
return default
def setdefault(self, key, default=None):
'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
if key in self:
return self[key]
self[key] = default
return default
# 使实例看起来正常
def __repr__(self, _repr_running=None):
'od.__repr__() <==> repr(od)'
if not _repr_running: _repr_running = {}
call_key = id(self), _get_ident()
if call_key in _repr_running:
return '...'
_repr_running[call_key] = 1
try:
if not self:
return '%s()' % (self.__class__.__name__,)
return '%s(%r)' % (self.__class__.__name__, self.items())
finally:
del _repr_running[call_key]
def __reduce__(self):
'Return state information for pickling'
items = [[k, self[k]] for k in self]
inst_dict = vars(self).copy()
for k in vars(OrderedDict()):
inst_dict.pop(k, None)
if inst_dict:
return (self.__class__, (items,), inst_dict)
return self.__class__, (items,)
def copy(self):
'od.copy() -> a shallow copy of od'
return self.__class__(self)
# 这里是使用迭代器的方式添加key,key可变。value不变
@classmethod
def fromkeys(cls, iterable, value=None):
'''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
and values equal to v (which defaults to None).
'''
d = cls()
for key in iterable:
d[key] = value
return d
def __eq__(self, other):
'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
while comparison to a regular mapping is order-insensitive.
'''
if isinstance(other, OrderedDict):
return len(self)==len(other) and self.items() == other.items()
return dict.__eq__(self, other)
def __ne__(self, other):
return not self == other
# -- the following methods are only used in Python 2.7 --
def viewkeys(self):
"od.viewkeys() -> a set-like object providing a view on od's keys"
return KeysView(self)
def viewvalues(self):
"od.viewvalues() -> an object providing a view on od's values"
return ValuesView(self)
def viewitems(self):
"od.viewitems() -> a set-like object providing a view on od's items"
return ItemsView(self)在此之前并不知道他做了什么，只知道他继承了dict，那么查找删除的时间复杂度应该就是O(1)还有是一个循环双端链表，那么我们先复习下
- 单链表
- 循环单链表
- 双链表
- 循环双端链表
单链表
# 单链表 singlyLinkedList.py
# 1. 单链表的插入、删除、查找操作
# 2. 链表中存储的数据类型是Int
class Node(object):
"""
链表结构的Node节点
"""
def __init__(self, data, next_node=None):
"""
Node 节点的初始化方法
:param data:参数的数据
:param next_node: 下一个Node节点的引用地址
"""
self.__data = data
self.__next = next_node
@property
def data(self):
"""
Node节点存储数据的获取
:return: 当前Node节点的数据
"""
return self.__data
@data.setter
def data(self, data):
"""
Node 节点存储数据的设置方法
:param data:新的存储数据
:return:
"""
self.__data = data
@property
def next_node(self):
"""
获取Node节点的next指针值
:return: next指针数据
"""
return self.__next
@next_node.setter
def next_node(self, next_node):
"""
Node节点next指针的修改方法
:param next_node:新的下一个Node节点的引用
:return:
"""
self.__next = next_node
class SinglyLinkedList(object):
"""
单向链表
"""
def __init__(self):
"""
单向列表的初始化方法===头节点
"""
self.__head = None
def find_by_value(self, value):
"""
按照数据值在单向列表中查找
:param value: 查找的数据
:return:Node
"""
node = self.__head
while (node is not None) and (node.data != value):
node = node.next_node
return node
def find_by_index(self, index):
"""
按照索引值在列表中查找
:param index: 索引值
:return: Node
"""
node = self.__head
pos = 0
while (node is not None) and (pos != index):
node = node.next_node
pos += 1
return node
def insert_to_head(self, value):
"""
在链表的头部插入一个存储value数值的Node节点
:param value:将要存储的数据
:return:
"""
node = Node(value)
node.next_node = self.__head
self.__head = node
return node
def insert_after(self, node, value):
"""
在链表的某个指定Node节点之后插入一个存储value数据的Node节点
:param node:指定的一个Node节点
:param value:将要存储在新的Node节点中的数据
:return:
"""
if node is None: # 如果指定在一个空节点之后插入数据节点，则什么都不做
return
new_node = Node(value)
new_node.next_node = node.next_node
node.next_node = new_node
return new_node
def insert_before(self, node, value):
"""
在连败哦中的某个指定Node节点之前插入一个存储value 数据的Node节点
:param node: 指定的一个Node节点
:param value: 将要存储在新的Node节点中的数据
:return:
"""
if (node is None) or (self.__head is None): # 如果指定在一个空节点之前或者空链表之前插入数据节点，则什么都不做
return
if node == self.__head: # 如果是在链表头之前插入数据节点，则直接插入
self.insert_to_head(value)
return
new_node = Node(value)
pro = self.__head
not_found = False # 如果在整个链表中都没有找到指定插入的Node节点，则该标记为True
while pro.next_node != node: # 寻找指定Node之前的一个Node
if pro.next_node is None: # 如果已经到了链表的最后一个节点，则表明该链表中没有找到指定插入的Node节点
not_found = True
break
else:
pro = pro.next_node
if not not_found:
pro.next_node = new_node
new_node.next_node = node
def delete_by_node(self, node):
"""在链表中删除指定Node的节点.
参数:
node:指定的Node节点
"""
if self.__head is None: # 如果链表是空的，则什么都不做
return
if node == self.__head: # 如果指定删除的Node节点是链表的头节点
self.__head = node.next_node
return
pro = self.__head
not_found = False # 如果在整个链表中都没有找到指定删除的Node节点，则该标记量设置为True
while pro.next_node != node:
if pro.next_node is None: # 如果已经到链表的最后一个节点，则表明该链表中没有找到指定删除的Node节点
not_found = True
break
else:
pro = pro.next_node
if not not_found:
pro.next_node = node.next_node
def delete_by_vlaue(self, value):
"""
在链表中删除指定存储数据的Node节点
:param value:指定的储存数据
:return:
"""
if self.__head is None: # 如果链表是空的、则什么都不做
return
if self.__head.data == value: # 如果链表的头Node节点就是指定删除的Node节点
self.__head = self.__head.next_node
# 前一个节点
pre = self.__head
# 当前节点
node = self.__head.next_node
not_found = False
while node.data != value:
if node.next_node is None: # 如果已经到链表的最后一个节点，则表明该链表中没有找到执行value值的Node节点
not_found = True
break
else:
pre = node
node = node.next_node
if not_found is False:
pre.next_node = node.next_node
def delete_last_n_node(self,n):
"""
删除链表中倒数第N个节点
主要思路
设置快、慢两个指针，快指针先行、慢指针不动，当快指针跨了N步以后，快、慢指针同时往链表尾部移动
当快指针到达链表尾部的时候，慢指针所指向的就是链表的倒数第N个节点
:param n: 需要删除的倒数第N个序数
:return:
"""
fast = self.__head
slow = self.__head
step = 0
while step <= 0:
fast = fast.next_node
step += 1
while fast.next_node is not None:
tmp = slow
fast = fast.next_node
slow = slow.next_node
tmp.next_node = slow.next_node
def find_mid_node(self):
"""
查找链表中的中间节点
主要思路：
设置快、慢指针、快指针没次跨两步，慢指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间节点
返回：
node:链表的中间节点
:return:
"""
fast = self.__head
slow = self.__head
while fast.next_node is not None:
fast = fast.next_node.next_node
slow = slow.next_node
return slow
def create_node(self, value):
"""
创建一个存储value值的Node节点
参数：
value:将要存储在Node节点中的数据
返回：
一个新的Node节点
:param value:
:return:
"""
return Node(value)
def print_all(self):
"""
打印当前链表所有节点数据
:return:
"""
pos = self.__head
if pos is None:
print("当前链表还没有数据")
return
list = []
while pos.next_node is not None:
list.append(pos.data)
print(str(pos.data) + "--->", end="")
pos = pos.next_node
print(str(pos.data))
list.append(pos.data)
return list
def reversed_self(self):
"""
翻转链表自身
:return:
"""
if self.__head is None or self.__head.next_node is None: # 如果链表为空，或者链表只为一个节点
return
pre = self.__head
node = self.__head.next_node
while node is not None:
pre, node = self.__reversed_with_two_node(pre, node)
self.__head.next_node = None
self.__head = pre
def __reversed_with_two_node(self, pre, node):
"""
翻转相邻两个节点
:param pre: 当前一个节点
:param node: 当前节点
:return:（pre, node）:下一个相邻节点的元祖
"""
tmp = node.next_node
node.next_node = pre
pre = node # 这样写有点啰嗦，但是能让人更能看明白
node = tmp
return pre, node
def has_ring(self):
"""
主要检查链表中是否有环
主要思想：
设置快、慢两种指针、快指针每次跨两步，慢指针每次跨异步，如果快指针没有雨慢指针相遇而是顺利到达链表尾部
说明没有环；否则，存在环
返回：
True:有环
False:没有环
:return:
"""
fast = self.__head
slow = self.__head
while (fast.next_node is not None) and (fast is not None):
fast = fast.next_node
slow = slow.next_node
if fast == slow:
return True
return False我们写一个pytest单元测试一下
from Brush_questions.linkedlist.singlyLinkedList import SinglyLinkedList
# 相似创建链表结构
def the_some():
singlylink = SinglyLinkedList()
head1 = singlylink.insert_to_head(1)
node2 = singlylink.insert_after(head1, 2)
node3 = singlylink.insert_after(node2, 3)
node4 = singlylink.insert_after(node3, 4)
node5 = singlylink.insert_after(node4, 5)
return singlylink
def test_create_singlink():
"""
创建链表
:return:
"""
singlylink = the_some()
list = singlylink.print_all()
assert list == [1,2,3,4,5]
def test_find_by_value():
"""
寻找某值
:return:
"""
singlylink = the_some()
list = singlylink.print_all()
node = singlylink.find_by_value(2)
assert list == [1, 2, 3, 4, 5]
assert node.data == 2
def test_find_by_index():
"""
寻找某索引的值
:return:
"""
singlylink = the_some()
list = singlylink.print_all()
node = singlylink.find_by_index(2)
print("node节点是:"+str(node)+"\nand值是："+str(node.data))
assert list == [1, 2, 3, 4, 5]
assert node.data == 3
def test_insert_before():
"""
插入某节点之前
:return:
"""
singlylink = SinglyLinkedList()
head1 = singlylink.insert_to_head(1)
node2 = singlylink.insert_after(head1, 2)
node3 = singlylink.insert_after(node2, 3)
node4 = singlylink.insert_after(node3, 4)
node5 = singlylink.insert_after(node4, 5)
list = singlylink.print_all()
node6 = singlylink.insert_after(node5, 6)
after = singlylink.print_all()
node7 = singlylink.insert_before(node6,7)
before = singlylink.print_all()
assert list == [1,2,3,4,5]
assert after == [1,2,3,4,5,6]
assert before == [1,2,3,4,5,7,6]
def test_delete_by_node():
"""
删除某节点
:return:
"""
singlylink = SinglyLinkedList()
head = singlylink.insert_to_head(1)
node = singlylink.insert_after(head, 2)
node = singlylink.insert_after(node, 3)
node = singlylink.insert_after(node, 4)
node = singlylink.insert_after(node, 5)
list = singlylink.print_all()
node = singlylink.delete_by_node(node)
delete_list = singlylink.print_all()
assert list == [1,2,3,4,5]
assert delete_list == [1,2,3,4]
def test_delete_last_n_node():
"""
删除倒数第几个节点
:return:
"""
singlylink = the_some()
list = singlylink.print_all()
node = singlylink.delete_last_n_node(2)
last_n_node = singlylink.print_all()
assert list == [1,2,3,4,5]
assert last_n_node == [1,2,3,5]
def test_reversed_self():
"""
翻转链表
:return:
"""
singlylink = the_some()
list = singlylink.print_all()
node = singlylink.reversed_self()
reversed_self = singlylink.print_all()
assert list == [1,2,3,4,5]
assert reversed_self == [5,4,3,2,1]
测试通过
循环单链表
# 循环单链表 circular_list.py
from Brush_questions.linkedlist.singlyLinkedList import Node
class CircularList():
"""
单向循环链表
"""
def __init__(self,head=None):
"""
单向列表的初始化方法===头节点
"""
self.__head = head
@property
def head(self):
return self.__head
@head.setter
def head(self, head):
self.__head = head
def is_empty(self):
"""
判断链表是否为空
:return:
"""
if self.__head == None:
return True
else:
return False
def find_by_value(self, value):
"""
按照数据值在单向列表中查找
:param value: 查找的数据
:return:Node
"""
node = self.__head
while (node is not None) and (node.data != value) and (self.__head != node.next_node):
node = node.next_node
return node
def find_by_index(self, index):
"""
按照索引值在列表中查找
:param index: 索引值
:return: Node
"""
node = self.__head
pos = 0
while (node is not None) and (pos != index) and (self.__head != node.next_node):
node = node.next_node
pos += 1
return node
def insert_to_head(self, value):
"""
在链表的头部插入一个存储value数值的Node节点
:param value:将要存储的数据
:return:
"""
node = Node(value)
last_node = self.find_last_node()
node.next_node = self.__head
self.__head = node
# 最后节点从新指向头节点
last_node.next_node = node
return node
def insert_after(self, node, value):
"""
在链表的某个指定Node节点之后插入一个存储value数据的Node节点
:param node:指定的一个Node节点
:param value:将要存储在新的Node节点中的数据
:return:
"""
if node is None: # 如果指定在一个空节点之后插入数据节点，则什么都不做
return
new_node = Node(value)
new_node.next_node = node.next_node
node.next_node = new_node
return new_node
def insert_before(self, node, value):
if (node is None) or (self.__head is None): # 如果指定在一个空节点之前或者空链表之前插入数据节点，则什么都不做
return
if node == self.__head: # 如果是在链表头之前插入数据节点，则直接插入
self.insert_to_head(value)
return
new_node = Node(value)
pro = self.__head
not_found = False # 如果在整个链表中都没有找到指定插入的Node节点，则该标记为True
while pro.next_node != node: # 寻找指定Node之前的一个Node
if pro.next_node is None: # 如果已经到了链表的最后一个节点，则表明该链表中没有找到指定插入的Node节点
not_found = True
break
else:
pro = pro.next_node
if not not_found:
pro.next_node = new_node
new_node.next_node = node
def insert_last(self,value):
"""
插入最后一个节点，然后指向的是头节点
:return:
"""
# 1. 先查找最后一个节点
# 2. 插入最后一个节点并将节点指向头节点
last_node = Node(value)
self.__head=last_node.next_node
def find_last_node(self):
"""
查找最后一个节点
:return:
"""
if self.is_empty():
return
else:
node = self.__head
while node.next_node != self.__head:
node = node.next_node
return node
def length_by_node(self):
"""
链表长度
:return:
"""
pos = self.__head
if pos is None:
print("当前链表还没有数据")
return
count = 1
while pos.next_node is not None and pos.next_node != self.__head:
count+= 1
pos = pos.next_node
return count
def delete_by_node(self, node):
"""在链表中删除指定Node的节点.
参数:
node:指定的Node节点
"""
if self.__head is None: # 如果链表是空的，则什么都不做
return
if node == self.__head: # 如果指定删除的Node节点是链表的头节点，最后一个节点就要指向现在的头节点
last_node = self.find_last_node()
self.__head = node.next_node
last_node.next_node = self.__head
return
pro = self.__head
not_found = False # 如果在整个链表中都没有找到指定删除的Node节点，则该标记量设置为True
while pro.next_node != node:
if pro.next_node == self.__head: # 如果已经到链表的最后一个节点，则表明该链表中没有找到指定删除的Node节点
not_found = True
break
else:
pro = pro.next_node
if not not_found:
pro.next_node = node.next_node
def create_node(self, value):
"""
创建一个存储value值的Node节点
参数：
value:将要存储在Node节点中的数据
返回：
一个新的Node节点
:param value:
:return:
"""
return Node(value)
def print_all(self):
"""
遍历整个链表
:return:
"""
pos = self.__head
if pos is None:
print("当前链表还没有数据")
return
list = []
# 这里
while pos.next_node is not None and pos.next_node != self.__head:
list.append(pos.data)
print(str(pos.data) + "--->", end="")
pos = pos.next_node
print(str(pos.data))
list.append(pos.data)
return list
我们用pytest 做一个单元测试看下
# test_cirularlist.py
from Brush_questions.linkedlist.circular_list import CircularList
def the_some():
"""
创建一个循环单链表
:return:
"""
circularlist = CircularList()
node1 = circularlist.create_node(1)
node2 = circularlist.create_node(2)
node3 = circularlist.create_node(3)
node4 = circularlist.create_node(4)
node5 = circularlist.create_node(5)
node1.next_node = node2
node2.next_node = node3
node3.next_node = node4
node4.next_node = node5
circularlist.head = node1
node5.next_node = circularlist.head
return circularlist
def test_create_singlink():
"""
创建链表
:return:
"""
circularlist = the_some()
list = circularlist.print_all()
assert list == [1,2,3,4,5]
def test_length_by_node():
circularlist = the_some()
length = circularlist.length_by_node()
assert length == 5
def test_insert_after():
"""
在某个节点之后插入某值
:return:
"""
circularlist = CircularList()
node1 = circularlist.create_node(1)
node2 = circularlist.create_node(2)
node3 = circularlist.create_node(3)
node4 = circularlist.create_node(4)
node5 = circularlist.create_node(5)
node1.next_node = node2
node2.next_node = node3
node3.next_node = node4
node4.next_node = node5
circularlist.head = node1
node5.next_node = circularlist.head
circularlist.insert_after(node2,7)
circularlist.insert_after(node3, 8)
print_a = circularlist.print_all()
assert print_a == [1,2,7,3,8,4,5]
def test_find_last_node():
"""
查找最后一个节点
:return:
"""
circularlist = the_some()
last_node = circularlist.find_last_node()
assert last_node.data == 5
def test_find_by_value():
"""
查找某值的节点
:return:
"""
circularlist = the_some()
find_by_value = circularlist.find_by_value(5)
assert find_by_value.data == 5
def test_find_by_index():
"""
根据索引值查找某个节点
:return:
"""
circularlist = the_some()
find_by_index = circularlist.find_by_value(4)
assert find_by_index.data == 4
def test_insert_to_head():
"""
插入到头节点
:return:
"""
circularlist = the_some()
circularlist.insert_to_head(10)
print_all = circularlist.print_all()
assert print_all == [10,1,2,3,4,5]
def test_insert_after():
"""
在某个节点插入某值
:return:
"""
circularlist = CircularList()
node1 = circularlist.create_node(1)
node2 = circularlist.create_node(2)
node3 = circularlist.create_node(3)
node4 = circularlist.create_node(4)
node5 = circularlist.create_node(5)
node1.next_node = node2
node2.next_node = node3
node3.next_node = node4
node4.next_node = node5
circularlist.head = node1
node5.next_node = circularlist.head
# 在某个节点之后插入某值
circularlist.insert_after(node2, 9)
circularlist.insert_after(node5, 11)
print_a = circularlist.print_all()
assert print_a == [1,2,9,3,4,5,11]
def test_delete_by_node():
"""
删除链表中的某个节点
:return:
"""
circularlist = CircularList()
node1 = circularlist.create_node(1)
node2 = circularlist.create_node(2)
node3 = circularlist.create_node(3)
node4 = circularlist.create_node(4)
node5 = circularlist.create_node(5)
node1.next_node = node2
node2.next_node = node3
node3.next_node = node4
node4.next_node = node5
circularlist.head = node1
node5.next_node = circularlist.head
circularlist.delete_by_node(node1)
print_a = circularlist.print_all()
assert print_a == [2,3,4,5]
def test_insert_before():
"""
在某个节点之前插入某值
:return:
"""
circularlist = CircularList()
node1 = circularlist.create_node(1)
node2 = circularlist.create_node(2)
node3 = circularlist.create_node(3)
node4 = circularlist.create_node(4)
node5 = circularlist.create_node(5)
node1.next_node = node2
node2.next_node = node3
node3.next_node = node4
node4.next_node = node5
circularlist.head = node1
node5.next_node = circularlist.head
circularlist.insert_before(node3,9)
print_a = circularlist.print_all()
assert print_a == [1,2,9,3,4,5]
测试通过
双链表
# doublelink.py
class Node(object):
"""
双链表
"""
def __init__(self, data):
"""
双链表节点
:param data:
"""
self.data = data
self.pre = None
self.next = None
class DoubleLinkedList(object):
"""
双链表
"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""
判断链表是否为空
:return:
"""
return self.__head is None
def length_by_node(self):
"""
获取链表长度
:return:
"""
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def add_head_by_node(self, elem):
"""
向双链表头部添加元素
:param elem:
:return:
"""
node = Node(elem)
if self.is_empty(): # 链表为空
self.__head = node
else:
node.next = self.__head
# node.next.pre = node # 同样可以这样写
self.__head.pre = node
self.__head = node
def append_last_by_node(self, elem):
"""
向链表尾部添加节点
:param elem:
:return:
"""
node = Node(elem)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
node.pre = cur
return node
def insert_before(self, node, value):
"""
在某个节点之前 处插入元素elem
:param pos:
:param elem:
:return:
"""
if (node is None) or (self.__head is None):
return
# 插入到头节点
if node == self.__head:
self.add_head_by_node(value)
return
new_node = Node(value)
# 前一个节点
pre = self.__head
# 当前节点
node = self.__head.next
not_fount = False
while pre.next != node:
if pre.next is None:
not_fount = True
break
else:
pre = node
node = node.next
if not not_fount:
pre.next = new_node
new_node.pre = pre
new_node.next = node
node.pre = new_node.next
def remove_by_node(self,value):
"""
删除链表中第一个值为elem的节点
:param self:
:param elem:
:return:
"""
if self.is_empty():
return
if self.__head.data == value: # 如果链表的头Node节点就是指定删除的Node节点
self.__head = self.__head.next
# 前一个节点
pre = self.__head
# 当前节点
node = self.__head.next
not_found = False
while node.data != value:
if node.next is None: # 如果已经到链表的最后一个节点，则表明该链表中没有找到执行value值的Node节点
not_found = True
break
else:
pre = node
node = node.next
if not_found is False:
pre.next = node.next
node.next.pre = pre.next
def search_by_node(self, elem):
"""
查找链表中是否有元素elem
:param elem:
:return:
"""
cur = self.__head
while cur is not None:
if cur.data == elem:
return True
else:
cur = cur.next
return False
def print_all(self):
"""
打印当前链表所有节点数据
:return:
"""
pos = self.__head
if pos is None:
print("当前链表还没有数据")
return
list = []
while pos.next is not None:
list.append(pos.data)
print(str(pos.data) + "--->", end="")
pos = pos.next
print(str(pos.data))
list.append(pos.data)
return list
我们还是使用pytest 测试一下
# test_doublelink.py
from Brush_questions.linkedlist.doublelink import DoubleLinkedList
def create_doublelinkedlist():
double_link_list = DoubleLinkedList()
double_link_list.append_last_by_node(1)
double_link_list.append_last_by_node(2)
double_link_list.append_last_by_node(3)
double_link_list.append_last_by_node(4)
double_link_list.append_last_by_node(5)
return double_link_list
def test_create_doublelinkedlist():
doublelinklist = create_doublelinkedlist()
print_all = doublelinklist.print_all()
assert print_all == [1,2,3,4,5]
def test_search_by_node():
doublelinklist = create_doublelinkedlist()
is_true_first = doublelinklist.search_by_node(2)
is_true_second = doublelinklist.search_by_node(3)
is_true_third = doublelinklist.search_by_node(9)
assert is_true_first == True
assert is_true_second == True
assert is_true_third == False
def test_insert_before():
"""
删除链表中第一个值为elem的节点
:return:
"""
doublelinklist = create_doublelinkedlist()
doublelinklist.insert_before(1,6)
print_all = doublelinklist.print_all()
assert print_all == [1,6,2,3,4,5]
def test_remove_by_node():
doublelinklist = create_doublelinkedlist()
doublelinklist.remove_by_node(3)
print_all = doublelinklist.print_all()
assert print_all == [1, 2, 4, 5]
doublelinklist.remove_by_node(9)
print_all = doublelinklist.print_all()
assert print_all == [1,2,4,5]
def test_insert_before():
double_link_list = DoubleLinkedList()
node1 = double_link_list.append_last_by_node(1)
node2 = double_link_list.append_last_by_node(2)
node3 = double_link_list.append_last_by_node(3)
node4 = double_link_list.append_last_by_node(4)
node5 = double_link_list.append_last_by_node(5)
double_link_list.insert_before(node2,9)
print_all = double_link_list.print_all()
assert print_all == [1,9,2,3,4,5]
循环双端链表
# circular_double_list.py思考
- 为什么先要了解这四种类型呢？
- 实现为什么不用数组来实现呢？数组与链表的各自优缺点到底有什么呢？
- 这和我们分析Orderdict有什么关系呢？
- 顺序字典的。为什么会使用循环双端链表来实现呢?我们先来看下这四种链表的时间复杂度
回答
- 因为了解Orderdict源码首先就要了解链表这种数据结构，他的底层是用循环双端链表来实现的
- 数组和链表的各自优缺点可以这么分为。数组分配是连续的一段内存空间，而链表可以将一段不连续的内存空间组合在一起。
- 数组按下标的查找时间复杂度为O(1)。而链表因为对单个节点而言，对单链表而言只知道后面节点，所以查找的时间复杂度为O(n)
- 数组的删除操作时间复杂度为O(n)。而链表的删除操作很方便O(1)(对已经知道节点的情况下)
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
这样就很好比较了他们的优缺点
3. 因为Orderdict 正式使用了循环双端链表来实现
Orderdict有几个方法
class OrderedDict(Dict[_KT, _VT], Reversible[_KT], Generic[_KT, _VT]):
def popitem(self, last: bool = ...) -> Tuple[_KT, _VT]: ...
def move_to_end(self, key: _KT, last: bool = ...) -> None: ...
def copy(self: _OrderedDictT) -> _OrderedDictT: ...
def __reversed__(self) -> Iterator[_KT]: ...
def keys(self) -> _OrderedDictKeysView[_KT]: ...
def items(self) -> _OrderedDictItemsView[_KT, _VT]: ...
def values(self) -> _OrderedDictValuesView[_VT]: ...
- popitem(last=True) # 有序字典的 popitem() 方法移除并返回一个 (key, value) 键值对。 如果 last 值为真，则按 LIFO 后进先出的顺序返回键值对，否则就按 FIFO 先进先出的顺序返回键值对。
- move_to_end(key, last=True) # 将现有 key 移动到有序字典的任一端。 如果 last 为真值（默认）则将元素移至末尾；如果 last 为假值则将元素移至开头。如果 key 不存在则会触发 KeyError:
- copy
- __reversed__
- keys # 这些就是返回有序字典的键值对
- items
- values我们知道了有几个方法而且也特别好用，那么我觉得OrderDict有点绕怎么办！我们用他的方法自己实现以下看如何
class DoubleLink(object):
""" 双端循环链表 """
def __init__(self):
super(DoubleLink, self).__init__()
self.__root = root = []
root[:] = [root, root, None]
self.__map = {}
def add(self, key):
# 每次都是在哨兵节点的前面插入一个新的节点
# 每次插入的节点逻辑上为最后一个节点
root = self.__root
last = root[0]
last[1] = root[0] = self.__map[key] = [last, root, key]
def delete(self, key):
prev, next, _ = self.__map.pop(key)
prev[1] = next
next[0] = prev
def __iter__(self):
root = self.__root # 哨兵节点不用参与遍历
curr = root[1] # start at the first node
while curr is not root:
yield curr[2] # yield the curr[KEY]
curr = curr[1] # move to next node
def __reversed__(self):
root = self.__root # 哨兵节点不用参与遍历
curr = root[0] # start at the last node
while curr is not root:
yield curr[2] # yield the curr[KEY]
curr = curr[0] # move to previous node
def clear(self):
root = self.__root
root[:] = [root, root, None]
self.__map.clear()
doublelink = DoubleLink()
doublelink.add("1")
doublelink.add("2")
doublelink.add("3")
doublelink.delete("2")
for i in doublelink:
print(i)
# 1
# 3OrderDict 顺序字典思路
- 使用循环双端链表来保存Key值，其中每个节点使用list 为[prev, next, key]。
- 初始化会一个头节点。头节点不会移动。
- 使用self.__map来保存key值和循环双端链表的映射关系。
- 使用继承dict功能来保存key 与value的关系
结尾
- 失望：但是我查阅资料，现在的dict 在python 3.6已经实现了顺序字典。那么我的分析就觉得我有病！但不知道作为标准库，他为什么还存在collection中？
- 下一节 ARTS主题 我们手把手实践一下代理。用go/python两种语言实践下混淆。
参考资料
