"""
链表(理解python语言的特殊性)
先定义链表的单个节点
再将节点连成线
"""

class Node(object):
    def __init__(self, elem):
        """
        其中一个节点
        :params elem:数据元素
        """
        self.elem = elem

        # 指向下一节点的连接域
        self.next = None


class SingleLinkList:
    def __init__(self, node=None):
        """
        初始化单向链表
        """
        self._head = node   # 只在这个类内部使用, 在外部不进行获取


    def add(self, item):
        """
        在单向链表头部添加元素
        可以不用讨论空链表的情况
        """
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            self._head, node.next = node, self._head
    def append(self, item):
        """
        在尾部追加元素
        :params item: 元素
        """
        node = Node(item)
        # cur = self._head 易错
        # while cur!=None:
        #     cur = cur.next
        # cur = node
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node
        
    def insert(self, pos, item):
        """
        在指定位置添加元素
        :params pos: 指定位置(从0开始索引)
        :params item: 添加的元素
        """
        if pos<=0:
            self.add(item)
        elif pos>self.length()-1:
            self.append(item)
        else:
            count = 0
            pre = self._head
            while count<(pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node
        
    def remove(self, item):
        """
        删除节点
        """
        # 删除头节点
        pre = self._head
        this = pre.next
        if self._head.elem == item:
            self._head = self._head.next
        else:
            while this.elem!=item:
                pre = pre.next
                this = this.next
            pre.next = this.next

    def search(self, item):
        """
        查找节点是否存在
        """
        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            cur = cur.next
        return False

    def is_empty(self):
        """
        判断链表是否为空
        头部是空的话链表就是空的
        """
        return self._head==None

    def length(self):
        """
        链表长度
        从头到尾的遍历过程
        定义 cur 用来指向节点的
        最后一个节点一定是None
        """
        cur = self._head
        count = 0
        while cur!=None:
            count+=1
            cur=cur.next
        return count

    def travel(self):
        """
        遍历节点
        """
        cur = self._head
        while cur!=None:
            print(cur.elem)
            cur = cur.next

if __name__ == '__main__':
    # 初始化元素值为20的单向链表
    # s = SingleLinkList()
    # s.append(100)
    # s.append(15)
    # s.add(20)
    # s.insert(1, 2)
    # s.remove(15)
    # s.travel()
    # print(s.search(100))
    def insertNodeAtTail(head, data):
        cur = head
        if head==None:
            return Node(data)
        while cur.next:
            cur = cur.next
        cur.next = Node(data)
        return head
    head = Node(5)
    print(insertNodeAtTail(head, 2))