단방향 연결 리스트 구현

class Node:
    # 단방향 연결 리스트 위한 노드
    def __init__(self,key = None):
        self.key = key
        self.next = None
    def __str__(self):
        return str(self.key)
        # v = Node()
        # print(v.key) # key값 출력
        # print(v) -> print(v.__str__()) 와 같음
'''
보통 이렇게 하지 않음 (매번 변수 선언)
a = Node(3)
b = Node(9)
c = Node(-1)
a.next = b
b.next = c
'''
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def pushFront(self,key):
        # O(1)
        v = Node(key)
        v.next = self.head
        self.head = v
        self.size += 1

    def pushBack(self,key):
        # O(n)
        v = Node(key)
        if len(self) == 0:
            self.head = v
        else:
            tail = self.head
            while tail.next != None:
                tail = tail.next
            tail.next = v
        self.size += 1
    
    def popFront(self):
        # O(1)
        if len(self) == 0:
            return None
        else: # 하나 이상은 존재
            x = self.head
            key = x.key
            self.head = x.next
            self.size -= 1
            del x
            return key

    def popBack(self):
        # O(n)
        if len(self) == 0:
            return None
        else:
            prev, tail = None, self.head
            while tail.next != None:
                prev = tail
                tail = tail.next
            if len(self) == 1:
                self.head = None
            else:
                prev.next = tail.next
            key = tail.key
            del tail
            self.size -= 1
            return key

    def __len__(self):
        return self.size
    
    def search(self, key):
        # key 값의 노드를 리턴, 없으면 None 리턴
        # O(n)
        v = self.head
        while v != None:
            if v.key == key:
                return v
            v = v.next
        return None

    # generator 스페셜 메소드 선언
    # search 연산과 비슷
    def __iter__(self):
        v = self.head
        while v != None:
            yield v # yield 는 return과 비슷
            v = v.next

L = SinglyLinkedList()
L.pushFront(1)
L.pushFront(2)
L.pushFront(3)
for x in L:
    print(x)