#  本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
#  - Techielearning.com 是来自硅谷的科技职业发展平台。
#  - 本代码所属课程：<< Techie编程算法集训营 >>
#  - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
#  - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
#  - 官方网站：https://www.techielearning.com/
#  - 版权所有，禁止转发和分享
 
  class ListNode(object):
    def __init__(self, data, next = None):
      self.data = data
      self.next = next
 
  class MyLinkedList:
    def __init__(self):
      self._head = None
      self._tail = None
      self._size = 0
 
    def _get(self, head, index): 
      for _ in range(index):
        head = head.next
      return head
 
    def _create_with_one_node(self, val):
      self._head = self._tail = ListNode(val)
      self._size = 1
 
    def get(self, index: int) -> int:
      if 0 <= index < self._size:
        return self._get(self._head, index).data
      else:
        return -1
 
    def addAtHead(self, val: int) -> None:
      if self._size == 0:
        self._create_with_one_node(val)
      else:
        self._head = ListNode(val, self._head)
        self._size += 1
 
    def addAtTail(self, val: int) -> None:
      if self._size == 0:
        self._create_with_one_node(val)
      else:
        self._tail.next = ListNode(val)
        self._tail = self._tail.next
        self._size += 1
 
    def addAtIndex(self, index: int, val: int) -> None:
      if index < 0 or index > self._size:
        return
      if index == self._size:
        self.addAtTail(val)
      elif index == 0:
        self.addAtHead(val)
      else:
        pred = self._get(self._head, index - 1)
        pred.next = ListNode(val, pred.next)
        self._size += 1
 
    def deleteAtIndex(self, index: int) -> None:
      if index < 0 or index >= self._size:
        return
      if index == 0:
        self._head = self._head.next
        self._size -= 1
        if self._size == 0:
          self._tail = None
      else:
        pred = self._get(self._head, index - 1)
        pred.next = pred.next.next
        if index == self._size - 1:
          self._tail = pred
        self._size -= 1
 
    def __str__(self):
      strs = []
      node = self._head
      while node is not None:
        strs.append(str(node.data))
        node = node.next
      return ' -> '.join(strs)
 
    def __len__(self):
      return self._size