链表的定义：
链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。
链表
链表的基本元素有：
节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
root:根节点
head:头结点
tail: 尾节点
None:链表中最后一个节点的指针域为None值
Python代码实现 -- 单链表
class Node(object):
# 这里我们 root 节点默认都是 None，所以都给了默认值
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __str__(self):
"""方便你打出来调试，复杂的代码可能需要断点调试"""
return '<Node: value: {}, next={}>'.format(self.value, self.next)
__repr__ = __str__
class LinkedList(object):
"""
链接表 ADT
[root] -> [node0] -> [node1] -> [node2]
"""
def __init__(self, maxsize=None):
"""
:param maxsize: int or None, 如果是 None，无限扩充
"""
self.maxsize = maxsize
self.root = Node() # 默认 root 节点指向 None
self.tailnode = None
self.length = 0
def __len__(self):
return self.length
def append(self, value): # O(1)
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value) # 构造节点
tailnode = self.tailnode
if tailnode is None: # 还没有 append 过，length = 0， 追加到 root 后
self.root.next = node
else: # 否则追加到最后一个节点的后边，并更新最后一个节点是 append 的节点
tailnode.next = node
self.tailnode = node
self.length += 1
def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value)
if self.tailnode is None: # 如果原链表为空，插入第一个元素需要设置 tailnode
self.tailnode = node
headnode = self.root.next
self.root.next = node
node.next = headnode
self.length += 1
def __iter__(self):
for node in self.iter_node():
yield node.value
def iter_node(self):
"""遍历 从 head 节点到 tail 节点"""
curnode = self.root.next
while curnode is not self.tailnode: # 从第一个节点开始遍历
yield curnode
curnode = curnode.next # 移动到下一个节点
if curnode is not None:
yield curnode
def remove(self, value): # O(n)
"""
删除包含值的一个节点，将其前一个节点的 next 指向被查询节点的下一个即可
:param value:
"""
prevnode = self.root
for curnode in self.iter_node():
if curnode.value == value:
prevnode.next = curnode.next
if curnode is self.tailnode: # NOTE: 注意更新 tailnode
self.tailnode = prevnode
del curnode
self.length -= 1
return 1 # 表明删除成功
else:
prevnode = curnode
return -1 # 表明删除失败
def find(self, value): # O(n)
"""
查找一个节点，返回序号，从 0 开始
:param value:
"""
index = 0
for node in self.iter_node(): # 我们定义了 __iter__，这里就可以用 for 遍历它了
if node.value == value:
return index
index += 1
return -1 # 没找到
def popleft(self): # O(1)
"""
删除第一个链表节点
"""
if self.root.next is None:
raise Exception('pop from empty LinkedList')
headnode = self.root.next
self.root.next = headnode.next
self.length -= 1
value = headnode.value
if self.tailnode is headnode: # 勘误：增加单节点删除 tailnode 处理
self.tailnode = None
del headnode
return value
def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.length = 0
self.tailnode = None
def test_linked_list():
ll = LinkedList()
ll.append(0)
ll.append(1)
ll.append(2)
ll.append(3)
assert len(ll) == 4
assert ll.find(2) == 2
assert ll.find(-1) == -1
assert ll.remove(0) == 1
assert ll.remove(10) == -1
assert ll.remove(2) == 1
assert len(ll) == 2
assert list(ll) == [1, 3]
assert ll.find(0) == -1
ll.appendleft(0)
assert list(ll) == [0, 1, 3]
assert len(ll) == 3
headvalue = ll.popleft()
assert headvalue == 0
assert len(ll) == 2
assert list(ll) == [1, 3]
assert ll.popleft() == 1
assert list(ll) == [3]
ll.popleft()
assert len(ll) == 0
assert ll.tailnode is None
ll.clear()
assert len(ll) == 0
assert list(ll) == []
def test_linked_list_remove():
ll = LinkedList()
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
ll.append(7)
ll.remove(7)
print(list(ll))
def test_linked_list_append():
ll = LinkedList()
ll.appendleft(1)
ll.append(2)
assert list(ll) == [1, 2]
if __name__ == '__main__':
test_linked_list()
test_linked_list_append()
test_linked_list_remove()
| 链表操作 | 平均时间复杂度 |
|---|---|
| linked_list.append(value) | O(1) |
| linked_list.appendleft(value) | O(1) |
| linked_list.find(value) | O(n) |
| linked_list.remove(value) | O(n) |
Python代码实现 -- 循环双端链表
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next
class CircularDoubleLinkedList(object):
"""
循环双端链表 ADT
多了个循环其实就是把 root 的 prev 指向 tail 节点，串起来
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0
def __len__(self):
return self.length
def headnode(self):
return self.root.next
def tailnode(self):
return self.root.prev
def append(self, value): # O(1), 你发现一般不用 for 循环的就是 O(1)，有限个步骤
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value=value)
tailnode = self.tailnode() or self.root
tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node
self.length += 1
def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value=value)
if self.root.next is self.root: # empty
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1
def remove(self, node): # O(1)，传入node 而不是 value 我们就能实现 O(1) 删除
"""remove
:param node # 在 lru_cache 里实际上根据key 保存了整个node:
"""
if node is self.root:
return
else: #
node.prev.next = node.next
node.next.prev = node.prev
self.length -= 1
return node
def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root:
yield curnode
curnode = curnode.next
yield curnode
def __iter__(self):
for node in self.iter_node():
yield node.value
def iter_node_reverse(self):
"""相比单链表独有的反序遍历"""
if self.root.prev is self.root:
return
curnode = self.root.prev
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode
def test_double_link_list():
dll = CircularDoubleLinkedList()
assert len(dll) == 0
dll.append(0)
dll.append(1)
dll.append(2)
assert list(dll) == [0, 1, 2]
assert [node.value for node in dll.iter_node()] == [0, 1, 2]
assert [node.value for node in dll.iter_node_reverse()] == [2, 1, 0]
headnode = dll.headnode()
assert headnode.value == 0
dll.remove(headnode)
assert len(dll) == 2
assert [node.value for node in dll.iter_node()] == [1, 2]
dll.appendleft(0)
assert [node.value for node in dll.iter_node()] == [0, 1, 2]
if __name__ == '__main__':
test_double_link_list()
| 循环双端链表操作 | 平均时间复杂度 |
|---|---|
| cdll.append(value) | O(1) |
| cdll.appendleft(value) | O(1) |
| cdll.remove(node)，注意这里参数是 node | O(1) |
| cdll.headnode() | O(1) |
| cdll.tailnode() | O(1) |
网友评论