Python程式碼實現雙連結串列

class Node(object):
    def __init__(self, item=None):
        #放資料
        self.item= item
        #指向後一個節點
        self.next = None
        #指向前一個節點
        self.prior =None

#雙向連結串列  從左往右讀
class Node(object):
        """雙向連結串列節點"""
        def __init__(self,item):
                #放資料的節點
                self.elem = item
                #指向後一個節點
                self.next = None
                #指向前一個節點
                self.prev = None
#雙向連結串列
class LinkList(object):
        def __init__(self,node=None):
                #代表頭節點
                self.__head = node

        #判斷連結串列是否為空
        def is_empty(self):
                return self.__head == None

        def length(self):
                """返回連結串列的長度"""
                #cur遊標移動，從而實現遍歷元素的功能
                cur = self.__head
                #count用來計數
                count = 0
                while cur != None:
                        count += 1
                        #讓cur遊標可以向下移動
                        cur = cur.next
                return count

        #遍歷整個連結串列
        def travel(self):
                if self.is_empty():
                        return
                #建立遊標等於起始節點
                else:
                        cur = self.__head
                        while cur != None:
                                print(cur.elem,end=" ")
                                cur = cur.next
                        print("")

        #頭插法
        def add(self,item):
                #新節點
                node = Node(item)
                if self.is_empty():
                        #頭節點指向了新的節點
                        self.__head = node
                else:
                        #新節點指向原第一個節點
                        node.next = self.__head
                        self.__head = node
                        node.next.prev = node

        def append(self,item):
                """連結串列尾部新增元素"""
                node = Node(item)  #定義新節點
                #連結串列是否為空連結串列
                if self.is_empty():
                        #如果為空，新的節點加了進去
                        self.__head = node
                else:
                        #頭節點 建立遊標
                        cur = self.__head   #設定指向頭結點的遊標  此時的當前連結串列第一個節點，就是頭節點指向的節點
                        #cur到最後一個節點停下
                        while cur.next != None:
                                cur = cur.next
                        #新增節點到尾部 cur道了最後一個結點  cur.next指向了新的節點node  從左往右讀  
                        cur.next = node
                        #當前的節點指向它前一個
                        node.prev = cur

        #插入法  #pos從零開始
        def insert(self,pos,item):
                """在指定位置新增元素"""
                #指向不是頭部元素，self.__head的地址
                # 為下一個元素，所以pre為下一個元素
                if pos <= 0:
                        #認為是頭插法
                        self.add(item)
                #假如長度是3 pos大於2要特殊處理  
                elif pos > (self.length()-1):
                        #尾插法
                        self.append(item)
                else:
                        #建立節點 新節點
                        node = Node(item)
                        cur = self.__head
                        count = 0
                        #動起來
                        while count < pos:
                                count+=1
                                cur = cur.next
                       
                        #把節點連結到中間任意位置 插入前一個節點   此時，cur停在後一個節點
                        node.next = cur
                        node.prev = cur.prev
                        cur.prev.next = node
                        cur.prev = node

        def remove(self,item):
                """刪除元素"""
                if self.is_empty():
                    return
                cur = self.__head
                #查詢所有的位置有沒有要刪除的，若有則刪除
                while cur != None:
                        #判斷cur指向的資料,是否為要刪除的資料   item要刪除的元素
                        if cur.elem == item:
                                #判斷此節點是否為頭節點
                                #考慮特殊情況,恰好要刪除是第一個元素    當前的元素就是我要刪除的元素 
                                if cur == self.__head:
                                        #如果刪除中間,  頭節點指向後一個節點 
                                        self.__head = cur.next
                                        #考慮連結串列只有一個節點  直接指向None
                                        if cur.next != None:
                                                #是否只有一個節點
                                                cur.next.prev = None
                                else:
                                        #中間節點
                                        cur.prev.next = cur.next
                                        if cur.next != None:
                                                cur.next.prev = cur.prev
                                break
                        else:
                                #沒有找到,cur遊標向繼續往下移動
                                cur = cur.next

        def search(self,item):
                """查詢結點是否存在"""
                #如果是一個空連結串列
                if self.is_empty():
                        return False
                cur = self.__head
                while cur.next != self.__head:
                        #cur資料是否為查詢的資料 item是要查的資料 
                        if cur.elem == item:
                                return True
                        else:
                                cur = cur.next
                #遍歷完成 cur指向None
                return False

if __name__ == '__main__':
        ll = LinkList()
        #第一次的
        print(ll.is_empty())
        print(ll.length())

        ll.append(1)
        print(ll.is_empty())
        print(ll.length())

        ll.append(2)

        ll.append(3)
        ll.append(4)
        ll.append(5)
        ll.travel()
        ll.insert(-1,50)
        ll.travel()
        ll.insert(2,60)
        ll.travel()
        ll.insert(10,300)
        ll.travel()
        ll.remove(50)
        ll.travel()
        ll.remove(300)
        ll.travel()