python單向鏈表怎么實現

這篇文章主要介紹“python單向鏈表怎么實現”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“python單向鏈表怎么實現”文章能幫助大家解決問題。

單向鏈表：是將所有的數據作為一個個節點，將所有的節點鏈接在一起。每一個節點中又分為： 存儲數據區，鏈接區

存儲數據區： 存儲具體的數據

鏈接區： 指向下一個節點

分析實現：

1、 分析：根據鏈表的特性，首先要存放有數據的容器，還要有存放節點的容器
2、 節點類中：要有數據區和next區
3、 鏈表類中：存放所有節點

單鏈表操作

1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節點
8、查找節點是否存在

代碼實現

# Functions  函數聲明
class Node():
    """
    存放節點類
    每次調用該類，實例化一個節點
    默認每個節點中有數據區，next區。
    數據區為該數據，next區為空
    """
    def __init__(self, item,next=None):
        self.item = item
        self.next = next
        pass

class Linklist():
    """
    存放數據類
    將所有的節點存放起來的容器
    首先，默認鏈表為空，在這里需要有一個頭節點，默認頭節點為空

    """
    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        return self.head == None

    def append(self, item):
        """
        往鏈表尾部添加數據
        1、實例化游標：使用游標指向每一個數據，檢索數據和判斷數據next是否為空
        2、移動游標，從頭節點開始，每次使用self.next移動，以為next指向的就是下一個數據
        3、添加數據，首先判斷鏈表是否為空，為空的情況下，直接將頭節點等于node數據
        4、如果不為空，需要從頭節點開始，移動游標，判斷游標指向的next是否為空
        5、使用循環不停的移動節點，當遇到節點中的next為空的情況下停止移動
        6、循環條件： 當 條件 != None, 進入循環獲取，當cur為空時就不會進入循環，所以在這里要使用 cur != None
        """
        # 首先要實例化一個節點
        node = Node(item)
        # 如果鏈表為空
        if self.is_empty():
            # 直接將頭節點的next添加node
            self.head = node
        else:
            # 實例化一個游標
            cur = self.head
            while cur.next != None:
                # 移動游標，得到最后一個游標的數據
                cur = cur.next
            # 將移動后的數據的下一個next添加上 node
            cur.next=node
            pass

    def travel(self):
        """遍歷數據"""
        # 實例化一個游標
        cur = self.head
        # 數據鏈為空的情況
        if self.is_empty():
            print('')
        else:
            # 獲取每個數據區中的數據
            # 移動游標，每移動一次，輸出一次數據區內的數據
            while cur != None:
                print(cur.item, end=' ')
                cur = cur.next
            print()

    def length(self):
        """返回鏈表的長度"""
        # 實例化游標
        cur = self.head
        # 計數，這里對空鏈表進行判斷，如果是鏈表，則不會進入循環，直接輸出 0
        count = 0
        # 移動游標，獲取下一個數據，然后讓count +=1
        while cur != None:
            # 計數
            count+=1
            # 移動游標
            cur = cur.next
        return count

    def add(self, item):
        """
        頭部添加數據
        分析： 將數據添加到第一個節點當中
        1、 需要先將node的next指向 原第一個節點，這原第一個節點就是self.head
        2、 再講self.head指向node進行連接
        """
        # 先實例化節點
        node = Node(item)
        # 將數據添加到頭部當中
        node.next=self.head
        self.head=node

    def insert(self, index, item):
        """
        指定位置添加數據
        分析：
        1、首先要找到，該位置的數據
        2、將要添加的數據next等于 原位置的next數據
        3、原數據的 next等于node新數據
        """
        if index<=0:
            # 如果輸入的索引小于或者等于O，默認使用頭插發
            self.add(item)
        elif index>self.length():
            # 如果輸入的索引大于鏈表的長度,使用尾插法
            self.append(item)
        else:
            # 實例化數據節點
            node = Node(item)
            # 找到該數據的位置
            # 實例化一個游標
            cur = self.head
            # 計數
            conent = 0
            while conent<(index-1):
                conent+=1
                cur = cur.next

            node.next=cur.next
            cur.next=node

    def search(self, item):
        """
        查詢指定的數據是否存在
        分析： 查詢指定的數據，需要對整個鏈表掃描，判斷這個數據是否等的該節點中的數據
        """
        # 實例化一個游標
        cur = self.head
        # 進行判斷是否相等
        while cur != None:
            # 判斷
            if cur.item == item:
                return True
            else:
                cur = cur.next
            pass
        # 否則返回False
        return False

    def remove(self, item):
        """
        移除指定的數據
        分析：
        1、刪除數據，需要首先判斷數據是否存在
        2、找到該數據所在的位置，將該數據的上一個數據的next指向自己的next
        3、如何獲取該數據的指向，和上一個數據的指向
        4、需要定義兩個指針
        5、先將兩個指針相等，再講一個指針先移動一次，再同時移動

        """
        # 先找到該數據
        cur = self.head
        por = None

        while cur != None:
            if cur.item==item:
                # 要判斷是否為第一個節點
                if cur == self.head:
                    self.head = cur.next
                else:
                    por.next = cur.next
                break
            else:
                # 如果在當前節點中沒有相等的，將節點進行移動
                # 移動要注意，現將兩個游標相等，再講另一個游標移動一次
                por = cur
                cur = cur.next

測試運行

# 程序的入口
if __name__ == "__main__":
    s = Linklist()
    s.append(100)
    s.append(200)
    s.append(300)
    s.add(1)
    s.add(12)
    s.insert(-1,6)
    
    s.travel()       #  6 12 1 100 200 300 
    print(s.length())  # 6
    print(s.search(11)) # False
    s.remove(12)
    s.travel()       # 6 1 100 200 300 
    print(s.length())  # 5
    print(s.search(11)) # False
    pass

關于“python單向鏈表怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。