请选择 进入手机版 | 继续访问电脑版

[python] Python 列表与链表的区别详解

[复制链接]
查看25 | 回复8 | 2021-9-13 13:10:08 | 显示全部楼层 |阅读模式
目次

python 列表和链表的区别

python 中的 list 并不是我们传统意义上的列表,传统列表——通常也叫作链表(linked list)是由一系列节点来实现的,此中 每个节点都持有一个指向下一节点的引用。

  1. class Node:
  2. def __init__(self, value, next=None):
  3. self.value = value
  4. self.next = next
复制代码

接下来,我们就可以将全部 的节点构造成一个列表了:

  1. >>> L = Node("a", Node("b", Node("c", Node("d"))))
  2. >>> L.next.next.value
  3. 'c'
复制代码

这是一个所谓的单向链表,双向链表的各节点中还必要 持有一个指向前一个节点的引用

但 python 中的 list 则与此有所不同,它不是由多少 个独立的节点相互引用而成的,而是一整块单一连 续的内存区块,我们通常称之为“数组”(array),这直接导致了它与链表之间的一些紧张 区别。

比方 假如 我们要按既定的索引值对某一元素举行 直接访问的话,显然利用 数组会更有效 率。由于 ,在数组中,我们通常可以直接计算出目的 元素在内存中的位置,并对其举行 直接访问。而对于链表来说,我们必须从头开始遍历整个链表。

但是详细 到 insert 操作上,环境 又会有所不同。对于链表而言,只要知道了要在那里 实行 insert 操作,其操作成本黑白 常低的,无论该列表中有多少元素,其操作时间大致上是雷同 的。而数组就不一样了,它每次实行 insert 操作都必要 移动插入点右边的全部 元素,乃至 在必要的时间 ,我们大概 还必要 将这些列表元素团体 搬到一个更大的数组中去。

也正因云云 ,append 操作通常会采取一种被称为动态数组或‘向量'的指定办理 方案,其紧张 想法是将内存分配的过大一些,并且等到其溢出时,在线性时间内再次重新分配内存。但如许 做好像 会使 append 变得跟 insert一样糟糕。实在 不然,由于 只管 这两种环境 都大概 会迫使我们去搬动大量的元素,但紧张 不同点在于,对于 append 操作,发生如许 的大概 性要小得多。毕竟 上,假如 我们能确保每次所搬入的数组都大过原数组肯定 的比例(比方 大20%乃至 100%),那么该操作的匀称 成本(或者说得更确切一些,将这些搬运开销均派 到每次 append 操作中去)通常是常数!

数组数据是一连 的,一样寻常 必要 预先设定数据长度,不能顺应 数据动态的增减,当数据增长 是大概 超过预设值,必要 要重新分配内存,当数据减少时,预先申请的内存未利用 ,造成内存浪费。链表的数据由于 是随机存储的,以是 链表可以动态的分配内存,顺应 长度的动态变化

1.数组的元素是存放在栈中的,链表的元素在堆中
2.读取操作:数组时间复杂度为O(1),链表为O(n)
3.插入或删除操作:数据时间复杂度为O(n),链表为O(1)

列表
关于列表的存储:

列表开发 的内存空间是一块一连 的内存,把这个内存等分成几份(单位是字节),他是一连 存储的。
假如 一个列表长度已满,再append添加元素的话,会在内存中重新开发 一个2倍的内存空间以存储新元素,原列表内存会被扫除 。

列表与链表复杂度:

  1. 按元素值查找:
  2. 按顺序查找,复杂度是一样的。
  3. 按二分查找,链表没法查找.
  4. 按下标查找:
  5. 列表是O( 1 )
  6. 链表是O(n)
  7. 在某元素后插入:
  8. 列表是O(n)
  9. 链表是O( 1 )
  10. 删除某元素:
  11. 列表是O(n)
  12. 链表是O( 1 )
复制代码

链表------->列表相对应的数据布局
链表是一种线性数据布局 (与树形布局 相对),不是举行 一连 存储的。
链表中每一个元素都是一个对象,每个对象称为一个节点,包含有数据域key和实行 下一个节点的指针next。通过各个节点之间的相互毗连 ,终极 串联成一个链表。
1、存储的过程中,必要 先创建节点,然后举行 定义。

  1. # 节点定义:
  2. class Node( object ):
  3.    def __init__( self ,item):
  4. self .item = item # 数据域
  5. self . next = None # 指针域
  6. n1 = Node( 1 )
  7. n2 = Node( 2 )
  8. n3 = Node( 3 )
  9. n1. next = n2
  10. n2. next = n3
  11. # 通过 n1 找到n3的值
  12. print (n1. next . next .item)
