一、链表
将元素存放在通过链接构造起来的一系列存储块中
在每一节点（数据存储单元）里存放下一个节点的位置信息（地址）
1.1 单链表
又称单向链表
它的每个节点包含两个域，一个信息域（元素域），一个链接域。这个链接指向链表的下一个节点，而最后一个节点的链接域则指向一个空值
- 元素域elem用来存放具体的数据
- 链接域next用来存放下一个节点的位置
- 变量p指向链接的头节点的位置，从p出发就可以找到表中的任意节点
1.1.1 变量实质
=相当于指向，操作的是地址信息
1.1.2 节点实现
eg:
# 节点
class Node(object):
# 对象属性：item, next
def __init__(self, item):
self.item = item
self.next = None
# 单链表
class SingleLinkList(object):
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""
链表是否为空
:return 链表为空返回真
"""
return self.__head is None
def length(self):
"""
计算链表长度
:return 链表长度
"""
count = 0
cur = self.__head
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
if not cur:
print(None)
else:
while cur is not None:
print(cur.item, end=' ')
cur = cur.next
print('')
def add(self, item):
"""
链表头部增加元素
:param item:要添加的具体数据
"""
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
"""链表尾部增加元素"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头部添加元素
if pos <= 0:
self.add(item)
# 在尾部添加元素
elif pos >= self.length():
self.append(item)
# 在中间添加元素
else:
cur = self.__head
count = 0
while count < (pos-1):
count += 1
cur = cur.next
node = Node(item)
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除元素"""
cur = self.__head
pre = None
while cur is not None:
if cur.item == item:
# 头部找到的元素
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
return
# 不是要找的元素，就移动游标
pre = cur
cur = cur.next
def search(self, item):
"""查看元素是否存在"""
cur = self.__head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
sll = SingleLinkList()
print(sll.length()) # 0
sll.travel() # None
sll.append(1) # 1
sll.travel()
sll.append(2) # 1,2
sll.travel()
sll.add(3) # 3,1,2
sll.travel()
sll.insert(0, 4) # 4,3,1,2
sll.travel()
sll.insert(19, 5) # 4,3,1,2,5
sll.travel()
sll.insert(2, 6) # 4,3,6,1,2,5
sll.travel()
sll.remove(4) # 3,6,1,2,5
sll.travel()
sll.remove(5) # 3,6,1,2
sll.travel()
sll.remove(6) # 3,1,2
sll.travel()
sll.remove(3) # 1,2
sll.travel()
sll.remove(1) # 2
sll.travel()
sll.remove(2) # None
sll.travel()
1.2 双向链表
eg:
# 节点
class Node(object):
# 对象属性：item, pre, next
def __init__(self, item):
self.item = item
self.pre = None
self.next = None
# 双向链表
class DoubleLinkList(object):
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""
链表是否为空
:return 链表为空返回真
"""
return self.__head is None
def length(self):
"""
计算链表长度
:return 链表长度
"""
count = 0
cur = self.__head
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
if not cur:
print(None)
else:
while cur is not None:
print(cur.item, end=' ')
cur = cur.next
print('')
def search(self, item):
"""查看元素是否存在"""
cur = self.__head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
# ==============前面的可以直接继承单链表类==============
def add(self, item):
"""
链表头部增加元素
:param item:要添加的具体数据
"""
node = Node(item)
node.next = self.__head
self.__head = node
# 补充的
if node.next:
node.next.pre = node
def append(self, item):
"""链表尾部增加元素"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
node.pre = cur
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头部添加元素
if pos <= 0:
self.add(item)
# 在尾部添加元素
elif pos >= self.length():
self.append(item)
# 在中间添加元素
else:
cur = self.__head
count = 0
while count < pos:
count += 1
cur = cur.next
node = Node(item)
node.next = cur
node.pre = cur.pre
# 特别注意下面的两句代码的先后顺序
# 先与前面的节点相连，再与后面的节点相连
cur.pre.next = node
cur.pre = node
def remove(self, item):
"""删除元素"""
cur = self.__head
while cur is not None:
if cur.item == item:
# 头部找到的元素
if cur == self.__head:
self.__head = cur.next
if cur.next:
self.__head.pre = None
else:
cur.pre.next = cur.next
if cur.next:
cur.next.pre = cur.pre
return
# 不是要找的元素，就移动游标
cur = cur.next
if __name__ == '__main__':
sll = DoubleLinkList()
print(sll.length()) # 0
sll.travel() # None
sll.append(1) # 1
sll.travel()
sll.append(2) # 1,2
sll.travel()
sll.add(3) # 3,1,2
sll.travel()
sll.insert(0, 4) # 4,3,1,2
sll.travel()
sll.insert(19, 5) # 4,3,1,2,5
sll.travel()
sll.insert(2, 6) # 4,3,6,1,2,5
sll.travel()
sll.remove(4) # 3,6,1,2,5
sll.travel()
sll.remove(5) # 3,6,1,2
sll.travel()
sll.remove(6) # 3,1,2
sll.travel()
sll.remove(3) # 1,2
sll.travel()
sll.remove(1) # 2
sll.travel()
sll.remove(2) # None
sll.travel()
1.3 单向循环链表
链表的最后一个节点的next域不再指向None，而是指向链表的头节点
eg:
# 节点
class Node(object):
# 对象属性：item, next
def __init__(self, item):
self.item = item
self.next = None
# 单向循环链表
class CycleSingleLinkList(object):
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""
链表是否为空
:return 链表为空返回真
"""
return self.__head is None
def length(self):
"""
计算链表长度
:return 链表长度
"""
if self.is_empty():
return 0
count = 1
cur = self.__head
while cur.next != self.__head:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
if self.is_empty():
print(None)
return
while cur.next != self.__head:
print(cur.item, end=' ')
cur = cur.next
print(cur.item)
def add(self, item):
"""
链表头部增加元素
:param item:要添加的具体数据
"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
self.__head = node
cur.next = self.__head
def append(self, item):
"""链表尾部增加元素"""
node = Node(item)
if self.is_empty():
node.next = node
self.__head = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头部添加元素
if pos <= 0:
self.add(item)
# 在尾部添加元素
elif pos >= self.length():
self.append(item)
# 在中间添加元素
else:
cur = self.__head
count = 0
while count < (pos-1):
count += 1
cur = cur.next
node = Node(item)
node.next = cur.next
cur.next = node
# 考虑没有节点、只有一个节点
# 考虑删除元素是头节点、尾节点还是中间节点
def remove(self, item):
"""删除元素"""
if self.is_empty():
return
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.item == item:
# 头部找到的元素
if cur == self.__head:
rear = self.__head
while rear.next != self.__head:
rear = rear.next
self.__head = cur.next
rear.next = cur.next
else:
pre.next = cur.next
return
# 不是要找的元素，就移动游标
pre = cur
cur = cur.next
# 退出循环，cur指向尾节点，需要单独处理
if cur.item == item:
# 链表只有一个节点
if cur == self.__head:
self.__head = None
return
pre.next = self.__head
def search(self, item):
"""查看元素是否存在"""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.item == item:
return True
cur = cur.next
if cur.item == item:
return True
return False
if __name__ == '__main__':
sll = CycleSingleLinkList()
print(sll.length()) # 0
sll.travel() # None
sll.append(1) # 1
sll.travel()
sll.append(2) # 1,2
sll.travel()
sll.add(3) # 3,1,2
sll.travel()
sll.insert(0, 4) # 4,3,1,2
sll.travel()
sll.insert(19, 5) # 4,3,1,2,5
sll.travel()
sll.insert(2, 6) # 4,3,6,1,2,5
sll.travel()
sll.remove(4) # 3,6,1,2,5
sll.travel()
sll.remove(5) # 3,6,1,2
sll.travel()
sll.remove(6) # 3,1,2
sll.travel()
sll.remove(3) # 1,2
sll.travel()
sll.remove(1) # 2
sll.travel()
sll.remove(2) # None
sll.travel()
更新中......
