摘要：數(shù)據(jù)結(jié)構(gòu)實現(xiàn)鏈表簡單介紹鏈表是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針。圖解如下查找通過遍歷鏈表，使用標記是否找到了正在尋找的項。一旦為，就是對包含要刪除的項的節(jié)點的引用。

鏈表(Linked list)是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。—— 維基百科

鏈表的基本構(gòu)造塊是節(jié)點(Node)。我們將在文章的第2部分通過Python實現(xiàn)一個簡單的Node類。

一個單向鏈表的構(gòu)造如下圖1所示包含兩個域：

信息域：當前節(jié)點的值(Data or Value)

指針域：指向下一個節(jié)點的指針鏈接(Reference or Link)

注1:必須明確指定鏈表的第一項的位置。一旦我們知道第一項在哪里，第一項目可以告訴我們第二項是什么，依次類推。按照一個方向遍歷，直到最后一項（最后一個節(jié)點），最后一項需要知道沒有下一項。
注2:這些節(jié)點在邏輯上是相連的，但要知道它們在物理內(nèi)存上并不相連。

我們先來實現(xiàn)Node類：

class Node(object):
    def __init__(self, initdata):
        self.data = initdata
        # 引用None代表沒有下一節(jié)點
        self.next = None
    # 獲得數(shù)據(jù)
    def getData(self):
        return self.data
    # 獲得下一個節(jié)點的引用
    def getNext(self):
        return self.next
    # 修改數(shù)據(jù)
    def setData(self, newdata):
        self.data = newdata
    # 修改下一節(jié)點的引用
    def setNext(self, newnext):
        self.next = newnext

創(chuàng)建一個Node對象試試：

>>> tmp = Node(33)
>>> tmp
<__main__.Node object at 0x1022699b0>
>>> tmp.getData()
33

只要知道第一個節(jié)點（包含第一個項），那么之后的每個節(jié)點都可以通過指向下一個節(jié)點的鏈接 依次找到。
考慮到這樣的情況，Unordered List類只要維護對第一個節(jié)點的引用就可以了。Unordered List類本身不包含任何節(jié)點對象，它只包含對鏈表結(jié)構(gòu)中第一個節(jié)點的單個引用！

class unOrderedList():
    def __init__(self):
        # 初始化None表示此時鏈表的頭部不引用任何內(nèi)容
        self.head = None

創(chuàng)建一個空的鏈表試試(如圖2所示)：

>>> myList = unOrderedList()

我們可通過下面的 isEmpty() 方法檢查是否為空鏈表：

# 只有在鏈表中沒有節(jié)點的時候為真
def isEmpty(self):
    return self.head == None

添加元素后的鏈表是這樣的(如圖3所示)，稍后在文章第3部分實現(xiàn)添加方法：

由于是在前端添加，因此最后添加的在最前端。

def add(self, item):
    temp = Node(item) # Step0:創(chuàng)建一個新節(jié)點并將新項作為數(shù)據(jù)
    temp.setNext(self.head) # Step1:更改新節(jié)點的下一個引用以引用舊鏈表的第一個節(jié)點
    self.head = temp # Step2:重新設置鏈表的頭以引用新節(jié)點

添加元素——執(zhí)行mylist.add(26)時候的圖解如下:

>>> mylist.add(31)
>>> mylist.add(77)
>>> mylist.add(17)
>>> mylist.add(93)
>>> mylist.add(26)

def size(self):
    current = self.head
    count = 0
    while current != None:
        count += 1
        current = current.getNext()
    return count

通過current遍歷鏈表并對節(jié)點計數(shù)。
圖解如下:

def search(self, item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

通過current遍歷鏈表，使用found標記是否找到了正在尋找的項。
圖解如下:

def remove(self, item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()
    if previous == None:
    # 當要刪除的項目恰好是鏈表中的第一個項，這時候prev是None，需要修改head以引用current之后的節(jié)點
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

3.4.1 上面的特殊情況，即要刪除的恰好是第一個節(jié)點的圖解如下：

3.4.2 其他情況，即要刪除的是鏈表中的節(jié)點（非第一個）：

我們遍歷鏈表，先搜索，再刪除。
1.搜索：
使用previous與current進行移動，借助found標記是否找到。
一旦found為True，current就是對包含要刪除的項的節(jié)點的引用。
2.刪除（修改引用）：
我們把previous的對下一節(jié)點的引用設為current的下一節(jié)點。

以上兩過程的圖解如下：

參考：
problem-solving-with-algorithms-and-data-structure-using-python
python-wikipedia

如有錯誤，還望指正~
完整實現(xiàn)及測試可在Github找到：Python-DataStructure-Implementation
感謝。