Python列表是單列還是雙列鏈表？

我想知道使用append（）構建的Python v2.7列表的複雜性順序是什麼？ Python列表是雙重鏈接的，因此它是不變的複雜性，還是單個鏈接，因此線性複雜？如果它是單獨鏈接的，那麼我怎麼能夠在線性時間內從迭代中建立一個列表，以從頭到尾的順序提供列表的值？Python列表是單列還是雙列鏈表？

例如：

def holes_between(intervals): 
    # Compute the holes between the intervals, for example: 
    #  given the table: ([ 8, 9] [14, 18] [19, 20] [23, 32] [34, 49]) 
    # compute the holes: ([10, 13] [21, 22] [33, 33]) 
    prec = intervals[0][1] + 1 # Bootstrap the iteration 
    holes = [] 
    for low, high in intervals[1:]: 
    if prec <= low - 1: 
     holes.append((prec, low - 1)) 
    prec = high + 1 
    return holes

來源

2013-02-27 WilliamKF

根本不是鏈表。它基本上被稱爲動態數組。你從哪裏知道這是一個鏈表？ – delnan 2013-02-27 20:42:58

@delnan排序。與某些其他語言不同，它不是靜態的，否則「追加」根本不起作用。它更接近Java的ArrayLists，以及其他語言中的類似結構。請參見[Dynamic Arrays]（http://en.wikipedia.org/wiki/Dynamic_array）。編輯：對不起，我一開始沒有看到「動態」。當然，你是對的。 – 2013-02-27 20:45:42

@StjepanBakrac這就是爲什麼我編輯它說幾乎立即發佈後的「動態數組」;-) – delnan 2013-02-27 20:46:26

的時間複雜性爲蟒list.append()是O（1）。請參閱Python Wiki上的Time Complexity list。

在內部，蟒列表是指針的載體：

typedef struct { 
    PyObject_VAR_HEAD 
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ 
    PyObject **ob_item; 

    /* ob_item contains space for 'allocated' elements. The number 
    * currently in use is ob_size. 
    * Invariants: 
    *  0 <= ob_size <= allocated 
    *  len(list) == ob_size 
    *  ob_item == NULL implies ob_size == allocated == 0 
    * list.sort() temporarily sets allocated to -1 to detect mutations. 
    * 
    * Items must normally not be NULL, except during construction when 
    * the list is not yet visible outside the function that builds it. 
    */ 
    Py_ssize_t allocated; 
} PyListObject;

根據需要用過度分配，得到攤銷O（1），用於附加成本的ob_item向量調整大小：

/* This over-allocates proportional to the list size, making room 
* for additional growth. The over-allocation is mild, but is 
* enough to give linear-time amortized behavior over a long 
* sequence of appends() in the presence of a poorly-performing 
* system realloc(). 
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... 
*/ 
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

這使得Python列出了dynamic arrays。

來源

2013-02-27 20:39:48

您分享的時間複雜性列表的鏈接非常有幫助。謝謝。 – Sriram 2016-08-18 21:26:15

Python列表是單列還是雙列鏈表？

回答

相關問題