四种常见的链表包括:单向链表,单向循环链表,双向链表,双向循环链表。
要实现的链表操作包括
-
is_empty()
判断链表是否为空 -
length()
求链表长度 -
traversing()
遍历所有节点元素 -
add()
头部添加节点 -
append()
尾部添加节点 -
insert(pos, item)
某个位置插入节点 -
remove(item)
删除一个节点 -
search(item)
查找某个节点是否存在
先初始化节点
class Node(object):
"""单节点"""
def __init__(self, elem):
self.elem = elem
self.next = None
class DoubleNode(Node):
"""双节点"""
def __init__(self, elem):
super(DoubleNode, self).__init__(elem)
self.prev = None
四种链表的实现中,每一个类都继承自 object
, self.__head
是私有变量,不能被子类或外部调用。
class SingleLinkList(object):
"""单向链表"""
def __init__(self, node=None):
self.head = node
def is_empty(self) -> bool:
"""链表是否为空 O(1)"""
return self.head is None
def length(self) -> int:
"""链表长度 O(n)"""
count, cur = 0, self.head
while cur is not None:
cur = cur.next # 不要写错 cur = self.head.next, self.__next 不是活动指针
count += 1
return count
def traversing(self) -> '':""" 遍历所有节点 O(n)"""
cur = self.head # 不是 self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next
return ''def add(self, item) -> None:""" 头部添加节点 O(1)"""
node = Node(item)
node.next = self.head
self.head = node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = Node(item)
cur = self.head
if self.is_empty():
self.head = node
else:
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = Node(item)
count, cur = 1, self.head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
pre, cur = None, self.head
while cur is not None:
if cur.elem == item:
if cur == self.head:
self.head = cur.next
break # 只 remove 第一个元素
pre.next = cur.next
break
pre = cur
cur = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
cur = self.head
while cur is not None:
if cur.elem == item:
return True
cur = cur.next
return False
class SingleCycleLinkList(object):
"""单向循环链表"""
def __init__(self, node=None):
self.__head = node
if node:
node.next = node
def is_empty(self) -> bool:
"""链表是否为空 O(1)"""
return self.__head is None
def length(self) -> int:
"""链表长度 O(n)"""
if self.is_empty():
return 0
count, cur = 1, self.__head
while cur.next != self.__head:
cur = cur.next # 不要写错 cur = self.__head.next, self.__next 不是活动指针
count += 1
return count
def transverse(self) -> '':""" 遍历所有节点 O(n)"""
if not self.is_empty():
cur = self.__head # 不是 self._head
while cur.next != self.__head:
print(cur.elem, end=' ')
cur = cur.next
print(cur.elem, end=' ')
return ''def add(self, item) -> None:""" 头部添加节点 O(n)"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# 退出 while 循环之后 cur 指向尾结点
node.next = self.__head
self.__head = node
cur.next = self.__head
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = Node(item)
count, cur = 1, self.__head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
if self.is_empty():
return
pre, cur = None, self.__head
while cur.next != self.__head:
if cur.elem == item:
# 移除头结点
if cur == self.__head:
rear = self.__head
while rear.next != self.__head:
rear = rear.next
self.__head = cur.next
rear.next = self.__head
# 移除中间节点
else:
pre.next = cur.next
return # 结束。只 remove 第一个元素
pre = cur
cur = cur.next
# 移除尾结点
if cur.elem == item:
if cur == self.__head:
self.__head = None
else:
pre.next = self.__head # 或者 pre.next = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
if self.is_empty():
return False
else:
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
return True
cur = cur.next
return cur.elem == item
class DoubleLinkList(object):
"""双向链表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self) -> bool:
"""链表是否为空 O(1)"""
return self.__head is None
def length(self) -> int:
"""链表长度 O(n)"""
count, cur = 0, self.__head
while cur is not None:
cur = cur.next # 不要写错 cur = self.__head.next, self.__next 不是活动指针
count += 1
return count
def transverse(self) -> '':""" 遍历所有节点 O(n)"""
cur = self.__head # 不是 self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next
return ''def add(self, item) -> None:""" 头部添加节点 O(1)"""
node = DoubleNode(item)
node.next = self.__head
self.__head = node
if node.next: # 当原链表为空时
node.next.prev = node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = DoubleNode(item)
cur = self.__head
if self.is_empty():
self.__head = node
else:
while cur.next is not None:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = DoubleNode(item)
count, cur = 1, self.__head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
node.prev = cur
cur.next.prev = node
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
cur = self.__head
while cur is not None:
if cur.elem == item:
if cur == self.__head:
self.__head = cur.next
if self.__head: # 只有一个节点的特殊情况
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break # 只 remove 第一个元素
cur = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
cur = self.__head
while cur is not None:
if cur.elem == item:
return True
cur = cur.next
return False
class DoubleCycleLinkList(object):
"""双向循环链表"""
def __init__(self, node=None):
self.__head = node
if node:
node.next = node
node.prev = node
def is_empty(self) -> bool:
"""链表是否为空 O(1)"""
return self.__head is None
def length(self) -> int:
"""链表长度 O(n)"""
if self.is_empty():
return 0
count, cur = 1, self.__head
while cur.next != self.__head:
cur = cur.next # 不要写错 cur = self.__head.next, self.__next 不是活动指针
count += 1
return count
def transverse(self) -> '':""" 遍历所有节点 O(n)"""
if not self.is_empty():
cur = self.__head # 不是 self._head
while cur.next != self.__head:
print(cur.elem, end=' ')
cur = cur.next
print(cur.elem, end=' ')
return ''def add(self, item) -> None:""" 头部添加节点 O(n)"""
node = DoubleNode(item)
if self.is_empty():
self.__head = node
node.next = node
node.prev = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# 退出 while 循环之后 cur 指向尾结点,双向循环链表需要改动 5 个指针
node.next = self.__head # 1.node.next 指向原来的头结点
node.prev = cur # 2.node.prev 指向尾结点,当前 cur 指向的节点
cur.next.prev = node # 3. 原来头结点的 prev 指向要插入的 node
self.__head = node # 4.self.__head 指向要插入的 node
cur.next = node # 5. 尾结点的 next 指向要插入的 node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = DoubleNode(item)
if self.is_empty():
self.__head = node
node.next = node
node.prev = node
else:
cur = self.__head
# 退出 while 循环之后 cur 指向尾结点,双向循环链表需要改动 4 个指针
while cur.next != self.__head:
cur = cur.next
cur.next.prev = node # 1. 原来头结点的.prev 指向要插入的 node
cur.next = node # 2. 原来尾结点.next 指向要插入的 node
node.prev = cur # 3.node.prev 指向原来的尾节点
node.next = self.__head # 4.node.next 指向头结点
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = DoubleNode(item)
count, cur = 1, self.__head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
node.prev = cur
cur.next.pre = node
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
if self.is_empty():
return
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
# 移除头结点
if cur == self.__head:
cur.prev.next = cur.next
cur.next.prev = cur.prev
self.__head = cur.next
# 移除中间节点
else:
cur.prev.next = cur.next
cur.next.prev = cur.prev
return # 结束。只 remove 第一个元素
cur = cur.next
# 移除尾结点
if cur.elem == item:
if cur == self.__head: # 当链表只有一个节点时
self.__head = None
else:
cur.next.prev = cur.prev
cur.prev.next = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
if self.is_empty():
return False
else:
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
return True
cur = cur.next
return cur.elem == item
在以上四种链表的实现中,可以发现有的类方法代码是重复的,具体重复的方法如下:
- 所有的
is_empty()
方法都一样 - 双向链表的
length()
,traversing()
,search(item)
实现与单向链表 - 双向循环链表的
length()
,traversing()
,search(item)
实现与单向循环链表一样
因此,我们可以使用 Python 中类的特性:继承和多态 来简化代码,使用了继承之后把self.__head
改成self.head
。
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# __author__ = 'zhao zi yang'
class Node(object):
"""单节点"""
def __init__(self, elem):
self.elem = elem
self.next = None
class DoubleNode(Node):
"""双节点"""
def __init__(self, elem):
super(DoubleNode, self).__init__(elem)
self.prev = None
class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.head = node
def is_empty(self) -> bool:
"""链表是否为空 O(1)"""
return self.head is None
def length(self) -> int:
"""链表长度 O(n)"""
count, cur = 0, self.head
while cur is not None:
cur = cur.next # 不要写错 cur = self.head.next, self.__next 不是活动指针
count += 1
return count
def traversing(self) -> '':""" 遍历所有节点 O(n)"""
cur = self.head # 不是 self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next
return ''def add(self, item) -> None:""" 头部添加节点 O(1)"""
node = Node(item)
node.next = self.head
self.head = node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = Node(item)
cur = self.head
if self.is_empty():
self.head = node
else:
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = Node(item)
count, cur = 1, self.head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
pre, cur = None, self.head
while cur is not None:
if cur.elem == item:
if cur == self.head:
self.head = cur.next
break # 只 remove 第一个元素
pre.next = cur.next
break
pre = cur
cur = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
cur = self.head
while cur is not None:
if cur.elem == item:
return True
cur = cur.next
return False
class SingleCycleLinkList(SingleLinkList):
"""单向循环链表"""
def __init__(self, node=None):
if node:
node.next = node
super(SingleCycleLinkList, self).__init__(node=node)
def length(self) -> int:
"""链表长度 O(n)"""
if self.is_empty():
return 0
count, cur = 1, self.head
while cur.next != self.head:
cur = cur.next # 不要写错 cur = self.head.next, self.__next 不是活动指针
count += 1
return count
def traversing(self) -> '':""" 遍历所有节点 O(n)"""
if not self.is_empty():
cur = self.head # 不是 self._head
while cur.next != self.head:
print(cur.elem, end=' ')
cur = cur.next
print(cur.elem, end=' ')
return ''def add(self, item) -> None:""" 头部添加节点 O(n)"""
node = Node(item)
if self.is_empty():
self.head = node
node.next = node
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
# 退出 while 循环之后 cur 指向尾结点
node.next = self.head
self.head = node
cur.next = self.head
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = Node(item)
if self.is_empty():
self.head = node
node.next = node
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
node.next = self.head
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = Node(item)
count, cur = 1, self.head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
if self.is_empty():
return
pre, cur = None, self.head
while cur.next != self.head:
if cur.elem == item:
# 移除头结点
if cur == self.head:
rear = self.head
while rear.next != self.head:
rear = rear.next
self.head = cur.next
rear.next = self.head
# 移除中间节点
else:
pre.next = cur.next
return # 结束。只 remove 第一个元素
pre = cur
cur = cur.next
# 移除尾结点
if cur.elem == item:
if cur == self.head:
self.head = None
else:
pre.next = self.head # 或者 pre.next = cur.next
def search(self, item) -> bool:
"""查找节点是否存在 O(n)"""
if self.is_empty():
return False
else:
cur = self.head
while cur.next != self.head:
if cur.elem == item:
return True
cur = cur.next
return cur.elem == item
class DoubleLinkList(SingleLinkList):
"""双链表"""
def add(self, item) -> None:
"""头部添加节点 O(1)"""
node = DoubleNode(item)
node.next = self.head
self.head = node
if node.next: # 当原链表为空时
node.next.prev = node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = DoubleNode(item)
cur = self.head
if self.is_empty():
self.head = node
else:
while cur.next is not None:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = DoubleNode(item)
count, cur = 1, self.head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
node.prev = cur
cur.next.prev = node
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
cur = self.head
while cur is not None:
if cur.elem == item:
if cur == self.head:
self.head = cur.next
if self.head: # 只有一个节点的特殊情况
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break # 只 remove 第一个元素
cur = cur.next
class DoubleCycleLinkList(SingleCycleLinkList):
"""双向循环链表"""
def __init__(self, node=None):
if node:
node.next = node
node.prev = node
super(DoubleCycleLinkList, self).__init__(node=node)
def add(self, item) -> None:
"""头部添加节点 O(n)"""
node = DoubleNode(item)
if self.is_empty():
self.head = node
node.next = node
node.prev = node
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
# 退出 while 循环之后 cur 指向尾结点,双向循环链表需要改动 5 个指针
node.next = self.head # 1.node.next 指向原来的头结点
node.prev = cur # 2.node.prev 指向尾结点,当前 cur 指向的节点
cur.next.prev = node # 3. 原来头结点的 prev 指向要插入的 node
self.head = node # 4.self.head 指向要插入的 node
cur.next = node # 5. 尾结点的 next 指向要插入的 node
def append(self, item) -> None:
"""尾部添加节点 O(n)"""
node = DoubleNode(item)
if self.is_empty():
self.head = node
node.next = node
node.prev = node
else:
cur = self.head
# 退出 while 循环之后 cur 指向尾结点,双向循环链表需要改动 4 个指针
while cur.next != self.head:
cur = cur.next
cur.next.prev = node # 1. 原来头结点的.prev 指向要插入的 node
cur.next = node # 2. 原来尾结点.next 指向要插入的 node
node.prev = cur # 3.node.prev 指向原来的尾节点
node.next = self.head # 4.node.next 指向头结点
def insert(self, position: int, item) -> None:
"""
节点插入到某个位置 O(n)
:param position: 0 表示第 1 个位置
:param item:
:return: None
"""
if position <= 0:
self.add(item)
elif position >= self.length():
self.append(item)
else:
node = DoubleNode(item)
count, cur = 1, self.head
while count < position:
cur = cur.next
count += 1
node.next = cur.next
node.prev = cur
cur.next.pre = node
cur.next = node
def remove(self, item) -> None:
"""删除链表中的一个节点 O(n)"""
if self.is_empty():
return
cur = self.head
while cur.next != self.head:
if cur.elem == item:
# 移除头结点
if cur == self.head:
cur.prev.next = cur.next
cur.next.prev = cur.prev
self.head = cur.next
# 移除中间节点
else:
cur.prev.next = cur.next
cur.next.prev = cur.prev
return # 结束。只 remove 第一个元素
cur = cur.next
# 移除尾结点
if cur.elem == item:
if cur == self.head: # 当链表只有一个节点时
self.head = None
else:
cur.next.prev = cur.prev
cur.prev.next = cur.next
if __name__ == '__main__':
print("----single_link_list-----")
single_link_list = SingleLinkList()
single_link_list.remove('test')
print(single_link_list.is_empty(), single_link_list.length())
single_link_list.insert(-1, 'zhao')
print(single_link_list.is_empty(), single_link_list.length())
single_link_list.insert(3, 'zi')
print(single_link_list.length())
single_link_list.append('yang')
single_link_list.add("head")
single_link_list.insert(4, "tail")
print(single_link_list.traversing())
single_link_list.remove(1)
print(single_link_list.traversing())
single_link_list.remove("head")
print(single_link_list.traversing())
single_link_list.remove("tail")
print(single_link_list.traversing())
single_link_list.remove('zi')
print(single_link_list.traversing())
print("\n----single_cycle_link_list-----")
single_cycle_link_list = SingleCycleLinkList()
single_cycle_link_list.remove('test')
print(single_cycle_link_list.is_empty(), single_cycle_link_list.length())
single_cycle_link_list.insert(-1, 'zhao')
print(single_cycle_link_list.is_empty(), single_cycle_link_list.length())
single_cycle_link_list.insert(3, 'zi')
print(single_cycle_link_list.length())
single_cycle_link_list.append('yang')
single_cycle_link_list.add("head")
single_cycle_link_list.insert(4, "tail")
print(single_cycle_link_list.traversing())
single_cycle_link_list.remove(1)
print(single_cycle_link_list.traversing())
single_cycle_link_list.remove("head")
print(single_cycle_link_list.traversing())
single_cycle_link_list.remove("tail")
print(single_cycle_link_list.traversing())
single_cycle_link_list.remove('zi')
print(single_cycle_link_list.traversing())
print("\n----double_link_list-----")
double_link_list = DoubleLinkList()
double_link_list.remove('test')
print(double_link_list.is_empty(), double_link_list.length())
double_link_list.insert(-1, 'zhao')
print(double_link_list.is_empty(), double_link_list.length())
double_link_list.insert(3, 'zi')
print(double_link_list.length())
double_link_list.append('yang')
double_link_list.add("head")
double_link_list.insert(4, "tail")
print(double_link_list.traversing())
double_link_list.remove(1)
print(double_link_list.traversing())
double_link_list.remove("head")
print(double_link_list.traversing())
double_link_list.remove("tail")
print(double_link_list.traversing())
double_link_list.remove('zi')
print(double_link_list.traversing())
print("\n----double_cycle_link_list-----")
double_cycle_link_list = DoubleCycleLinkList()
double_cycle_link_list.remove('test')
print(double_cycle_link_list.is_empty(), double_cycle_link_list.length())
double_cycle_link_list.insert(-1, 'zhao')
print(double_cycle_link_list.is_empty(), double_cycle_link_list.length())
double_cycle_link_list.insert(3, 'zi')
print(double_cycle_link_list.length())
double_cycle_link_list.append('yang')
double_cycle_link_list.add("head")
double_cycle_link_list.insert(4, "tail")
print(double_cycle_link_list.traversing())
double_cycle_link_list.remove(1)
print(double_cycle_link_list.traversing())
double_cycle_link_list.remove("head")
print(double_cycle_link_list.traversing())
double_cycle_link_list.remove("tail")
print(double_cycle_link_list.traversing())
double_cycle_link_list.remove('zi')
print(double_cycle_link_list.traversing())
结果运行如下:
----single_link_list-----
True 0
False 1
2
head zhao zi yang tail
head zhao zi yang tail
zhao zi yang tail
zhao zi yang
zhao yang
----single_cycle_link_list-----
True 0
False 1
2
head zhao zi yang tail
head zhao zi yang tail
zhao zi yang tail
zhao zi yang
zhao yang
----double_link_list-----
True 0
False 1
2
head zhao zi yang tail
head zhao zi yang tail
zhao zi yang tail
zhao zi yang
zhao yang
----double_cycle_link_list-----
True 0
False 1
2
head zhao zi yang tail
head zhao zi yang tail
zhao zi yang tail
zhao zi yang
zhao yang