复制代码

只保留头结点,实行 第一个位置,剩下的都是next去指定。

2、链表遍历:(头节点的变动)

在这里插入图片形貌

  1. # 节点定义:
  2. class Node( object ):
  3.    def __init__( self ,item):
  4. self .item = item # 数据域
  5. self . next = None # 指针域
  6. n1 = Node( 1 )
  7. n2 = Node( 2 )
  8. n3 = Node( 3 )
  9. n1. next = n2
  10. n2. next = n3
  11. # 通过 n1 找到n3的值
  12. print (n1. next . next .item)
复制代码

3、链表节点的插入和删除操作(非常方便,时间复杂度低)

插入:

在这里插入图片形貌

  1. p = Node( 5 ) # 要插入的值
  2. curNode = Node( 1 ) # 标志位
  3. # 顺序不能乱,否则就找不到原链表中的下一个值
  4. p. next = curNode. next # 指定插入值之后的值为标志位之后的值
  5. curNode. next = p # 然后再把原先的链next指向改成插入的值
复制代码

删除:

在这里插入图片形貌

  1. curNode 代表当前值
  2. p = curNode. next # 表示要删除的数
  3. curNode. next = p. next # 重新指定建立链表
  4. del p 删除数
复制代码

4、建立链表(单链表)

在这里插入图片形貌

1)头插法:是在head头节点的位置后插入数;得到的链表与原先的列表次序 是相反的。

在这里插入图片形貌

  1. def createLinkListF(li):
  2.   l = Node() # 始终指向头节点
  3.    for num in li:
  4. s = Node(num)
  5. s. next = l. next
  6. l. next = s
  7.    return l
复制代码

2)尾插法:在链表的尾巴上插入。相称 于是追加,必须时候 记住尾巴在哪儿

在这里插入图片形貌

  1. def createLinkListR(li):
  2.   l = Node()
  3.   r = l # r指向尾节点
  4.    for num in li:
  5. s = Node(num):
  6. r. next = s
  7. r = s # 重新指定尾节点
复制代码

双链表
双链表中每个节点有两个指针:一个指向后面节点,一个指向前面节点。

在这里插入图片形貌

1、节点定义:

  1. class Node( object ):
  2.    def __init__( self ,item = None ):
  3. self .item = item # 记录当前值
  4. self . next = None # 记录下一个值
  5. self .prior = None # 记录前置的一个值
复制代码

2、双链表节点的插入和删除

在这里插入图片形貌

  1. curNode = Node( 1 ) # 取一数据作为标志位
复制代码

1)插入:

  1. p = Node( 2 ) # 要插入的数
  2. p. next = curNode. next # 指定插入数的next 是 当前数的next
  3. curNode. next .prior = p # 指定插入数的下一个数的 前置数为当前的数值
  4. p.prior = curNode # 插入数的前置数为 标志位
  5. curNode. next = p # 指定,标志位的next数是当前要插入的数
复制代码

2)删除:

  1. p = curNode. next # 标志位的下一个数,要删除的数
  2. curNode. next = p. next # 将next指向下一个数
  3. p. next .prior = curNode # 将要删除数的下一个数的前置数改为标志位
  4. del p # 删除当前数
复制代码

3、建立双链表

  1. 尾插法:
  2. def createLinkListR(li):
  3.   l = Node()
  4.   r = l
  5.    for num in li:
  6. s = Node(num)
  7. r. next = s
  8. s.prior = r
  9. r = s
  10.    return l,r
复制代码

单链表逆置

在这里插入图片形貌

循环反转单链表。在循环的方法中,利用 pre指向前一个节点,cur指向当前节点,每次把cur->next指向pre即可。

  1. # 创建节点
  2. class Node( object ):
  3. def __init__( self ,item = None , next = None ):
  4. self .item = item # 数据域
  5. self . next = next # 指针域
  6. # 循环逆置方法
  7. def revLinkList(link):
  8. if link is None or link. next is None :
  9. return link
  10. pre = link # 记录当前节点的值
  11. cur = link. next # 记录下一节点的值
  12. pre. next = None # 先将当前节点的next指向定为None
  13. while cur: # 链表中一直有值
  14. tmp = cur. next # 获取cur的下一个值,临时赋值给tmp
  15. cur. next = pre # 将cur值指向pre
  16. pre = cur # 重新指定
  17. cur = tmp
  18. return pre # 把当前值返回
  19. #应用
  20. link = Node( 1 , Node( 2 , Node( 3 , Node( 4 , Node( 5 , Node( 6 , Node( 7 , Node( 8 , Node( 9 )))))))))
  21. r = revLinkList(link): # 链表逆置之后,得到的head值
  22. while r:
  23. print ( "{0}---->" . format (r.item)) # 输出逆置后的当前值
  24. r = r. next # 获取下一个,重新赋给r,然后交给上边输出
