美文网首页
数组链表的概念及区别

数组链表的概念及区别

作者: 人生苦短_我用Python | 来源:发表于2018-05-31 22:20 被阅读0次

    Python中的list

    python中的list并不是我们传统意义上的列表
    传统列表——通常也叫作链表(linked list)是由一系列节点来实现的,其中每个节点都持有一个指向下一节点的引用
    简单实现起来应该就像下面那样:

    class Node:
        def __init__(self, value, next=None):
            self.value = value
            self.next = next
    

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

    >>> L = Node("a", Node("b", Node("c", Node("d"))))
    >>> L.next.next.value
    '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)


    相关文章

      网友评论

          本文标题:数组链表的概念及区别

          本文链接:https://www.haomeiwen.com/subject/pgsjjftx.html