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

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

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

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

信息域：當(dāng)前節(jié)點(diǎn)的值(Data or Value)

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

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

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

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

創(chuàng)建一個(gè)Node對(duì)象試試：

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

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

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

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

>>> myList = unOrderedList()

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

# 只有在鏈表中沒有節(jié)點(diǎn)的時(shí)候?yàn)檎?def isEmpty(self):
    return self.head == None

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

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

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

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

>>> 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遍歷鏈表并對(duì)節(jié)點(diǎn)計(jì)數(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標(biāo)記是否找到了正在尋找的項(xiàng)。
圖解如下:

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:
    # 當(dāng)要?jiǎng)h除的項(xiàng)目恰好是鏈表中的第一個(gè)項(xiàng)，這時(shí)候prev是None，需要修改head以引用current之后的節(jié)點(diǎn)
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

3.4.1 上面的特殊情況，即要?jiǎng)h除的恰好是第一個(gè)節(jié)點(diǎn)的圖解如下：

3.4.2 其他情況，即要?jiǎng)h除的是鏈表中的節(jié)點(diǎn)（非第一個(gè)）：

我們遍歷鏈表，先搜索，再刪除。
1.搜索：
使用previous與current進(jìn)行移動(dòng)，借助found標(biāo)記是否找到。
一旦found為True，current就是對(duì)包含要?jiǎng)h除的項(xiàng)的節(jié)點(diǎn)的引用。
2.刪除（修改引用）：
我們把previous的對(duì)下一節(jié)點(diǎn)的引用設(shè)為current的下一節(jié)點(diǎn)。

以上兩過程的圖解如下：

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

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