python雙向迴圈連結串列範例詳解

# Functions  函數宣告
class Node():
    """範例化節點類"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存放節點類
    """
    def __init__(self):
        self.head = None

    # 1. 連結串列是否為空
    def is_empty(self):
        return self.head == None

    # 2. 連結串列的長度
    def length(self):
        """
        返回連結串列中所有資料的個數
        範例化遊標，遍歷連結串列，使用計數器自增一
        空連結串列

        """
        # 範例化遊標
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return 0
        else:
            # 不為空
            # 定義計數
            count = 1
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count
            pass

    # 3. 遍歷連結串列
    def travel(self):
        """
        遍歷連結串列
        範例化遊標，遍歷連結串列，每次輸出節點的資料
        空連結串列
        只有頭節點
        """
        # 範例化遊標
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            print(cur.item)
            pass

    # 4. 連結串列頭部新增元素
    def add(self, item):
        """
        頭節點新增
        範例化節點，
        """
        # 範例化節點
        node = Node(item)
        # 範例化遊標
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            node.next = node
            node.prev = node
            self.head = node
        else:
            # 連結串列不為空的情況
            # 只有一個節點的情況
            # node.next = self.head
            node.next = cur
            node.prev = cur
            if cur.next == self.head:
                # print(cur.item)
                cur.prev = node
                cur.next = node
                self.head = node
            elif cur.next != self.head:
                pro = self.head
                while cur.next != self.head:
                    cur = cur.next
                pro.prev = node
                cur.next = node
                self.head = node
                pass

    # 5. 連結串列尾部新增元素
    def append(self, item):
        """
        連結串列尾部新增資料
        範例化節點，範例化遊標，指向尾部節點，修改指向
        連結串列為空
        """
        # 範例化節點
        node = Node(item)
        # 範例化遊標
        cur = self.head
        if self.is_empty():
            self.add(item)
        else:
            # 不為空的情況
            # 指標指向最後一個節點
            self.head.prev = node
            node.next = self.head
            while cur.next != self.head:
                cur = cur.next
            node.prev = cur
            cur.next = node
            pass

    # 6. 連結串列指定位置新增元素
    def insert(self, index, item):
        """
        指定位置新增資料
        範例化節點， 範例化遊標
        移動遊標到索引位置，更改指向
        輸入索引大小判斷
        連結串列是否為空
        """
        # 範例化節點
        node = Node(item)
        # 範例化遊標
        cur = self.head
        if index <= 0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 中間新增資料
            # 宣告計數
            count = 0
            print(index)
            while count < index-1:
                count+=1
                cur = cur.next
            # print(cur.item)
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node
            pass

    # 7. 連結串列刪除節點
    def remove(self, item):
        """
        刪除資料
        範例化遊標，遍歷連結串列，查詢有沒有改資料
        有，對改資料兩側的節點進行指向修改
        """
        # 範例化遊標
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況下
            # 如果刪除的是頭節點
            if cur.item == item:
                # 如果只有一個頭節點
                if cur.next == self.head:
                   self.head = None
                else:
                    # self.head = cur.next
                    pro = cur.next
                    while cur.next != self.head:
                        cur = cur.next
                    cur.next = pro
                    pro.prev = cur
                    self.head = pro
                    pass
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        # print(cur.item)
                        pro = cur.prev
                        nex = cur.next
                        pro.next = cur.next
                        nex.prev = pro
                        return True
                    else:
                        cur = cur.next
                # 如果是最後一個節點
                if cur.item == item:
                    cur.prev.next = self.head
                    self.head.prev = cur.prev

    # 8. 查詢節點是否存在
    def search(self, item):
        """
        查詢指定的資料是否存在
        範例化遊標
        遍歷所有的節點。每個節點中判斷資料是否相等，相等，返回True
        """
        # 範例化遊標
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況
            # 遍歷所有的節點
            while cur.next != self.head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            if cur.item == item:
                return True
            pass

# 程式的入口
if __name__ == "__main__":
    a = Linklist()
    a .add(400)
    a .add(300)
    a .add(200)
    a .add(100)
    a.append(10)
    a.append(11)
    a.add(1)
    a.insert(30, 12) # 1 100 200 300 400 10 11 12
    a.remove(1)    # 100 200 300 400 10 11 12
    a.remove(12)   # 100 200 300 400 10 11
    a.remove(400)  # # 100 200 300  10 11
    a.remove(4000)
    print(a.search(100))  # True
    print(a.search(11))   # True
    print(a.search(111))  # None
    print(a.is_empty())   # False
    a.travel()            # 100 200 300 10 11
    print(a.length())     # 5
    pass