链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向null。为了方便链表的删除与插入操作，可以为链表添加一个表头。
删除操作可以通过修改一个指针来实现。
插入操作需要执行两次指针调整。
1. 单向链表的实现
1.1 node实现
    每个node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个node。
class node(): __slots__=['_item','_next'] #限定node实例的属性 def __init__(self,item): self._item=item self._next=none #node的指针部分默认指向none def getitem(self): return self._item def getnext(self): return self._next def setitem(self,newitem): self._item=newitem def setnext(self,newnext): self._next=newnext
1.2 singlelinkedlist的实现
class singlelinkedlist(): def __init__(self): self._head=none #初始化链表为空表 self._size=0
1.3 检测链表是否为空
def isempty(self): return self._head==none
1.4 add在链表前端添加元素
def add(self,item): temp=node(item) temp.setnext(self._head) self._head=temp
1.5 append在链表尾部添加元素
def append(self,item): temp=node(item) if self.isempty(): self._head=temp #若为空表，将添加的元素设为第一个元素 else: current=self._head while current.getnext()!=none: current=current.getnext() #遍历链表 current.setnext(temp) #此时current为链表最后的元素
1.6 search检索元素是否在链表中
def search(self,item): current=self._head founditem=false while current!=none and not founditem: if current.getitem()==item: founditem=true else: current=current.getnext() return founditem
1.7 index索引元素在链表中的位置
def index(self,item): current=self._head count=0 found=none while current!=none and not found: count+=1 if current.getitem()==item: found=true else: current=current.getnext() if found: return count else: raise valueerror,'%s is not in linkedlist'%item
1.8 remove删除链表中的某项元素
def remove(self,item): current=self._head pre=none while current!=none: if current.getitem()==item: if not pre: self._head=current.getnext() else: pre.setnext(current.getnext()) break else: pre=current current=current.getnext()
1.9 insert链表中插入元素
def insert(self,pos,item): if posself.size(): self.append(item) else: temp=node(item) count=1 pre=none current=self._head while count 全部代码
class node(): __slots__=['_item','_next'] def __init__(self,item): self._item=item self._next=none def getitem(self): return self._item def getnext(self): return self._next def setitem(self,newitem): self._item=newitem def setnext(self,newnext): self._next=newnext class singlelinkedlist(): def __init__(self): self._head=none #初始化为空链表 def isempty(self): return self._head==none def size(self): current=self._head count=0 while current!=none: count+=1 current=current.getnext() return count def travel(self): current=self._head while current!=none: print current.getitem() current=current.getnext() def add(self,item): temp=node(item) temp.setnext(self._head) self._head=temp def append(self,item): temp=node(item) if self.isempty(): self._head=temp #若为空表，将添加的元素设为第一个元素 else: current=self._head while current.getnext()!=none: current=current.getnext() #遍历链表 current.setnext(temp) #此时current为链表最后的元素 def search(self,item): current=self._head founditem=false while current!=none and not founditem: if current.getitem()==item: founditem=true else: current=current.getnext() return founditem def index(self,item): current=self._head count=0 found=none while current!=none and not found: count+=1 if current.getitem()==item: found=true else: current=current.getnext() if found: return count else: raise valueerror,'%s is not in linkedlist'%item def remove(self,item): current=self._head pre=none while current!=none: if current.getitem()==item: if not pre: self._head=current.getnext() else: pre.setnext(current.getnext()) break else: pre=current current=current.getnext() def insert(self,pos,item): if posself.size(): self.append(item) else: temp=node(item) count=1 pre=none current=self._head while count