一、鏈表-實(shí)現(xiàn)-判空-長度-遍歷-增加結(jié)點(diǎn):

• 鏈表的實(shí)現(xiàn)、判斷是否為空、長度、遍歷
• 頭部增加新結(jié)點(diǎn)
• 尾部增加結(jié)點(diǎn)
• 指定位置增加結(jié)點(diǎn)
• 刪除結(jié)點(diǎn)
• 查找節(jié)點(diǎn)是否存在

# 鏈表節(jié)點(diǎn)實(shí)現(xiàn)
class SingleNode(object):
    def __init__(self, item):
        # item：存放元素
        self.item = item
        # next:標(biāo)識下一個結(jié)點(diǎn)
        self.next = None


# 單鏈表的實(shí)現(xiàn)
class SingleLinkList(object):
    def __init__(self, node=None):
        # head：首節(jié)點(diǎn)
        self.head = node

    # 判斷鏈表是否為空
    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False

    # 獲取鏈表長度 length()
    def length(self):
        # 游標(biāo)記錄當(dāng)前所在的位置
        cur = self.head
        # 記錄鏈表的長度
        count = 0

        while cur is not None:
            cur = cur.next
            count += 1
        return count

    # 遍歷鏈表 travel()
    def travel(self):
        # 游標(biāo)記錄當(dāng)前所在的位置
        cur = self.head

        while cur is not None:
            print(cur.item)
            cur = cur.next

    # 頭部增加結(jié)點(diǎn)add()
    def add(self, item):
        # 新節(jié)點(diǎn)存儲新數(shù)據(jù)
        node = SingleNode(item)
        node.next = self.head
        self.head = node

    # 尾部增加結(jié)點(diǎn)append()
    def append(self, item):
        # 新節(jié)點(diǎn)存儲新數(shù)據(jù)
        node = SingleNode(item)

        # 判斷是否是空鏈表
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            # 找到尾結(jié)點(diǎn)
            while cur.next is not None:
                cur = cur.next

            cur.next = node

    # 指定位置增加結(jié)點(diǎn)：insert(pos, item)
    def insert(self, pos, item):

        # 頭部增肌新結(jié)點(diǎn)
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            # 游標(biāo)
            cur = self.head
            # 計(jì)數(shù)
            count = 0
            # 新結(jié)點(diǎn)
            node = SingleNode(item)

            # 1、找到插入位置的前一個結(jié)點(diǎn)
            while count < pos - 1:
                cur = cur.next
                count += 1

            # 2、完成插入新結(jié)點(diǎn)
            node.next = cur.next
            cur.next = node

    # 刪除結(jié)點(diǎn) remove(item)
    def remove(self, item):
        # 游標(biāo)
        cur = self.head
        # 輔助游標(biāo)
        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
            # 沒有找到要刪除的元素
            else:
                pre = cur
                cur = cur.next

    # 查找節(jié)點(diǎn)是否存在
    def search(self, item):
        # 游標(biāo)
        cur = self.head

        while cur is not None:
            # 找到了指定結(jié)點(diǎn)
            if cur.item == item:
                return True
            cur = cur.next

        return False

if __name__ == '__main__':
    # 節(jié)點(diǎn)
    node1 = SingleNode(10)
    print(node1.item)
    print(node1.next)
    # 鏈表
    link1 = SingleLinkList()
    print(link1.head)
    link2 = SingleLinkList(node1)
    print(link2.head.item)
    # 判空
    print(link1.is_empty())
    print(link2.is_empty())
    # 長度
    print(link1.length())
    print(link2.length())
    # 遍歷
    link2.travel()
    # 頭部增加結(jié)點(diǎn)
    print("頭部添加結(jié)點(diǎn)后")
    link2.add(9)
    link2.travel()
    # 尾部增加結(jié)點(diǎn)
    print("尾部添加結(jié)點(diǎn)后")
    link2.append(11)
    link2.travel()
    # 指定位置增加結(jié)點(diǎn)
    print("指定位置增加結(jié)點(diǎn)")
    link2.insert(2, 0)
    link2.travel()
    # 刪除結(jié)點(diǎn)
    print("刪除結(jié)點(diǎn)")
    link2.remove(9)
    link2.travel()
    # 查找結(jié)點(diǎn)是否存在
    print("查找結(jié)點(diǎn)是否存在")
    print(link2.search(11))
    print(link2.search(12))

運(yùn)行結(jié)果：

運(yùn)行結(jié)果.png