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
        # 技術器
        # 如果連結串列為空，不會進入迴圈，直接輸出 0
        count = 0
        # 遍歷所有的資料
        while cur != None:
            count +=1
            cur = cur.next
        return count

    # 3. 遍歷連結串列
    def treval(self):
        """
        遍歷連結串列，獲取所有的資料
        使用遊標，遍歷整個連結串列，每次輸出cur.item 的值
        注意連結串列為空的情況，
        """
        # 範例化一個遊標
        cur = self.head
        # 遍歷連結串列
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
    # 4. 連結串列頭部新增元素
    def add(self, item):
        """
        頭部新增資料
        分析：
        1、頭部新增資料，連結串列為空時： self.head 指向node
        2、連結串列不為空時： 先將node.next = self.head.next, 再講 self.head = node
        """
        # 範例化節點
        node = Node(item)
        # 新增資料
        # 判斷連結串列是否為空
        if self.is_empty():
            # 為空，直接將self.head 指向node
            self.head=node
        else:
            # 不為空，先將noede
            node.next = self.head
            self.head.prev=node
            self.head=node

    # 5. 連結串列尾部新增元素
    def append(self,item):
        """
        尾部新增資料
        分析：
        要先將指標指向尾部的節點
        最後的節點的 cur.next = node, node.prev = cur
        """
        # 範例化節點
        node = Node(item)
        # 範例化遊標
        cur = self.head
        # 移動遊標到最後一個節點
        # 如果連結串列為空
        # 直接使用頭插法
        if self.is_empty():
            self.add(item)
        else:
            while cur.next != None:
                # cur.next 不為空，則進入迴圈， 上次迴圈，是進入上上個節點，但 將cur  = cur.next，就指向了最後一個節點
                cur = cur.next
            node.prev = cur
            cur.next = node

    # 6. 連結串列指定位置新增元素
    def insert(self, index, item):
        """
        指定位置新增資料
        分析
        單連結串列中需要範例化兩個有遊標
        雙向連結串列，直接向指標指向索引的位置
        將這個位置節點的 cur.
        """
        # 範例化節點
        node = Node(item)
        # 範例化遊標
        cur = self.head
        # 起始位置
        count = 0
        if index<=0:
            # 使用頭插法
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 移動遊標
            while count < index:
                # 增加一
                count += 1
                # 移動遊標到索引位置
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node


    # 7. 連結串列刪除節點
    def remove(self,item):
        """
        刪除指定的節點
        首先範例化節點，遍歷連結串列，找到該節點，刪除該節點
        """
        # 範例化遊標
        cur = self.head
        # 遍歷連結串列，找到該節點
        while cur != None:
            if cur.item == item:
                if self.head == cur:
                    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
                    pass
                break
            else:
                cur = cur.next

    # # 8. 查詢節點是否存在
    def search(self, item):
        """
        檢視節點是否存在
        分析
        遍歷連結串列，檢視每一個節點的資料區
        空連結串列
        只有頭節點
        只有尾節點
        """
        # 範例化一個遊標
        cur = self.head

        # 遍歷連結串列
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

# 程式的入口
if __name__ == "__main__":
    s = Linklist()
    print(s.is_empty())  #  True
    s.append(100) 
    s.append(200)
    s.append(300)
    s.add(6)
    s.insert(1, 10)
    s.search(6)
    s.treval()   # 6 10 100 200 300 
    s.remove(100)
    s.treval()   # 6 10 200 300 
    pass