from __future__ import annotations
from dataclasses import dataclass
from typing import Any, Optional


@dataclass
class _Node:
    """A node in a linked list.

    Note that this is considered a "private class", one which is only meant
    to be used in this module by the LinkedList class, but not by client code.

    Instance Attributes:
      - item: The data stored in this node.
      - next: The next node in the list, if any.
    """
    item: Any
    next: Optional[_Node] = None  # By default, this node does not link to any other node

from typing import Iterable

class LinkedList:
    """A linked list implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first node in this linked list, or None if this list is empty.
    _first: Optional[_Node]

    def __init__(self, items: Iterable) -> None:
        """Initialize an empty linked list.
        """
        self._first = None
        for item in items:
            self.append(item)

# linky = LinkedList([])
# linky._first = _Node('a', _Node('b', _Node('c')))

    def print_items(self) -> None:
        """Print out each item in this linked list."""
        curr = self._first
        while curr is not None:
            print(curr.item)  # Note: this is the only line we needed to fill in!
            curr = curr.next

    def to_list(self) -> list:
        """Return a built-in Python list containing the items of this linked list.

        The items in this linked list appear in the same order in the returned list.
        """
        items_so_far = []

        curr = self._first
        while curr is not None:
            items_so_far.append(curr.item)
            curr = curr.next

        return items_so_far

    def __getitem__(self, i: int) -> Any:
        """Return the item stored at index i in this linked list.

        Raise an IndexError if index i is out of bounds.

        Preconditions:
            - i >= 0
        """
        # VERSION 1: using an early return.
        curr = self._first
        curr_index = 0

        while curr is not None:
            if curr_index == i:
                return curr.item

            curr = curr.next
            curr_index = curr_index + 1

        # If we've reached the end of the list and no item has been returned,
        # the given index is out of bounds.
        raise IndexError

        # VERSION 2: using a compound loop condition.
        # curr = self._first
        # curr_index = 0
        #
        # while not (curr is None or curr_index == i):
        #     curr = curr.next
        #     curr_index = curr_index + 1
        #
        # assert curr is None or curr_index == i
        # if curr is None:
        #     # index is out of bounds
        #     raise IndexError
        # else:
        #     # curr_index == i, so curr is the node at index i
        #     return curr.item

    def __contains__(self, item: Any) -> bool:
        """Return whether <item> is in this list.

        Use == to compare items.
        """
        curr = self._first
        while curr is not None:
            if curr.item == item:
                return True
            curr = curr.next
        return False

# Custom
    def __len__(self) -> int:
        """Return the number of elements in this list.

        >>> lst = LinkedList()
        >>> lst.__len__()
        0
        # >>> lst2 = build_sample_linked_list()
        # >>> lst2.__len__()
        # 4
        """
        num = 0
        curr = self._first  # self is a LinkedList
        while curr is not None:
            num += 1
            curr = curr.next
        return num

    def count(self, item: Any) -> int:
        """Return the number of times the given item occurs in this list.

        Use == to compare items.

        >>> lst = LinkedList()
        >>> lst.count(111)
        0
        # >>> lst2 = build_sample_linked_list()
        # >>> lst2.count(111)
        # 2
        """
        num = 0
        curr = self._first
        while curr is not None:
            if item == curr.item:
                num += 1
            curr = curr.next
        return num

    def index(self, item: Any) -> int:
        """Return the index of the first occurrence of the given item in this list.

        Raise ValueError if the given item is not present.

        Use == to compare items.

        >>> lst = LinkedList()
        >>> lst.index(111)
        Traceback (most recent call last):
        ValueError
        # >>> lst2 = build_sample_linked_list()
        # >>> lst2.index(111)
        # 0
        # >>> lst2.index(9000)
        # 2
        """
        indx = 0
        curr = self._first

        while curr is not None:
            if item == curr.item:
                return indx
            else:
                indx += 1
                curr = curr.next
        raise ValueError

    def __setitem__(self, i: int, item: Any) -> None:
        """Store item at index i in this list.

        Raise IndexError if i >= len(self).

        Preconditions:
            - i >= 0

        >>> lst = LinkedList()
        >>> lst.__setitem__(0, 'hello')
        Traceback (most recent call last):
        IndexError
        # >>> lst2 = build_sample_linked_list()
        # >>> lst2.__setitem__(0, 'hello')
        # >>> lst2.to_list()
        # ['hello', -5, 9000, 111]
        # >>> lst2.__setitem__(2, 10000)
        # >>> lst2.to_list()
        # ['hello', -5, 10000, 111]
        """
        indx = 0
        curr = self._first

        while curr is not None:
            if i == indx:
                curr.item = item
                return
            else:
                indx += 1
                curr = curr.next
        raise IndexError

# Notes
    def append(self, item: Any) -> None:
        """..."""
        new_node = _Node(item)

        if self._first is None:
            self._first = new_node
        else:
            curr = self._first
            while curr.next is not None:
                curr = curr.next

            # After the loop, curr is the last node in the LinkedList.
            assert curr is not None and curr.next is None
            curr.next = new_node

    def insert(self, i: int, item: Any) -> None:
        """Insert the given item at index i in this list.

        Raise IndexError if i > len(self).
        Note that adding to the end of the list (i == len(self)) is okay.

        Preconditions:
            - i >= 0

        >>> lst = LinkedList([1, 2, 10, 200])
        >>> lst.insert(2, 300)
        >>> lst.to_list()
        [1, 2, 300, 10, 200]
        >>> lst.insert(6, 1)
        Traceback (most recent call last):
        IndexError
        """
        new_node = _Node(item)

        if i == 0:
            # Insert the new node at the start of the linked list.
            self._first, new_node.next = new_node, self._first
        else:
            curr = self._first
            curr_index = 0

            while not (curr is None or curr_index == i - 1):
                curr = curr.next
                curr_index = curr_index + 1

            # After the loop is over, either we've reached the end of the list
            # or curr is the (i - 1)-th node in the list.
            assert curr is None or curr_index == i - 1

            if curr is None:
                # i - 1 is out of bounds. The item cannot be inserted.
                raise IndexError
            else:  # curr_index == i - 1
                # i - 1 is in bounds. Insert the new item.
                curr.next, new_node.next = new_node, curr.next

    def pop(self, i: int) -> Any:
        """Remove and return the item at index i.

        Raise IndexError if i >= len(self).

        Preconditions:
            - i >= 0

        >>> lst = LinkedList([1, 2, 10, 200])
        >>> lst.pop(1)
        2
        >>> lst.to_list()
        [1, 10, 200]
        >>> lst.pop(2)
        200
        >>> lst.pop(0)
        1
        >>> lst.to_list()
        [10]
        >>> lst.pop(0)
        10
        >>> lst.to_list()
        []
        >>> lst.pop(0)
        <class 'IndexError'>
        """
        if self._first is None:
            return IndexError
        elif i == 0:
            first_item = self._first.item
            self._first = self._first.next
            return first_item
        prev, curr = None, self._first
        curr_index = 0
        while not (curr is None or curr_index == i):
            prev, curr = curr, curr.next
            curr_index = curr_index + 1
        if curr is None:
            raise IndexError
        else:
            prev.next = curr.next
            return curr.item

    def remove(self, item: Any) -> None:
        """Remove the first occurence of item from the list.

        Raise ValueError if the item is not found in the list.

        >>> lst = LinkedList([10, 20, 30, 20])
        >>> lst.remove(20)
        >>> lst.to_list()
        [10, 30, 20]
        >>> lst.remove(10)
        >>> lst.to_list()
        [30, 20]
        >>> lst.remove(30)
        >>> lst.to_list()
        [20]
        >>> lst.remove(20)
        >>> lst.to_list()
        []
        >>> lst.remove(0)
        Traceback (most recent call last):
        ValueError
        """
        prev, curr = None, self._first
        while not (curr is None or curr.item == item):
            prev, curr = curr, curr.next
        if curr is None:
            raise ValueError
        else:
            if prev is None:
                self._first = curr.next
            else:
                prev.next = curr.next