复制代码

列表的实现机制

Python 标准范例 list 就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的次序 (即保序),而且还具有以下举动 特性 :

  1. 基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1);为满足该特征,应该采用顺序表技术,表中元素保存在一块连续的存储区中。
  2. 允许任意加入元素,而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变。为满足该特征,就必须能更换元素存储区,并且为保证更换存储区时 list 对象的标识 id 不变,只能采用分离式实现技术。
复制代码

在 Python 的官方实现中,list 就是一种采用分离式技术实现的动态次序 表。这就是为什么用 list.append(x) (或 list.insert(len(list), x),即尾部插入)比在指定位置插入元素服从 高的缘故原由 。

在 Python 的官方实现中,list 实现采用了如下的策略:在建立空表(或者很小的表)时,体系 分配一块能容纳 8 个元素的存储区;在实行 插入操作(insert 或 append)时,假如 元素存储区满就换一块 4 倍大的存储区。但假如 此时的表已经很大(现在 的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方式,是为了避免出现过多空闲的存储位置。

列表的实现可以是数组或者链表。列表是一种次序 表,次序 表一样寻常 是数组。列表是一个线性表,它答应 用户在任何位置举行 插入、删除、访问和更换 元素。

列表的实现是基于数组或者基于链表布局 ,当利用 列表迭代器的时间 ,双向链表布局 比单链表布局 更快。
Python 中的列表英文名是 list,因此很轻易 与 C 语言中的链表搞混了,由于 在 C 语言中大家常常 给链表定名 为 list。毕竟 上 CPython,也是我们常见的用 C 语言开发 的 Python 表明 器,Python 语言底层是 C 语言实现的)中的列表根本不是列表。在 CPython 中列表被实现为长度可变的数组。

从细节上看,Python 中的列表是由其他对象的引用构成 的一连 数组,指向这个数组的指针及其长度被保存在一个列表头布局 中。这就意味着,每次添加或删除一个元素时,由引用构成 的数组必要 改变大小(重新分配)。荣幸 的是,Python在创建这些数组时采用了指数分配,以是 并不是每次操作都要改变数组的大小。但是,也由于 这个缘故原由 添加或者取出元素是平摊复杂度较低。不幸的是,在平凡 链表上“代价很小”的其他一些操作在 Python 中计算复杂度相对较高。

总的来说,Python中的列表是一个动态的次序 表,而次序 表大多是由数组实现的。

链表

链表是由很多 雷同 数据范例 的数据项按照特定的次序 分列 而成的线性表。链表中的数据项在计算机的内存中的位置是不一连 且随机的,然而列表是一连 的。链表数据的插入和删除是很方便的,但数据的查找服从 较低,不能像列表一样随机读取数据。
链表由一个一个的结点构成,每个结点由数据域和“指针域”构成 ,数据域存储数字,“指针域”指向下一个结点地点 的内存地址。(由于 Python 中没有指针这一概念的,这里的指针是一种指向)

  1. class Node(object):
  2. """节点"""
  3. def __init__(self, elem):
  4. self.elem = elem
  5. self.next = None
复制代码

链表封装的一系列操作:

  1. class SingleLinkList(object):
  2. """单链表"""
  3. def __init__(self, node=None):
  4. self.__head = node
  5. def is_empty(self):
  6. """链表是否为空"""
  7. return self.__head == None
  8. def length(self):
  9. """链表长度"""
  10. # cur游标,用来移动遍历节点
  11. cur = self.__head
  12. # count记录数量
  13. count = 0
  14. while cur != None:
  15. count += 1
  16. cur = cur.next
  17. return count
  18. def travel(self):
  19. """遍历整个链表"""
  20. cur = self.__head
  21. while cur != None:
  22. print(cur.elem, end=" ")
  23. cur = cur.next
  24. print("")
  25. def add(self, item):
  26. """链表头部添加元素,头插法"""
  27. node = Node(item)
  28. node.next = self.__head
  29. self.__head = node
  30. def append(self, item):
  31. """链表尾部添加元素, 尾插法"""
  32. node = Node(item)
  33. if self.is_empty():
  34. self.__head = node
  35. else:
  36. cur = self.__head
  37. while cur.next != None:
  38. cur = cur.next
  39. cur.next = node
  40. def insert(self, pos, item):
  41. """指定位置添加元素
  42. :param pos 从0开始
  43. """
  44. if pos <= 0:
  45. self.add(item)
  46. elif pos > (self.length()-1):
  47. self.append(item)
  48. else:
  49. pre = self.__head
  50. count = 0
  51. while count < (pos-1):
  52. count += 1
  53. pre = pre.next
  54. # 当循环退出后,pre指向pos-1位置
  55. node = Node(item)
  56. node.next = pre.next
  57. pre.next = node
  58. def remove(self, item):
  59. """删除节点"""
  60. cur = self.__head
  61. pre = None
  62. while cur != None:
  63. if cur.elem == item:
  64. # 先判断此结点是否是头节点
  65. # 头节点
  66. if cur == self.__head:
  67. self.__head = cur.next
  68. else:
  69. pre.next = cur.next
  70. break
  71. else:
  72. pre = cur
  73. cur = cur.next
  74. def search(self, item):
  75. """查找节点是否存在"""
  76. cur = self.__head
  77. while cur != None:
  78. if cur.elem == item:
  79. return True
  80. else:
  81. cur = cur.next
  82. return False
