一、链表-实现-判空-长度-遍历-增加结点:

• 链表的实现、判断是否为空、长度、遍历
• 头部增加新结点
• 尾部增加结点
• 指定位置增加结点
• 删除结点
• 查找节点是否存在

# 链表节点实现
class SingleNode(object):
    def __init__(self, item):
        # item：存放元素
        self.item = item
        # next:标识下一个结点
        self.next = None


# 单链表的实现
class SingleLinkList(object):
    def __init__(self, node=None):
        # head：首节点
        self.head = node

    # 判断链表是否为空
    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False

    # 获取链表长度 length()
    def length(self):
        # 游标记录当前所在的位置
        cur = self.head
        # 记录链表的长度
        count = 0

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

    # 遍历链表 travel()
    def travel(self):
        # 游标记录当前所在的位置
        cur = self.head

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

    # 头部增加结点add()
    def add(self, item):
        # 新节点存储新数据
        node = SingleNode(item)
        node.next = self.head
        self.head = node

    # 尾部增加结点append()
    def append(self, item):
        # 新节点存储新数据
        node = SingleNode(item)

        # 判断是否是空链表
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            # 找到尾结点
            while cur.next is not None:
                cur = cur.next

            cur.next = node

    # 指定位置增加结点：insert(pos, item)
    def insert(self, pos, item):

        # 头部增肌新结点
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            # 游标
            cur = self.head
            # 计数
            count = 0
            # 新结点
            node = SingleNode(item)

            # 1、找到插入位置的前一个结点
            while count < pos - 1:
                cur = cur.next
                count += 1

            # 2、完成插入新结点
            node.next = cur.next
            cur.next = node

    # 删除结点 remove(item)
    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
            # 没有找到要删除的元素
            else:
                pre = cur
                cur = cur.next

    # 查找节点是否存在
    def search(self, item):
        # 游标
        cur = self.head

        while cur is not None:
            # 找到了指定结点
            if cur.item == item:
                return True
            cur = cur.next

        return False

if __name__ == '__main__':
    # 节点
    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()
    # 头部增加结点
    print("头部添加结点后")
    link2.add(9)
    link2.travel()
    # 尾部增加结点
    print("尾部添加结点后")
    link2.append(11)
    link2.travel()
    # 指定位置增加结点
    print("指定位置增加结点")
    link2.insert(2, 0)
    link2.travel()
    # 删除结点
    print("删除结点")
    link2.remove(9)
    link2.travel()
    # 查找结点是否存在
    print("查找结点是否存在")
    print(link2.search(11))
    print(link2.search(12))

运行结果：