一、链表简介

链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。

二、单向链表

单向链表也叫单链表，是链表中最简单的形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

head 保存首地址，item 存储数据，next 指向下一结点地址。

链表失去了序列的随机读取优点，同时链表增加了指针域，空间开销也较大，但它对存储空间的使用要相对灵活。

列如：有一堆数据[1,2,3,5,6,7]，要在3和5之间插入4, 如果用数组，需要将5之后的数据都往后退一位，然后再插入4，这样非常麻烦，但是如果用链表，我就直接在3和5之间插入4就行。

1. 定义结点

结点的数据结构为数据元素(item)与 指针(next)

class Node(object):"""单链表的结点"""def __init__(self, item):# item存放数据元素self.item = item# next是下一个节点的标识self.next = None

2. 定义链表

链表需要具有首地址指针head。

class SingleLinkList(object):"""单链表"""def __init__(self):self._head = None

示例：创建链表

if __name__ == '__main__':# 创建链表link_list = SingleLinkList()# 创建结点node1 = Node(1)node2 = Node(2)# 将结点添加到链表link_list._head = node1# 将第一个结点的next指针指向下一结点node1.next = node2# 访问链表print(link_list._head.item)# 访问第一个结点数据print(link_list._head.next.item)# 访问第二个结点数据

是不是感觉很麻烦，所以我们要在链表中增加操作方法。

• is_empty() 链表是否为空
• length() 链表长度
• items() 获取链表数据迭代器
• add(item) 链表头部添加元素
• append(item) 链表尾部添加元素
• insert(pos, item) 指定位置添加元素
• remove(item) 删除节点
• find(item) 查找节点是否存在

代码如下：

