#!/usr/bin/env python
# coding: utf-8

# # Linked List

# In[1]:


from enum import Enum


# In[2]:


class Position(Enum):
    START = 0
    END = 2


# In[3]:


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
    def __repr__(self):
        return f'{self.__class__.__name__}({self.data})'


# # Insertions
# 1. Start: **O(1)**
# 1. Insert After: **O(n)**
# 1. End: **O(1)**

# In[4]:


class LinkedList:
    def __init__(self, ls = []):
        self.head = None
        self.tail = None
        self.count = len(ls)
        
        if self.count > 0:
            for item in ls:
                self._insertEnd(item)
    
    def _insertStart(self, data):
        self.count += 1
        
        tmp = Node(data)
        tmp.next = self.head
        self.head = tmp
        
        if self.tail is None:
            self.tail = self.head
            
        return tmp
    
    def _insertAfter(self, data, after):
        self.count += 1

        q = self.head

        while q is not None:
            if q.data == after:
                tmp = Node(data)
                tmp.next = q.next
                q.next = tmp
                
                if tmp.next is None:
                    self.tail = tmp
                    
                return tmp
            
            q = q.next
    
    def _insertEnd(self, data):
        self.count += 1

        if self.head is None:
            tmp = Node(data)
            self.head = self.tail = tmp
            return tmp
        
        tmp = Node(data)
        self.tail.next = tmp
        self.tail = self.tail.next
        
        return tmp


# # Deletions
# 1. Start: **O(1)**
# 1. Delete Element: **O(n)**
# 1. End: **O(n)**

# In[5]:


def _deleteStart(self):
    if self.count == 0:
        return
    
    self.count -= 1
    
    if self.head == self.tail:
        self.head = self.tail = None
        return
    
    tmp = self.head
    self.head = self.head.next
    
    return tmp

def _deleteEle(self, ele):
    if self.count == 0 or (self.count == 1 and self.head.data != ele):
        return
    
    if self.head.data == ele:
        return self._deleteStart()
    
    q = self.head
    
    while q.next is not None:
        if q.next.data == ele:
            tmp = q.next
            q.next = tmp.next
            
            if q.next is None:
                self.tail = q
            
            self.count -= 1
            
            return tmp
        
        q = q.next
    

def _deleteEnd(self):
    if self.count == 0:
        return
    
    self.count -= 1

    if self.head is self.tail:
        self.head = self.tail = None
        return
    
    q = self.head

    while q.next is not self.tail:
        q = q.next

    tmp = self.tail
    self.tail = q
    self.tail.next = None

    return tmp

LinkedList._deleteEle = _deleteEle
LinkedList._deleteStart = _deleteStart
LinkedList._deleteEnd = _deleteEnd


# # Public Interface

# In[6]:


def push(self, data, ele = Position.END):
    method =  {
        Position.START: self._insertStart,
        Position.END: self._insertEnd
    }.get(ele, self._insertAfter)

    if method == self._insertAfter:
        return self._insertAfter(data, ele)

    return method(data)

def pop(self, ele = Position.END):
    method =  {
        Position.START: self._deleteStart,
        Position.END: self._deleteEnd
    }.get(ele, self._deleteEle)

    if method == self._deleteEle:
        return method(ele)

    return method()

LinkedList.push = push
LinkedList.pop = pop


# # Dunders
# To make life easier

# In[7]:


def __repr__(self):    # For Debug purpose: it returns the string which upon executing, results in exact same object
    ls = []
    q = self.head

    while q is not None:
        ls.append(q.data)
        q = q.next

    return f'{self.__class__.__name__}({ls})'

def __str__(self):    # For User, pretty print of object
    q = self.head

    s = ''

    while q and q.next is not None:
        s += f'{q.data} -> '
        q = q.next

    s += f'{str(q.data)}' if q is not None else None

    return f'[{s}]'

def __len__(self):
    return self.count

LinkedList.__repr__ = __repr__
LinkedList.__str__ = __str__
LinkedList.__len__ = __len__


# # Tests

# In[8]:


ls = LinkedList()

ls.push(3, Position.END)
ls.push(1, Position.START)

ls.push(4, ele = 3)
ls.push(2, ele = 1)

ls.push(0, Position.START)
ls.push(5, Position.END)

ls.push(6)

print(f"Linked List ({len(ls)}) : {ls}")


# In[9]:


ls


# In[10]:


print(LinkedList([0, 1, 2, 3, 4, 5, 6]))    # Yield same result as all the above statements


# In[11]:


ls.pop(Position.START)
ls.pop(3)
ls.pop(Position.END)
print(f"Linked List ({len(ls)}) : {ls}")


# In[12]:


ls