[Python]연결리스트

리스트

연결 리스트

• 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결
• 노드: 각각의 원소. 포인터, 데이터를 포함하고 있다.

from __future__ import annotations
from typing import Any, Type

class Node:
    def __init__(self,data: Any, next: Node = None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self) -> None:
        self.no = 0
        self.head = None
        self.current = None

    def __len__(self) -> int:
        return self.no
    
    def search(self,data: Any) -> int:
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1

    def __contains__(self,data: Any) -> bool:
        return self.search(data) >= 0
    
    def add_first(self,data: Any) -> None:
        ptr = self.head
        self.head = Node(data,ptr)
        self.no += 1

    def add_last(self,data: Any) -> None:
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = Node(data,None)
        self.no += 1

    def remove_first(self) -> None:
        if self.head is not None:
            self.head = self.head.next
        self.no -= 1

    def remove_last(self) -> None:
        if self.head is not None:
            if self.head.next is None:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head
                while ptr.next is not None:
                    pre = ptr
                    ptr = ptr.next
                pre.next = None
                self.no -= 1

    def remove(self, p: Node) -> None:
        if self.head is not None:
            if p is self.head:
                self.remove_first()
            else:
                ptr = self.head

                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                ptr.next = p.next
                self.no -= 1

    def __iter__(self) -> LinkedListIterator:
        return LinkedListIterator(self.head)
    
class LinkedListIterator:
    def __init__(self,head : None):
        self.current = head

    def __iter__(self) -> LinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is None:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return data