class LNode:
    def __init__(self,elem,next_=None):
        self.elem=elem
        self.next=next_

class LinkedListUnderflow(ValueError):
    pass
        
class LList:
    def __init__(self):
        self._head=None
        
    def is_empty(self):
        '''判断链表是否为空'''
        return self._head is None
    
    def prepend(self,elem):
        '''在链表的最前端加入元素'''
        self._head=LNode(elem,self._head)
        
    def append(self,elem):
        '''在链表的最后端加入元素'''
        if self._head is None:
            self._head=LNode(elem)
            return 
        p=self._head
        while p.next is not None:
            p=p.next
        p.next=LNode(elem)
        
    def insert(self,elem,i):
        '''在链表的中间加入元素'''
        if i==0:
            self.prepend(elem)
        if i>0:
            count=0
            p=self._head
            while count<i-1:
                p=p.next
                count+=1
            p_next=p.next
            p.next=LNode(elem,self._head)
            p.next.next=p_next
            
    def pop_first(self):
        '''删除最开始的元素'''
        if self._head is None: # 无结点
            raise LinkedListUnderflow("in pop")
        e=self._head.elem
        self._head=self._head.next
        return e 
        
    def pop_last(self):
        '''删除最末尾的元素'''
        if self._head is None:
            raise LinkedListUnderflow("in pop_last")
        p=self._head
        # 表中只有一个元素
        if p.next is None:
            e=p.elem
            self._head=None
            return e
        while p.next.next is not None:
            p=p.next
        e=p.next.elem
        p.next=None
        return e
    
    def pop_index(self,i):
        '''根据index删除元素'''
        if i==0:
            self.pop_first()
        else:
            count=0
            p=self._head
            while count<i-1:
                p=p.next
                count+=1
            
            p_next=p.next
            e=p.next.elem
            p.next=p_next.next
            return e 
    
    def find(self,r):
        '''查找第一个元素的index'''
        p=self._head
        count=0
        while p is not None:
            if p.elem==r:
                return count
            else:
                p=p.next
                count+=1
        return -1
    
    def forall(self,func):
        '''对于所有的元素执行某个操作'''
        p=self._head
        count=0
        while p is not None:
            e=p.elem
            p.elem=func(e)
            p=p.next
        
    def printall(self):
        '''打印所有的元素'''
        p=self._head
        while p is not None:
            print(p.elem,end='')
            if p.next is not None:
                print(',',end='')
            p=p.next
        print('')
        
    def __len__(self):
        '''判断链表的长度'''
        p=self._head
        count=0
        while p is not None:
            p=p.next
            count+=1
        return count

# 创造一个链表加入元素
mlist1=LList()
for i in range(10):
    mlist1.prepend(i)
for i in range(11,20):
    mlist1.append(i)
mlist1.insert(2222,0)
mlist1.printall()

# 删除index是1的元素
print(mlist1.pop_index(1))
mlist1.printall()

# 查找元素5所在的位置
mlist1.find(5)

# 对所有元素执行add1操作
def add1(x):
    return x+x
mlist1.forall(add1)
mlist1.printall()

# 分析链表的长度
len(mlist1)