class Node:
    def __init__(self, data = None):
        self.__data = data
        self.__next = None
    
    ## __del__은 소멸자라고 하고 객체가 메모리에서 사라질때 반드시 한번 호출하는 것
    def __del__(self):
        print("data of {} is deleted".format(self.__data))

    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self.__data = data

    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, next):
        self.__next = next

class SingleLinkedList:
    def __init__(self):
        self.head = None 
        ## 헤드는 저장되어 있는 리스트중에 첫번째를 가리키는 것이다.
        ## 헤드는 싱글링크드리스트의 자료의 존재를 위해서도 필요하다. head가 없다면 예를들어 맨앞에 데이터의 reference count가 0이 되면서
        ## 연쇄적으로 데이터가 가비지 컬렉션될 것이고 자료 전체가 유지되지 않을것이다.
        self.d_size = 0 ## d_size는 이 싱글연결리스트가 갖고 있는 데이터 개수를 말한다.


    ## 아래 empty와 size 함수는 사용자가 이 싱글연결리스트에 데이터가 비어있는지 몇개 있는지 확인할때 쓴다.

    def empty(self): ## single 링크드 리스트가 비어있을때는 트루, 아니면 false
        if self.d_size == 0:
            return True
        else:
            return False

    def size(self): ## integer를 반환하는데 데이터의 개수를 반환한다.
        return self.d_size


    ## 아래 add, search, delete 함수는 ADT 삽입, 탐색, 삭제 구현
    
    def add(self, data):
        new_node = Node(data)
        new_node.next = self.head ## 새로운 노드 next를 기존에 있던 헤드를 가리키게 한다.
        self.head = new_node ## 헤드를 새로운 노드로 바꿔준다.
        self.d_size += 1

    def search(self, target): ## cur가 처음부터 하나씩 비교를해서 찾는다.
        cur = self.head ## cur를 헤드를 가리키도록 한다.
        while cur: ## cur가 있다면, 다시말해 링크드리스트를 돌면서(cur가 next를 계속하다가 None을 만나면 while문을 빠져나오게 된다.)
            if cur.data == target:
                return cur
            cur = cur.next ## 순회(traversal)를 구현함
        return None

    def delete(self): ## 싱글링크드 리스트의 맨 앞을 지우게 된다.
        self.head = self.head.next ## 기존에 데이터를 참조횟수를 0으로 만들어서 없애버림
        self.d_size -= 1


    ## 아래에 트레버스 함수는 ADT에는 들어가지는 않는데 
    ## 데이터가 있으면 헤더부터 시작해서 반환해서 넘겨주는 함수 search와 비슷함

    def traverse(self):
        cur = self.head
        while cur:
            yield cur 
            cur = cur.next

## 쇼리스트 함수는 트레버스 함수를 이용해서 리스트를 사용자에게 보여주는 함수
## 자료구조에서 중요한 부분은 아니다.
def show_list(slist):
    print('data size : {}'.format(slist.size()))
    g = slist.traverse()
    for node in g:
        print(node.data, end = '  ')
    print()


## 사용자 부분의 구현
if __name__ == "__main__":

    print('*'*10)
    slist = SingleLinkedList() ## 우리가 쓸 자료구조를 하나 인스턴스를 만든다.

    print('데이터 삽입')
    slist.add(3)
    slist.add(4)
    slist.add(5)
    slist.add(1)
    show_list(slist)

    print('데이터 탐색')
    target = 3
    res = slist.search(target)
    if res:
        print('데이터 {} 검색 성공'.format(res.data))
    else:
        print('데이터 {} 검색 실패'.format(target))
    del res

    print('데이터 삭제')
    slist.delete()
    slist.delete()
    show_list(slist)
    
    print('*'*10)