1.链表

1.1 基本原理

• 节点
  • 组成链表的数据格子不是连续的。可以分布在内存的各个位置。这种不相邻的格子就叫结点。
  • 每个结点保存数据还保存着链表里的下一结点的内存地址。
• 链表(Linkedlist)
  • 链表结构相对于顺序表可以充分利用计算机内存空间。
  • 实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。
  • 是一种常见的基础数据结构，是一种线性表

1.2 链表大O记法表示

操作	大O记法表示【最坏情况】默认采用	大O记法表示【最好情况】
读取	O($N$)	O(1)
查找	O($N$)	O(1)
插入	O($N$)	O(1)
删除	O($N$)	O(1)

2. 链表操作

2.1 读取

• 链表的结点可以分布在内存的任何位置。
• 根据索引读取
• 读取值：必须先读取索引为0的链，顺着该链去找索引1。根据索引 1 的链去找索引 2…最终找到自己要读取的值。
  

2.2 查找

• 根据值查找是否存在
• 根据读取一样，在读取每个索引节点时，读取值判断是否与查找的值相等，否则读取下一个节点，直到末尾未找到值。
  

2.3 插入

• 开头插入：创建新节点，将新节点链表指向的下一个内存地址为原先链表头部即可
• 中间插入：创建新节点，读取链表索引0，根据索引0找到下一个节点，依此类推找到要插入的位置，将插入索引前面的索引节点链表指向的下一个内存地址为新节点位置，将新节点指向的下一个内存地址为插入索引后面的索引节点
• 末尾插入：创建新节点，读取链表索引0，根据索引0找到下一个节点，依此类推找到末尾位置，将末尾内存节点null设置为新节点的内存地址，将新节点指向的下一个内存地址设为null
  

2.4 删除

• 开头删除：将链表的第二个节点设置为第一个节点即可
• 中间删除：遍历链表，遍历到要删除的索引，将删除的前一个节点指向下一个内存地址重新指向删除节点的后一个节点即可
• 末尾删除：遍历链表，遍历到倒数第二个节点，将此节点指向的下一个节点地址设为null即可
  

3.链表代码实现

# 节点封装
class Node():def __init__(self, item):self.item = itemself.next = None# 链表封装
class Link():def __init__(self):  # 构建一个空链表self._head = None  # _head永远要指向链表中的第一个节点，None表示链表没有节点# 读取操作def read(self,index):count = 0current = self._headwhile True:if count!=index:count += 1current = current.nextelse:item=current.itemprint(f'索引{index}的值为:{item}')breakreturn item# 查找操作def search(self, item):  # 查找节点是否存在current = self._headfind = Falsecount=0while current:if current.item == item:find = Trueprint(f'值为{item}的索引为:{count}')breakelse:current = current.nextcount+=1return find# 插入操作def add(self, item):  # 开头插入node = Node(item) # 实例化一个新的节点node.next = self._headself._head = nodedef insert(self, pos, item):  # 中间插入node = Node(item)current = self._headtemp = None# 单独判断插入位置为0的节点if pos == 0:self.add(item)# node.next = self._head# self._head = nodereturnfor i in range(pos):temp = currentcurrent = current.nexttemp.next = nodenode.next = currentdef append(self, item):  # 尾部插入# 实例化一个新的节点node = Node(item)# 如果链表为空if self._head == None:self._head = node# 如果链表为非空temp = Nonecurrent = self._headwhile current:temp = currentcurrent = current.nexttemp.next = node# 删除操作def delete(self, item):  # 将item对应的节点删除current = self._headtemp = Noneif current.item == item:  # 删除的节点是第一个节点self._head = current.nextreturnwhile current:temp = currentcurrent = current.nextif current.item == item:temp.next = current.nextreturn# 遍历整个链表def travel(self):# print(self._head.item)# print(self._head.next.item)# print(self._head.next.next.item)# current指向第一个节点# _head永远要指向第一个节点，轻易不要修改_head指向current = self._headwhile current:print(current.item,end='\t')current = current.nextprint('\n')def isEmpty(self):  # 链表是否为空return self._head == Nonedef length(self):  # 返回列表中节点的个数count = 0current = self._headwhile current:count += 1current = current.nextreturn count# 翻转def reverse(self):pre = self._headcur = pre.nextnext_node = cur.nextpre.next = Nonewhile True:cur.next = prepre = curcur = next_nodeif next_node != None:next_node = next_node.nextelse:breakself._head = pre
link = Link()
# 插入
# 头部
for i in range(1,6):link.add(i)
print('头部添加元素链表为:',end='')
link.travel()# 中间
link.insert(1, 1234)
print('中间添加元素链表为【(1, 1234)】:',end='')
link.travel()# 尾部
link.append(12)
print('尾部添加元素12链表为:',end='')
link.travel()# 读取
link.read(1)# 查找
link.search(4)# 删除
link.delete(3)
print('删除元素3后链表为:',end='')
link.travel()print("链表长度为:"+str(link.length()))
print("链表反转后值为:")
link.reverse()
link.travel()