〖Python〗 | 您所在的位置:网站首页 › python链表和列表一样吗 › 〖Python〗 |
【列表与链表】
列表
关于列表的存储: 列表开辟的内存空间是一块连续的内存,把这个内存等分成几份(单位是字节),他是连续存储的。 如果一个列表长度已满,再append添加元素的话,会在内存中重新开辟一个2倍的内存空间以存储新元素,原列表内存会被清除。 列表与链表复杂度: 1 2 3 4 5 6 7 8 9 10 11 12 按元素值查找: 按顺序查找,复杂度是一样的。 按二分查找,链表没法查找. 按下标查找: 列表是O(1) 链表是O(n) 在某元素后插入: 列表是O(n) 链表是O(1) 删除某元素: 列表是O(n) 链表是O(1) 链表------->列表相对应的数据结构链表是一种线性数据结构(与树形结构相对),不是进行连续存储的。 链表中每一个元素都是一个对象,每个对象称为一个节点,包含有数据域key和执行下一个节点的指针next。通过各个节点之间的相互连接,最终串联成一个链表。 1、存储的过程中,需要先创建节点,然后进行定义。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # 节点定义: class Node(object): def __init__(self,item): self.item = item # 数据域 self.next = None # 指针域 n1 = Node(1) n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 # 通过 n1 找到n3的值 print(n1.next.next.item)只保留头结点,执行第一个位置,剩下的都是next去指定。 2、链表遍历:(头节点的变动) 3、链表节点的插入和删除操作(非常方便,时间复杂度低) 插入: 删除: 4、建立链表(单链表) 1)头插法:是在head头节点的位置后插入数;得到的链表与原先的列表顺序是相反的。 2)尾插法:在链表的尾巴上插入。相当于是追加,必须时刻记住尾巴在哪儿 双链表中每个节点有两个指针:一个指向后面节点,一个指向前面节点。 1、节点定义: 1 2 3 4 5 class Node(object): def __init__(self,item=None): self.item = item # 记录当前值 self.next = None # 记录下一个值 self.prior = None # 记录前置的一个值2、双链表节点的插入和删除 1)插入: 1 2 3 4 5 p = Node(2) # 要插入的数 p.next = curNode.next # 指定插入数的next 是 当前数的next curNode.next.prior = p # 指定插入数的下一个数的 前置数为当前的数值 p.prior = curNode # 插入数的前置数为 标志位 curNode.next = p # 指定,标志位的next数是当前要插入的数2)删除: 1 2 3 4 p = curNode.next # 标志位的下一个数,要删除的数 curNode.next = p.next # 将next指向下一个数 p.next.prior = curNode# 将要删除数的下一个数的前置数改为标志位 del p # 删除当前数3、建立双链表 1 2 3 4 5 6 7 8 9 10 尾插法: def createLinkListR(li): l = Node() r = l for num in li: s = Node(num) r.next = s s.prior = r r = s return l,r 单链表逆置循环反转单链表。在循环的方法中,使用pre指向前一个节点,cur指向当前节点,每次把cur->next指向pre即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 # 创建节点 class Node(object): def __init__(self,item=None,next=None): self.item = item # 数据域 self.next = next # 指针域 # 循环逆置方法 def revLinkList(link): if link is None or link.next is None: return link pre = link # 记录当前节点的值 cur = link.next # 记录下一节点的值 pre.next = None # 先将当前节点的next指向定为None while cur: # 链表中一直有值 tmp = cur.next # 获取cur的下一个值,临时赋值给tmp cur.next = pre # 将cur值指向pre pre = cur # 重新指定 cur = tmp return pre # 把当前值返回 #应用 link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9))))))))) r = revLinkList(link): # 链表逆置之后,得到的head值 while r: print("{0}---->".format(r.item)) # 输出逆置后的当前值 r = r.next # 获取下一个,重新赋给r,然后交给上边输出 |
CopyRight 2018-2019 实验室设备网 版权所有 |