from __future__ import print_function

class SingleNode(object):
    '''单节点'''

    def __init__(self, data):
        # 数据域
        self.data = data
        self.next=None

class SingleLinkList(object):
    '''单向链表'''

    def __init__(self, node=None):
        # 头节点
        self.__head=node

    # 是否为空
    def is_empty(self):
        return self.__head is None
    
    # 长度
    def length(self):
        count =0
        current = self.__head
        while current is not None:
            count += 1
            current = current.next
        return count

    # 遍历
    def travel(self):
        current = self.__head
        print('[', end=' ')
        while current is not None:
            print(current.data, end=' ')
            current = current.next
        print(']')

    # 头部添加
    def add(self, item):
        node = SingleNode(item)
        # 新节点的下一节点为旧节点的头
        node.next=self.__head
        # 新链表的头为新节点
        self.__head=node

    # 尾部添加
    def append(self, item):
        node =SingleNode(item)
        # 是否为空
        if self.is_empty():
            self.__head = node
        else:
            # 遍历到最后节点
            current= self.__head
            while current.next is not None:
                current = current.next
            # 最后一个节点添加新节点
            current.next=node
    
    # 指定位置插入
    def insert(self, index, item):
        # 判断插入位置
        if index <= 0:
            self.add(item)
        elif index > self.length()-1:
            self.append(item)
        else:
            node=SingleNode(item)
            count =0
            # 遍历到插入节点的上一个节点
            prev = self.__head
            while count < index-1:
                count +=1
                prev=prev.next
            
            temp = prev.next
            prev.next=node
            node.next=temp
    
    # 删除节点，注意链表没有索引
    def remove(self, item):
        # 前节点指向下一节点
        prev= None
        current= self.__head
        # 搜索节点
        while current is not None:
            if current.data == item:
                if prev is not None:
                    prev.next = current.next
                else:
                    self.__head = current.next
                return
            else:
                prev = current
                current=current.next

    # 搜索节点
    def search(self, item):
        # 遍历搜索
        current = self.__head
        while current.next is not None:
            if current.data == item:
                return True
            else:
                current = current.next
        return False
    
if __name__ == '__main__':
    print('test:')
    single_link_list = SingleLinkList()

    print('--------判断是否为空-------')
    print(single_link_list.is_empty())

    print('-----------长度------------')
    print(single_link_list.length())

    single_link_list.append(2)
    single_link_list.append(3)
    single_link_list.append(5)

    print('-----------遍历------------')
    single_link_list.travel()

    single_link_list.add(1)
    single_link_list.add(0)
    single_link_list.insert(4, 4)
    single_link_list.insert(-1, -1)

    print('-----------遍历------------')
    single_link_list.travel()

    print('-----------查找------------')
    print(single_link_list.search(49))

    print('-----------删除------------')
    single_link_list.remove(-1)

    print('-----------遍历------------')
    single_link_list.travel()

    print('-----------长度------------')
    print(single_link_list.length())