表的抽象数据类型

ADT list:                      #一个表的抽象数据类型

　　List(self)               #表的构造操作，创建一个空表

　　is_empty(self)        #判断self是否为一个空表

　　len(self)                #获得self的长度

　　prepend(self， elem)         #将元素elem加入表中作为第一个元素

　　append(self， elem)           #将元素elen加入表中作为最后一个元素

　　insert(self， elem， i)       #将elem加入表中作为第i个元素，其他元素的顺序不变

　　del_first(self)    #删除表中的首元素

　　del_last(self)     #删除表中的尾元素

　　del(self， i)     #删除表中第i个元素

　　search(self， elem)   #查找元素elem在表中出现的位置，不出现时返回-1

　　forall(self， op)     #对表中的每个元素执行操作op

1、构建结点对象

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

2、单链表的实现

class LList:     def __init__(self):         self._head = None     def is_empty(self):         return self._head is None     def len(self):         p = self._head         l = 0         while p is not None:             l += 1             p = p.next         return l     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 or i > self.len():             raise ValueError         if i == 0:             self.prepend(elem)         else:             p = self._head             while p is not None and i > 1:                 i -= 1                 p = p.next             p.next = LNode(elem, p.next)     def del_first(self):         if self._head is None:             raise ValueError         e = self._head.elem         self._head = self._head.next         return e     def del_last(self):         if self._head is None:             raise ValueError         p = self._head         if p.next is None:             self._head = None             return p.elem         while p.next.next is not None:             p = p.next         e = p.next.elem         p.next = None         return e     def del_(self, i):         if i<0 or i >= self.len() or self._head is None:             raise ValueError         if i == 0:             self.del_first()         else:             p = self._head             while p is not None and i > 1:                 i -= 1                 p = p.next             e = p.elem             p.next = p.next.next             return e     def search(self, elem):         p = self._head         i = 0         while p is not None:             if p.elem  == elem:                 return i             i += 1             p = p.next         return -1     def forall(self, op):         p = self._head         while p is not None:             op(p.elem)             p = p.next