复制代码

链表与列表的差异

Python 中的 list(列表)并不是传统意义上的列表,传统的意义上的列表就是链表,不同地方在于链表在数据存储方面更加的自由,其带有指示下一个结点未知的指向,可以随意的存储数据。而列表则只能分配在一段一连 的存储空间里,且是作为一个团体 ,这就大大限定 了数据的变更操作,但其在举行 一些基础简单的操作时,时间复杂度极低。

list(列表):动态的次序 表
链表:存储地址分散的,必要 “指针”指向的线性表

链表插入删除服从 极高,达到O(1)。对于不必要 搜索 但变动频仍 且无法预知数目 上限的数据,比如内存池、操作体系 的历程 管理、网络通讯 协议栈的 trunk 管理等。乃至 就连很多脚本语言都有内置的链表、字典等基础数据布局 支持。

列表是一个线性的集合,它答应 用户在任何位置插入、删除、访问和更换 元素。
列表实现是基于数组或基于链表布局 的。当利用 列表迭代器的时间 ,双链表布局 比单链表布局 更快。
有序的列表是元素总是按照升序或者降序分列 的元素。

实现细节
python中的列表的英文名是list,因此很轻易 和别的 语言(C++, Java等)标准库中常见的链表混淆。毕竟 上CPython的列表根本不是列表(大概 换成英文明白 起来轻易 些:python中的list不是list)。在CPython中,列表被实现为长度可变的数组。

可参考《Python高级编程(第2版)》

从细节上看,Python中的列表是由对别的 对象的引用构成 的一连 数组。指向这个数组的指针及其长度被保存在一个列表头布局 中。这意味着,每次添加或删除一个元素时,由引用构成 的数组必要 该标大小(重新分配)。荣幸 的是,Python在创建这些数组时采用了指数分配,以是 并不是每次操作都必要 改变数组的大小。但是,也由于 这个缘故原由 添加或取出元素的平摊复杂度较低。

不幸的是,在平凡 链表上“代价很小”的别的 一些操作在Python中计算复杂度相对过高。

利用 list.insert(i,item) 方法在恣意 位置插入一个元素——复杂度O(N)
利用 list.pop(i) 或 list.remove(value) 删除一个元素——复杂度O(N)

列表的算法服从
可以采用时间复杂度来衡量:

index() O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains(in) O(n)
get slice[x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(nlogn)
multiply O(nk)

O括号内里 的值越大代表服从 越低

到此这篇关于Python 列表与链表的区别详解的文章就先容 到这了,更多相干 Python 列表与链表区别内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章盼望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 御风而行2017 | 2021-9-13 20:11:46 | 显示全部楼层
记得吃药!
回复

使用道具 举报

avatar 话筒他常te | 2021-9-13 20:50:01 | 显示全部楼层
admin楼主又闹绯闻了!
回复

使用道具 举报

avatar 123457166 | 2021-9-19 22:28:20 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,运动刷步数还是免费刷的,QQ和微信都可以刷,特别好用。访问地址:http://yd.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 宇宙无限 | 2021-10-4 09:54:58 | 显示全部楼层
收藏了,以后可能会用到!
回复

使用道具 举报

admin楼主给脑残下了定义!
回复

使用道具 举报

admin楼主是好人!
回复

使用道具 举报

admin楼主很有经验啊!
回复

使用道具 举报

avatar Deville | 4 小时前 | 显示全部楼层
admin楼主是我最崇拜的人!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则