單向鏈表

class Node():
    '''節(jié)點(diǎn)'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''單鏈表'''
    def __init__(self,node=None):
        #內(nèi)部私有函數(shù)，鏈表頭的初始化，可以直接建立空鏈表
        self.__head = node

    def is_empty(self):
        """判斷鏈表是否為空"""
        return self.__head == None

    def length(self):
        """返回鏈表的長(zhǎng)度"""
        #cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
        #count，用來(lái)記錄節(jié)點(diǎn)數(shù)量
        count = 0
        cur = self.__head
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷鏈表"""
        cur = self.__head
        while cur != None:
            print(cur.elem,end=' ')
            cur = cur.next

    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        """尾部添加節(jié)點(diǎn)"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        pre = self.__head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos >= (self.length()-1):
            self.append(item)
        else:
            while count < (pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除一個(gè)節(jié)點(diǎn)"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                #先判斷是否為頭節(jié)點(diǎn)，然后再去處理頭節(jié)點(diǎn)
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next


    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

• 鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷(xiāo)比較大，但對(duì)存儲(chǔ)空間的使用要相對(duì)靈活。
• 注意雖然表面看起來(lái)復(fù)雜度都是 O(n)，但是鏈表和順序表在插入和刪除時(shí)進(jìn)行的是完全不同的操作。鏈表的主要耗時(shí)操作是遍歷查找，刪除和插入操作本身的復(fù)雜度是O(1)。順序表查找很快，主要耗時(shí)的操作是拷貝覆蓋。因?yàn)槌四繕?biāo)元素在尾部的特殊情況，順序表進(jìn)行插入和刪除時(shí)需要對(duì)操作點(diǎn)之后的所有元素進(jìn)行前后移位操作，只能通過(guò)拷貝和覆蓋的方法進(jìn)行。

雙向鏈表

• 我們先看看雙鏈表的構(gòu)造

  是不是和單鏈表如出一轍，無(wú)需更改程序。

• 我們看看雙鏈表的探空功能：

  這樣是不是又和單鏈表一樣了。

• 我們看看求長(zhǎng)度的功能：
  我們只需要計(jì)數(shù)，是不是完全可以把它當(dāng)成單鏈表，只需要一個(gè)游標(biāo)next就可以實(shí)現(xiàn)求長(zhǎng)度啊，遍歷的travel和求長(zhǎng)度一樣都可以看作是單鏈表，簡(jiǎn)單粗暴。

• 我們看看從頭部添加的功能：
  我們是不是要先操作新節(jié)點(diǎn)啊
  這樣就可以實(shí)現(xiàn)。
  但如果用代碼實(shí)現(xiàn)的話(huà)，可以有兩種方式，與指向的前后順序相關(guān)：
  

  1 方法一

 def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node

2 方法二

    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        node = Node(item)
        node.next = self.__head
        self.__head.prev = node
        self.__head = node

• 實(shí)現(xiàn)鏈表尾部添加元素的功能：
  

  尾插法是不是首先要定位啊，定位到最后一個(gè)元素，這個(gè)過(guò)程雙鏈表和單鏈表是沒(méi)有區(qū)別的，定位到最后一個(gè)元素后
  只要實(shí)現(xiàn)這樣的指向就OK了吧，那要怎么實(shí)現(xiàn)呢。

    def append(self, item):
        """尾部添加節(jié)點(diǎn)"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur

考慮一下特殊情況，加入這個(gè)鏈表為空鏈表呢，程序也是沒(méi)問(wèn)題的。

• 實(shí)現(xiàn)insert插入功能：
  

  我們先截個(gè)單鏈表中的insert代碼
  我們看看雙鏈表中需要怎么更改呢？
  這一部分是不需要更改的吧，位置小于等于0我們就調(diào)用頭插法，pos大于等于（length() - 1，我們就調(diào)用尾插法。唯一需要更改的就是，最后的指向問(wèn)題。
  這么一來(lái)是不是就一目了然
• 先操作node節(jié)點(diǎn)，讓node節(jié)點(diǎn)分別指向節(jié)點(diǎn)6和節(jié)點(diǎn)40，node.next = cur，node.prev = cur.prev

• 然后讓節(jié)點(diǎn)40和節(jié)點(diǎn)6分別對(duì)接node節(jié)點(diǎn)，cur.prev.next = node，cur.prev = node

  
  

  這么寫(xiě)也可以。
  那么完整的代碼怎么實(shí)現(xiàn)呢，顯然需要做一些更改，首先pre這個(gè)游標(biāo)就不需要了，我們只需要一個(gè)cur游標(biāo)，且count < pos即可。

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        cur = self.__head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos >= (self.length() - 1):
            self.append(item)
        else:
            while count < pos:
                count += 1
                cur = cur.next
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

測(cè)試結(jié)果沒(méi)問(wèn)題

• 實(shí)現(xiàn)刪除的功能：
  那如果要?jiǎng)h除的是頭節(jié)點(diǎn)要怎么處理呢？
  這樣是不是OK
  那如果原有的鏈表只有一個(gè)節(jié)點(diǎn)要如何處理呢？我們還是直接看代碼吧。

 def remove(self, item):
        """刪除一個(gè)節(jié)點(diǎn)"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                # 先判斷是否為頭節(jié)點(diǎn)，然后再去處理頭節(jié)點(diǎn)
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                       cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

測(cè)試結(jié)果一切正常