class SingleLinkList(object):"""单链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 初始指针指向headcur = self._headcount = 0# 指针指向None 表示到达尾部while cur is not None:count += 1# 指针下移cur = cur.nextreturn countdef items(self):"""遍历链表"""# 获取head指针cur = self._head# 循环遍历while cur is not None:# 返回生成器yield cur.item# 指针下移cur = cur.nextdef add(self, item):"""向链表头部添加元素"""node = Node(item)# 新结点指针指向原头部结点node.next = self._head# 头部结点指针修改为新结点self._head = nodedef append(self, item):"""尾部添加元素"""node = Node(item)# 先判断是否为空链表if self.is_empty():# 空链表，_head 指向新结点self._head = nodeelse:# 不是空链表，则找到尾部，将尾部next结点指向新结点cur = self._headwhile cur.next is not None:cur = cur.nextcur.next = nodedef insert(self, index, item):"""指定位置插入元素"""# 指定位置在第一个元素之前，在头部插入if index <= 0:self.add(item)# 指定位置超过尾部，在尾部插入elif index > (self.length() - 1):self.append(item)else:# 创建元素结点node = Node(item)cur = self._head# 循环到需要插入的位置for i in range(index - 1):cur = cur.nextnode.next = cur.nextcur.next = nodedef remove(self, item):"""删除节点"""cur = self._headpre = Nonewhile cur is not None:# 找到指定元素if cur.item == item:# 如果第一个就是删除的节点if not pre:# 将头指针指向头节点的后一个节点self._head = cur.nextelse:# 将删除位置前一个节点的next指向删除位置的后一个节点pre.next = cur.nextreturn Trueelse:# 继续按链表后移节点pre = curcur = cur.nextdef find(self, item):"""查找元素是否存在"""return item in self.items()

示例：操作链表

if __name__ == '__main__':link_list = SingleLinkList()# 向链表尾部添加数据for i in range(5):link_list.append(i)# 向头部添加数据link_list.add(6)# 遍历链表数据for i in link_list.items():print(i, end='\t')# 链表数据插入数据link_list.insert(3, 9)print('\n', list(link_list.items()))# 删除链表数据link_list.remove(0)# 查找链表数据print(link_list.find(4))

三、循环链表

单向循环链表为单向链表的变种，链表的最后一个next指向链表头，新增一个循环。

1. 循环链表结点

class Node(object):"""链表的结点"""def __init__(self, item):# item存放数据元素self.item = item# next是下一个节点的标识self.next = None

2. 定义循环链表

class SingleCycleLinkList(object):def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 链表为空if self.is_empty():return 0# 链表不为空count = 1cur = self._headwhile cur.next != self._head:count += 1# 指针下移cur = cur.nextreturn countdef items(self):""" 遍历链表 """# 链表为空if self.is_empty():return# 链表不为空cur = self._headwhile cur.next != self._head:yield cur.itemcur = cur.nextyield cur.itemdef add(self, item):""" 头部添加结点"""node = Node(item)if self.is_empty():# 为空self._head = nodenode.next = self._headelse:# 添加结点指向headnode.next = self._headcur = self._head# 移动结点，将末尾的结点指向nodewhile cur.next != self._head:cur = cur.nextcur.next = node# 修改 head 指向新结点self._head = nodedef append(self, item):"""尾部添加结点"""node = Node(item)if self.is_empty():# 为空self._head = nodenode.next = self._headelse:# 寻找尾部cur = self._headwhile cur.next != self._head:cur = cur.next# 尾部指针指向新结点cur.next = node# 新结点指针指向headnode.next = self._headdef insert(self, index, item):""" 指定位置添加结点"""if index <= 0:# 指定位置小于等于0，头部添加self.add(item)# 指定位置大于链表长度，尾部添加elif index > self.length() - 1:self.append(item)else:node = Node(item)cur = self._head# 移动到添加结点位置for i in range(index - 1):cur = cur.next# 新结点指针指向旧结点node.next = cur.next# 旧结点指针 指向 新结点cur.next = nodedef remove(self, item):""" 删除一个结点 """if self.is_empty():returncur = self._headpre = Node# 第一个元素为需要删除的元素if cur.item == item:# 链表不止一个元素if cur.next != self._head:while cur.next != self._head:cur = cur.next# 尾结点指向 头部结点的下一结点cur.next = self._head.next# 调整头部结点self._head = self._head.nextelse:# 只有一个元素self._head = Noneelse:# 不是第一个元素pre = self._headwhile cur.next != self._head:if cur.item == item:# 删除pre.next = cur.nextreturn Trueelse:pre = cur# 记录前一个指针cur = cur.next# 调整指针位置# 当删除元素在末尾if cur.item == item:pre.next = self._headreturn Truedef find(self, item):""" 查找元素是否存在"""return item in self.items()if __name__ == '__main__':link_list = SingleCycleLinkList()print(link_list.is_empty())# 头部添加元素for i in range(5):link_list.add(i)print(list(link_list.items()))# 尾部添加元素for i in range(6):link_list.append(i)print(list(link_list.items()))# 添加元素link_list.insert(3, 45)print(list(link_list.items()))# 删除元素link_list.remove(5)print(list(link_list.items()))# 元素是否存在print(4 in link_list.items())

四、双向链表

双向链表比单向链表更加复杂，它每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个链接指向下一个节点，当此节点为最后一个节点时，指向空值。

head 保存首地址，item 存储数据，next 指向下一结点地址，prev 指向上一结点地址。

1. 定义双向链表结点

class Node(object):"""双向链表的结点"""def __init__(self, item):# item存放数据元素self.item = item# next 指向下一个节点的标识self.next = None# prev 指向上一结点self.prev = None

2. 定义双向链表

class BilateralLinkList(object):"""双向链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 初始指针指向headcur = self._headcount = 0# 指针指向None 表示到达尾部while cur is not None:count += 1# 指针下移cur = cur.nextreturn countdef items(self):"""遍历链表"""# 获取head指针cur = self._head# 循环遍历while cur is not None:# 返回生成器yield cur.item# 指针下移cur = cur.nextdef add(self, item):"""向链表头部添加元素"""node = Node(item)if self.is_empty():# 头部结点指针修改为新结点self._head = nodeelse:# 新结点指针指向原头部结点node.next = self._head# 原头部 prev 指向 新结点self._head.prev = node# head 指向新结点self._head = nodedef append(self, item):"""尾部添加元素"""node = Node(item)if self.is_empty():# 链表无元素# 头部结点指针修改为新结点self._head = nodeelse:# 链表有元素# 移动到尾部cur = self._headwhile cur.next is not None:cur = cur.next# 新结点上一级指针指向旧尾部node.prev = cur# 旧尾部指向新结点cur.next = nodedef insert(self, index, item):""" 指定位置插入元素"""if index <= 0:self.add(item)elif index > self.length() - 1:self.append(item)else:node = Node(item)cur = self._headfor i in range(index):cur = cur.next# 新结点的向下指针指向当前结点node.next = cur# 新结点的向上指针指向当前结点的上一结点node.prev = cur.prev# 当前上一结点的向下指针指向nodecur.prev.next = node# 当前结点的向上指针指向新结点cur.prev = nodedef remove(self, item):""" 删除结点 """if self.is_empty():returncur = self._head# 删除元素在第一个结点if cur.item == item:# 只有一个元素if cur.next is None:self._head = Nonereturn Trueelse:# head 指向下一结点self._head = cur.next# 下一结点的向上指针指向Nonecur.next.prev = Nonereturn True# 移动指针查找元素while cur.next is not None:if cur.item == item:# 上一结点向下指针指向下一结点cur.prev.next = cur.next# 下一结点向上指针指向上一结点cur.next.prev = cur.prevreturn Truecur = cur.next# 删除元素在最后一个if cur.item == item:# 上一结点向下指针指向Nonecur.prev.next = Nonereturn Truedef find(self, item):"""查找元素是否存在"""return item in self.items()