- Python数据结构&算法(02) 链表
- 2.1 基本概念
- 2.2 链表基本操作
- 2.2.1 链表初始化
- 2.2.2 链表插入
- 2.2.3 链表删除
- 2.2.4 单链表实现代码
- 2.3 链表变种
- 2.3.1 双链表
- 2.3.1.1 双链表初始化
- 2.3.1.2 双链表插入
- 2.3.1.3 双链表删除
- 2.3.1.4 双链表实现代码
- 2.3.2 循环链表
- 2.3.2.1 循环链表初始化
- 2.3.2.2 循环链表插入
- 2.3.2.3 循环链表删除
- 2.3.2.4 循环链表实现代码
- 2.3.3 双向循环链表
链式存储结构的特点是用一组任意的存储单元存储一组数据元素，这些存储单元可以是连续的或是不连续的，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素而言除了需要存储其本身的信息之外还需要存储一个指示其直接后续的信息。这两部分信息构成了数据元素的存储映像，称为结点。
每个结点中包含两个域，其中存储数据元素信息的域称为数据域，存储直接后继元素存储位置的域称为指针域。指针域中存储的信息称作指针或链。
在链表中数据元素之间的逻辑关系是由结点中的指针指示的，换句话说指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理地址不要求相连，因此这种存储结构为非顺序映像或链式映像。
2.2 链表基本操作抽象数据类型链表的定义如下：
ADT List{
数据对象：D = {ai | ai ∈ elemset, i = 1, 2, ..., n, n >= 0}
数据关系：R = { | ai-1, ai ∈ D, i = 2, ..., n}
基本操作：
初始化链表
插入元素
删除第i个元素
清空链表
判定链表是否为空
返回链表中元素个数
获取第i个元素的值
通过值定位第一个符合的元素的序号
获取第i个元素前驱结点的值
获取第i个元素后驱结点的值
遍历链表
}
2.2.1 链表初始化
在python中，我们可以使用类代替C语言中的结构体完成链表的初始化。根据链表的定义，需要规定每个结点的存储数据以及链接下一个结点的指针。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class LinkList:
def __init__(self):
self.__head = Node(-1)
2.2.2 链表插入
链表中元素的插入可以分为两种：头插法以及尾插法，实际使用中也经常会设计到在第 i 个元素之前或之后插入元素，因此我们必须要了解链表插入的原理。
由于链表是一种非顺序存储映像，其指定直接后续的方式是使用指针存储后续单元的地址，因此在插入的过程中需要修改当前单元的指针。
头插法即在头结点之后进行元素插入，最终形成的链表顺序是与输入相反的。首先需要将头结点的后续结点指派给要插入的新结点，之后将头结点的后续结点指派为新结点。注意这两步的操作顺序是不可颠倒的，如果先将新结点指派为头结点的后续结点，则会丢失原先头结点的后续结点，原理图如下：
尾插法则是在链表最末尾插入新结点，每次需要遍历到最后一个结点，将最后一个结点的指针指向新结点即可。这样创建的链表和输入的顺序一致，原理图如下：
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class LinkList:
def __init__(self):
self.__head = Node(-1)
def insertHead(self, elem):
newNode = Node(elem)
newNode.next = self.__head.next # 将头结点的后续结点链接到新结点的指针
self.__head.next = newNode # 将新结点链接到头结点的指针
def insertRear(self, elem):
newNode = Node(elem) # 定义新结点
nowNode = self.__head # 从头结点开始遍历直到最后一个结点
while nowNode.next != None:
nowNode = nowNode.next
nowNode.next = newNode # 将新结点链接到最后一个结点的指针
2.2.3 链表删除
在学习完如何在链表中插入元素之后，我们需要了解如何删除链表中的某个元素，这里我们使用序号来寻找删除的第 i 个元素。和链表插入结点原理相似，删除某个结点只需要将该结点的前置结点的指针指向被删除结点的后续结点即可，这在单链表中就可以做到在遍历时跳过该删除结点直接访问其下一个结点。注意，在C语言中需要将被删除的结点释放（从内存空间中清除）。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class LinkList:
def __init__(self):
self.__head = Node(-1)
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next != None:
num = num + 1 # 由于要找到被删除结点的前置结点，每次遍历前先将结点序号加一并进行比对，满足则当前结点即为前置结点
if num == index:
nowNode.next = nowNode.next.next
break
else:
nowNode = nowNode.next
2.2.4 单链表实现代码
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class LinkList:
def __init__(self):
self.__head = Node(-1)
def insertHead(self, elem):
newNode = Node(elem)
newNode.next = self.__head.next # 将头结点的后续结点链接到新结点的指针
self.__head.next = newNode # 将新结点链接到头结点的指针
def insertRear(self, elem):
newNode = Node(elem) # 定义新结点
nowNode = self.__head # 从头结点开始遍历直到最后一个结点
while nowNode.next != None:
nowNode = nowNode.next
nowNode.next = newNode # 将新结点链接到最后一个结点的指针
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next != None:
num = num + 1 # 由于要找到被删除结点的前置结点，每次遍历前先将结点序号加一并进行比对，满足则当前结点即为前置结点
if num == index:
nowNode.next = nowNode.next.next
break
else:
nowNode = nowNode.next
def clear(self):
self.__head.next = None
def isEmpty(self):
return self.__head.next == None
def num(self):
nowNode = self.__head
num = 0
while nowNode.next != None:
nowNode = nowNode.next # 由于头结点不计入链表长度，因此先进入下一个结点再改变长度
num = num + 1
return num
def returnValue(self, index):
nowNode = self.__head
num = 0
while nowNode.next != None:
nowNode = nowNode.next
num = num + 1
if num == index:
return nowNode.elem
def returnIndex(self, elem):
nowNode = self.__head
num = 0
while nowNode.next != None:
nowNode = nowNode.next
num = num + 1
if nowNode.elem == elem:
return num
def returnPre(self, index):
if index == 1:
print("Error!")
return
nowNode = self.__head
num = 0
while nowNode.next != None:
num = num + 1
if num == index:
return nowNode.elem
else:
nowNode = nowNode.next
def returnNext(self, index):
num = self.num()
if index == num:
print("Error!")
return
nowNode = self.__head
num = 0
while nowNode.next != None:
nowNode = nowNode.next
num = num + 1
if num == index:
return nowNode.next.elem
def printLinkList(self):
nowNode = self.__head.next
while nowNode != None:
print(nowNode.elem)
nowNode = nowNode.next
if __name__ == "__main__":
L = LinkList()
for i in range(1, 10):
L.insertRear(i)
print(L.num(), 'n')
L.printLinkList()
2.3 链表变种
在学会了单链表的基础上，链表还有额外两种变种形式，分别为双链表以及循环链表，还有比较复杂的双向循环链表。
2.3.1 双链表双链表和单链表的区别在于单链表只有一个指向其后继结点的指针，而双链表还包含了指向其前置结点的指针，这就造成了双链表在插入和删除结点中比单链表更加复杂的情况。
2.3.1.1 双链表初始化根据链表的定义，需要规定每个结点的存储数据、链接上一个以及下一个结点的指针。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.prior = None
self.next = None
class DoubleLinkList:
def __init__(self):
self.__head = Node(-1)
2.3.1.2 双链表插入
与单链表相同，这里介绍头插法以及尾插法两种双链表插入结点的方式。
对于头插法，首先需要判定是不是插入的第一个元素，即 self.__head.next == None。如果是第一个插入的元素，则只需要将新结点链接到头结点的后继指针且将头结点链接到新结点的前置指针即可；如果不是第一个元素，则需要先将新结点链接到头结点的后继结点的前置指针，且将头结点的原后继结点链接到新结点的后继指针，之后才能将新结点链接到头结点的后继指针且将头结点链接到新结点的前置指针。注意这个过程同样是不可颠倒的。由于文字说明过于复杂，这里附上原理图：
对于尾插法，只需要遍历到最后一个结点，将新结点链接到最后一个结点的后继指针并且将最后一个结点链接到新结点的前置指针即可，原理图如下：
class Node:
def __init__(self, elem=None):
self.elem = elem
self.prior = None
self.next = None
class DoubleLinkList:
def __init__(self):
self.__head = Node(-1)
def insertHead(self, elem):
newNode = Node(elem)
if self.__head.next != None: # 如果不是第一个插入的结点
self.__head.next.prior = newNode # 新结点链接头结点的后继结点的前置指针
newNode.next = self.__head.next # 头结点的后继结点链接新结点的后继指针
self.__head.next = newNode # 新结点链接头结点的后继指针
newNode.prior = self.__head # 头结点链接新结点的前置指针
def insertRear(self, elem):
newNode = Node(elem)
nowNode = self.__head
while nowNode.next != None: # 遍历到最后一个结点
nowNode = nowNode.next
nowNode.next = newNode # 新结点链接最后一个结点的后继结点
newNode.prior = nowNode # 最后一个结点链接新结点的前置结点
2.3.1.3 双链表删除
对比单链表删除，双链表删除除了需要将删除结点的后继结点链接到删除结点的前置结点的后继指针外，还需要将删除结点的前置结点链接到删除结点的后继结点的前置指针，并且顺序应当是先后继结点链接前置后前置结点链接后继，同时也需要考虑删除结点是否为最后一个结点，原理图如下：
class Node:
def __init__(self, elem=None):
self.elem = elem
self.prior = None
self.next = None
class DoubleLinkList:
def __init__(self):
self.__head = Node(-1)
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next != None:
num = num + 1
if num == index:
if nowNode.next.next != None: # 如果被删除的结点不是最后一个结点
nowNode.next.next.prior = nowNode # 被删除结点的前置结点链接被删除的结点的后继结点的前置指针
nowNode.next = nowNode.next.next # 被删除结点的后继结点链接被删除的结点的前置结点的后继指针
else:
nowNode.next = None # 如果被删除结点是最后一个结点，被删除结点的前置结点的后继指针指空
else:
nowNode = nowNode.next
2.3.1.4 双链表实现代码
class Node:
def __init__(self, elem=None):
self.elem = elem
self.prior = None
self.next = None
class DoubleLinkList:
def __init__(self):
self.__head = Node(-1)
def insertHead(self, elem):
newNode = Node(elem)
if self.__head.next != None: # 如果不是第一个插入的结点
self.__head.next.prior = newNode # 新结点链接头结点的后继结点的前置指针
newNode.next = self.__head.next # 头结点的后继结点链接新结点的后继指针
self.__head.next = newNode # 新结点链接头结点的后继指针
newNode.prior = self.__head # 头结点链接新结点的前置指针
def insertRear(self, elem):
newNode = Node(elem)
nowNode = self.__head
while nowNode.next != None: # 遍历到最后一个结点
nowNode = nowNode.next
nowNode.next = newNode # 新结点链接最后一个结点的后继结点
newNode.prior = nowNode # 最后一个结点链接新结点的前置结点
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next != None:
num = num + 1
if num == index:
if nowNode.next.next != None: # 如果被删除的结点不是最后一个结点
nowNode.next.next.prior = nowNode # 被删除结点的前置结点链接被删除的结点的后继结点的前置指针
nowNode.next = nowNode.next.next # 被删除结点的后继结点链接被删除的结点的前置结点的后继指针
else:
nowNode.next = None # 如果被删除结点是最后一个结点，被删除结点的前置结点的后继指针指空
else:
nowNode = nowNode.next
def printDoubleLinkList(self):
nowNode = self.__head.next
while nowNode != None:
print(nowNode.elem)
nowNode = nowNode.next
def printDoubleLinkListReverse(self):
nowNode = self.__head.next
while nowNode.next != None:
nowNode = nowNode.next
while nowNode.elem != -1:
print(nowNode.elem)
nowNode = nowNode.prior
if __name__ == "__main__":
DL = DoubleLinkList()
for i in range(1, 3):
DL.insertRear(i)
DL.printDoubleLinkList()
2.3.2 循环链表
循环链表顾名思义就是将两边的头尾串在一起形成一个环，在遍历时如果不设置停止条件就会一直循环下去。
2.3.2.1 循环链表初始化循环链表需要在单链表的基础上将头结点链接到其自身的后继指针上以形成一个环。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class CircularLinkList:
def __init__(self):
self.__head = Node(-1)
self.__head.next = self.__head
2.3.2.2 循环链表插入
头插法与单链表头插法相同；
相对于单链表，尾插法需要判定何时到达链表尾部（头结点的前一个结点），这时可以检查下一个结点的值是否为头结点的特设值（即永远不会与其他结点的值相同，该例中设置为 -1）。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class CircularLinkList:
def __init__(self):
self.__head = Node(-1)
self.__head.next = self.__head
def insertHead(self, elem):
newNode = Node(elem)
newNode.next = self.__head.next # 头结点的后继结点链接到新结点的后继指针
self.__head.next = newNode # 新结点链接到头结点的后继指针
def insertRear(self, elem):
newNode = Node(elem)
nowNode = self.__head.next
if nowNode.elem == self.__head.elem: # 如果当前只有头结点
newNode.next = self.__head
self.__head.next = newNode
else:
while nowNode.next.elem != self.__head.elem: # 遍历到最后一个结点
nowNode = nowNode.next
newNode.next = nowNode.next # 最后一个结点的后继结点（头结点）链接到新结点的后继指针
nowNode.next = newNode # 新结点链接到最后一个结点的后继指针
2.3.2.3 循环链表删除
使用序号寻找结点时同样也需要设定遍历一遍后停止，否则会造成死循环。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class CircularLinkList:
def __init__(self):
self.__head = Node(-1)
self.__head.next = self.__head
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next.elem != self.__head.elem:
num = num + 1
if num == index:
nowNode.next = nowNode.next.next
break
else:
nowNode = nowNode.next
def printCircularLinkList(self):
nowNode = self.__head
while nowNode.next.elem != self.__head.elem:
nowNode = nowNode.next
print(nowNode.elem)
2.3.2.4 循环链表实现代码
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
class CircularLinkList:
def __init__(self):
self.__head = Node(-1)
self.__head.next = self.__head
def insertHead(self, elem):
newNode = Node(elem)
newNode.next = self.__head.next # 头结点的后继结点链接到新结点的后继指针
self.__head.next = newNode # 新结点链接到头结点的后继指针
def insertRear(self, elem):
newNode = Node(elem)
nowNode = self.__head.next
if nowNode.elem == self.__head.elem: # 如果当前只有头结点
newNode.next = self.__head
self.__head.next = newNode
else:
while nowNode.next.elem != self.__head.elem: # 遍历到最后一个结点
nowNode = nowNode.next
newNode.next = nowNode.next # 最后一个结点的后继结点（头结点）链接到新结点的后继指针
nowNode.next = newNode # 新结点链接到最后一个结点的后继指针
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next.elem != self.__head.elem:
num = num + 1
if num == index:
nowNode.next = nowNode.next.next
break
else:
nowNode = nowNode.next
def printCircularLinkList(self):
nowNode = self.__head
while nowNode.next.elem != self.__head.elem:
nowNode = nowNode.next
print(nowNode.elem)
if __name__ == "__main__":
CL = CircularLinkList()
for i in range(1, 10):
CL.insertRear(i)
CL.printCircularLinkList()
2.3.3 双向循环链表
双向循环链表是一种结合了双向链表和循环链表特点的链表，这里只提供实现代码，不再进行讲解。
class Node:
def __init__(self, elem=None):
self.elem = elem
self.next = None
self.prior = None
class DoubleCircularLinkList:
def __init__(self):
self.__head = Node(-1)
self.__head.next = self.__head
self.__head.prior = self.__head
def insertHead(self, elem):
newNode = Node(elem)
self.__head.next.prior = newNode
newNode.next = self.__head.next
self.__head.next = newNode
newNode.prior = self.__head
def insertRear(self, elem):
newNode = Node(elem)
nowNode = self.__head.prior
self.__head.prior = newNode
newNode.next = self.__head
nowNode.next = newNode
newNode.prior = nowNode
def delete(self, index):
nowNode = self.__head
num = 0
while nowNode.next.elem != self.__head.elem:
num = num + 1
if num == index:
nowNode.next = nowNode.next.next
break
else:
nowNode = nowNode.next
def printDoubleCircularLinkList(self):
nowNode = self.__head
while nowNode.next.elem != self.__head.elem:
nowNode = nowNode.next
print(nowNode.elem)
if __name__ == "__main__":
DCL = DoubleCircularLinkList()
for i in range(1, 10):
DCL.insertRear(i)
DCL.printDoubleCircularLinkList()
