資料結構 單連結清單 python實作

連結清單

連結清單屬于線性表

可以充分利用計算機記憶體空間，實作靈活的記憶體動态管理

連結清單的定義

連結清單（Linked list）是一種常見的基礎資料結構，是一種線性表，但是不像順序表一樣連續存儲資料，而是在每一個幾點（資料存儲單元）裡存放下一個節點的位置資訊（即位址）。
           

單向連結清單

單向連結清單也叫單連結清單，是連結清單中最簡單的一種形式，它的每個節點包含兩個域，一個資訊域（元素域），和一個連結域。這個連結指向連結清單中的下一個節點，而最後一個節點的連結域則指向一個空值。
           

• 表元素域elem⽤來存放具體的資料。
• 連結域next⽤來存放下⼀個節點的位置（python中的辨別）
• 變量p指向連結清單的頭節點（⾸節點）的位置，從p出發能找到表中的任意節點。

頭結點，首結點 -> 前驅節點->後繼節點-> 尾節點

節點實作

單向清單的定義

class Node(object):
    """結點類"""
    def __init__(self, item):
        # item存放資料元素
        self.item = item
        # next是下一個節點的辨別
        self.next = None
           

單連結清單的實作

#!/usr/bin/python3
class Node:
    """單連結清單的節點"""
    def __init__(self, item):
        # item存放資料元素
        self.item = item
        # next是下一個節點的辨別
        self.next = None


class SingleLinkList:
    """單連結清單"""
    def __init__(self, node=None):
        # 頭節點指向第一個節點
        self.__head = node

    def __str__(self):
        """周遊清單"""
        sll = "["
        cur = self.__head
        while cur is not None:
            sll += str(cur.item)
            sll += ", "
            cur = cur.next
        sll += "]"
        return sll

    def is_empty(self):
        """判斷連結清單是否為空"""
        return self.__head is None

    def length(self):
        """連結清單長度"""
        # cur初始時指向頭節點
        cur = self.__head
        count = 0
        # 尾節點指向None，當未達到尾部時
        while cur is not None:
            count += 1
            # 将cur後移一個節點
            cur = cur.next
        return count

    def add(self, item):
        """
        連結清單頭部添加元素
        :param item: 要儲存的資料
        """
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        """清單尾部添加元素"""
        node = Node(item)
        if self.is_empty():
            # 如果連結清單為空的話，則直接把新節點放在頭部
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            # 退出循環的時候，cur指向尾節點
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素"""
        # 在頭部添加元素
        if pos <= 0:
            self.add(item)
        # 若指定位置超過連結清單尾部，則執行尾部插入
        elif pos >= self.length():
            self.append(item)
        # 找到指定位置
        else:
            cur = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                # 退出循環時，cur指向pos的前一個位置
                cur = cur.next
            node = Node(item)
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """删除節點"""
        cur = self.__head
        pre = None
        while cur is not None:
            # 找到了要删除的元素
            if cur.item == item:
                # 在頭部找到了元素
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                return
            # 沒找到元素 移動遊标
            pre = cur
            cur = cur.next

    def search(self, item):
        """查找節點是否存在"""
        cur = self.__head
        while cur is not None:
            if cur.item == item:
                return True
        return False


if __name__ == '__main__':
    # 生成連結清單對象
    sll = SingleLinkList()

    # 列印連結清單的長度
    print("連結清單的長度", end=" ")
    print(sll.length())

    # 列印連結清單
    print(sll)

    # 向連結清單追加節點
    sll.append(1)

    # 向連結清單添加節點
    sll.add(2)

    # 向連結清單插入節點
    sll.insert(0, 3)

    # 列印連結清單
    print(sll)

    # 判斷連結清單是否為空
    print("連結清單是否為空", end=" ")
    print(sll.is_empty())

    # 判斷節點是否存在
    print("判斷節點3是否存在", end=" ")
    print(sll.search(3))

    # 删除節點
    sll.remove(3)

    # 列印連結清單
    print(sll)


           

exit(?)