单链表由线性的节点组成，每个节点储存一个数据和一个指向下一个数据的指针

# 节点类
class Node:
    def __init__(self, elem):
        self.elem = elem
        self.next = None


# 单链表类
class Single_linked_list:
    def __init__(self):
        self.__head = None

    def is_empty(self):
        '''
        :return: bool
        '''
        return self.__head is None

    def length(self):
        cur = self.__head
        count = 0
        while cur:
            count += 1
            if not cur.next:
                break
            cur = cur.next

        return count

    def travel(self):
        '''
        :return: 打印所有元素
        '''
        cur = self.__head
        while cur:
            print(cur.elem, end=' ')
            cur = cur.next

    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''
        :param item: 添加元素
        :return: None
        '''
        node = Node(item)
        cur = self.__head
        if not cur:
            self.__head = node
        else:
            while cur:
                if not cur.next:
                    cur.next = node
                    break
                cur = cur.next

    def insert(self, index, item):
        '''
        :param index: 插入的索引位置
        :param item: 要插入的数据元素
        :return: None
        '''
        node = Node(item)
        if index <= 0:
            self.add(item)
        elif index >= self.length():
            self.append(item)
        else:
            cur = self.__head
            pre = None
            cur_count = 0
            while cur:
                if cur_count == index:
                    node.next = cur
                    pre.next = node
                pre = cur
                cur = cur.next
                cur_count += 1

    def remove(self, item):
        cur = self.__head
        pre = None
        cur_count = 0
        while cur:
            if cur.elem == item:
                if cur_count == 0:
                    self.__head = cur.next
                    break
                pre.next = cur.next
            pre = cur
            cur = cur.next
            cur_count += 1

    def search(self, item):
        '''
        :param item: 查找元素
        :return: bool
        '''
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    single = Single_linked_list()
    print(single.is_empty())
    single.append(10)
    single.append(20)
    single.append(300)
    single.add(1)
    single.insert(2, 100)
    single.remove(100)
    single.travel()
    print(single.length())
    print(single.search(100))