Python資料結構與演算法之列表(連結串列,linked list)簡單實現

NO IMAGE

Python 中的 list 並不是我們傳統(電腦科學)意義上的列表,這也是其 append 操作會比 insert 操作效率高的原因。傳統列表——通常也叫作連結串列(linked list)——通常是由一系列節點(node)來實現的,其每一個節點(尾節點除外)都持有一個指向下一個節點的引用。

其簡單實現:


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

接下來,我們就可使用連結串列的結構來組織所有節點了。


>>> L = None('a', Node('b', Node('c', Node('d'))))
>>> L.next.next.value
'c'

這是所謂的單向連結串列,雙向連結串列的各節點還需要持有一個指向前一節點的引用。

總結