1. Linked List

鏈表是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，與之對應(yīng)的另外一個選擇是數(shù)組。在查詢方面，數(shù)組有優(yōu)勢，復(fù)雜度是O(1)，但是在插入刪除等操作上不如鏈表，復(fù)雜度是O(n)；鏈表在插入刪除等操作上有優(yōu)勢，復(fù)雜度是O(1)，而查詢上不如數(shù)組，必須按照順序檢索，復(fù)雜度是O(n)。
以上特征的原因來自于二者不同的儲存方式，數(shù)組是在內(nèi)存空間中選取連續(xù)單元，所以查詢速度極快，但是如果插入元素超過了附近可用的內(nèi)存空間，則要整體復(fù)制遷移，重新分配內(nèi)存空間。相比之下，鏈表的存儲不是連續(xù)的內(nèi)存空間，每一個位置上記錄與之相鄰的元素，如果是單鏈表，只記錄下一個元素的內(nèi)存位置，雙鏈表的話還會記錄上一個元素位置。

1.1 Linked List基本構(gòu)成

一般要有兩個class，一個定義單個Node的構(gòu)成（value和element address），另一個定義整體的list（head起始位置）

class Node:
    def __init__(self, value):
        self.value = value
        self.next_node = None
#單鏈表的Node有兩個部分構(gòu)成，一個是當(dāng)前element的value，另一個是下一個element的address

class LinkedList:
    def __init__(self):
        self.head = None
#Linked list的必須元素只有head

1.2 Linked List的生成和顯示

Linked List一般需要根據(jù)Class Node生成一個連續(xù)的鏈表，并且可以根據(jù)需要顯示鏈表的元素。

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

class LinkedList:
    def __init__(self, L = None):
        if not L:
        #課上的代碼比較冗余，這里做了update，原代碼是"if L is None or len(L) == 0"，兩個判斷可以合并，因?yàn)镹one和[]的boolean判斷都是False
            self.head = None
        self.head = Node(L[0])
        current_node = self.head
        #將head賦給L中的第一個element，當(dāng)下的node也是第一個element
        for e in L[1: ]:
            current_node.next_node = Node(e)
            current_node = current_node.next_node

    def print_list(self, sep = ', '):
        values = []
        node = self.head
        #從head開始，只要node有值，全都變成str加入values中，方便格式化輸出
        while node:
            values.append(str(node.value))
            node = node.next_node
        print(sep.join(values))

1.3 Linked List插入元素

常見的插入操作是在兩端加入，所以定義兩個function實(shí)現(xiàn)頭尾兩端插入元素的功能。

#Node和LinkedList上文定義過的屬性功能不再重復(fù)，這里只附兩個函數(shù)的代碼
class LinkedList:
    def append(self, value):
    #在最后插入新的node
        new_node = Node(value) 
        if not self.head:
            self.head = new_node
        #如果當(dāng)前Linked List中沒有node，則讓head指向這個新的Node
        else:
            current_node = self.head
            while current_node.next_node:
                current_node = current_node.next_node
            current_node.next_node = new_node
        #如果當(dāng)下有node，則遍歷所有node，直到找到最后一個node，由于while的body將當(dāng)前node指向了下一個，所以終止條件是判斷下一個node是否為真

    def prepend(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            #新的node指向head，這里的head是一個linked list
            self.head = new_node
            #head指向new node，這里的head是上文提到過的LinkedList class中的一個屬性

1.4 Linked List刪除元素

同樣，常見的刪除位置是在首尾兩端，和插入的方法類似，只是刪除時的條件判斷更加復(fù)雜。

class LinkedList:
    def delete_first_element(self):
        if not self.head:
            return 
        if not self.head.next_node:
        #之所以要比insert多加一個判斷，是因?yàn)槿绻挥幸粋€元素，head要指向None，如果多于一個元素，head指向剩下緊鄰的元素
            self.head = None
        else:
            self.head = self.head.next_node
        #鏈表中刪除元素，其實(shí)不用真的將值改變，或者移動后續(xù)元素，只需要在鏈表的關(guān)聯(lián)中刪除該元素的地址，任何元素都將無法找到這個元素，也就被刪除了。

    def delete_last_element(self):
        if not self.head:
            return 
        if not self.head.next_node:
        #之所以要比insert多加一個判斷，是因?yàn)槿绻挥幸粋€元素，head要指向None，如果多于一個元素，head指向剩下緊鄰的元素
            self.head = None
        else:
            current_node = self.head
            while current_node.next_node.next_node:
                current_node = current_node.next_node
            current_node.next_node = None
            #和在最后插入位置類似，循環(huán)判斷條件需要注意，因?yàn)橐獎h除最后一個元素，我們要讓當(dāng)前位置停留在倒數(shù)第二個元素，而while的body內(nèi)會更改當(dāng)前元素到下一個，所以判別結(jié)束條件應(yīng)該是當(dāng)下元素后面的第三個元素為空。

1.4 Linked List排序判斷

Linked List的數(shù)據(jù)結(jié)構(gòu)最擅長排序，所以自然要在class的定義中判斷排序狀態(tài)。

class LinkedList:
    def __init__(self, L = None, comparison_key = lambda x: x):
        if L is None or not len(L):
            self.head = None
        else:
            self.head = Node(L[0])
            current_last_node = self.head
            for e in L[1: ]:
                current_last_node.next_node = Node(e)
                current_last_node = current_last_node.next_node
        self.comparison_key = comparison_key

    def is_sorted(self):
        if not self.head or not self.head.next_node:
            return True
        #如果鏈表為空，或者只有一個元素，都認(rèn)為是有序的
        node = self.head
        while node.next_node:
            if self.comparison_key(node.value) > self.comparison_key(node.next_node.value):
                return False
            node = node.next_node
        return True

1.5 Linked List逆序

和上文同樣的原因，逆序也是常用功能。

class LinkedList:
    def reverse(self):
        if not self.head or not self.head.next_node:
            return True
        tail = self.head
        #最后的位置是現(xiàn)在的head處
        current_node = self.head.next_node
        #要處理的元素是head后面一個
        tail.next_code = None
        #切斷tail和其他元素的聯(lián)系
        while current_node:
            next_node = current_node.next_node
            #找到下一個要逆序的元素
            current_node.next_node = tail
            #建立當(dāng)下處理元素的逆序關(guān)系
            tail = current_node
            #標(biāo)記當(dāng)前逆序list中最后一個元素
            current_node = next_node
            #處理好當(dāng)前的元素后，準(zhǔn)備再次循環(huán)處理下面的元素
        self.head = tail
        #全部逆序后，head應(yīng)該指向tail的標(biāo)記處      

2. Deque實(shí)現(xiàn)

Deque的數(shù)據(jù)結(jié)構(gòu)也是Linked List，可以方便的插入、刪除數(shù)據(jù)，一般都是在頭尾操作元素。