漫画风格网站,人物介绍网页模板html,自贡市工程造价信息网,未来网站建设想法链表基本原理1.链表1.1 基本原理1.2 链表大O记法表示2. 链表操作2.1 读取2.2 查找2.3 插入2.4 删除3.链表代码实现1.链表
1.1 基本原理
节点 组成链表的数据格子不是连续的。可以分布在内存的各个位置。这种不相邻的格子就叫结点。每个结点保存数据还保存着链表里的下一结点的…
链表基本原理1.链表1.1 基本原理1.2 链表大O记法表示2. 链表操作2.1 读取2.2 查找2.3 插入2.4 删除3.链表代码实现1.链表
1.1 基本原理
节点 组成链表的数据格子不是连续的。可以分布在内存的各个位置。这种不相邻的格子就叫结点。每个结点保存数据还保存着链表里的下一结点的内存地址。 链表(Linkedlist) 链表结构相对于顺序表可以充分利用计算机内存空间。实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。是一种常见的基础数据结构是一种线性表
1.2 链表大O记法表示
操作大O记法表示【最坏情况】默认采用大O记法表示【最好情况】读取O(NNN)O(1)查找O(NNN)O(1)插入O(NNN)O(1)删除O(NNN)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:itemcurrent.itemprint(f索引{index}的值为:{item})breakreturn item# 查找操作def search(self, item): # 查找节点是否存在current self._headfind Falsecount0while current:if current.item item:find Trueprint(f值为{item}的索引为:{count})breakelse:current current.nextcount1return 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()
