python中的链表（linked list）是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表的数据结构如下图所示
在链表中删除操作可以通过修改指针来实现,如下图所示:
插入则是调整,插入点的前后两个指针的指向关系,如下图所示:
在python中每个变量都是指针,例如:
用内置数据结构(list, dict, tuple等）的嵌套/组合，它们隐式地包含了指向/嵌套关系，如graph[u][v]={w0,w1..}类的成员变量、嵌套类可能包含了指向/嵌套关系；
引用表示指向关系，只不过引用不能像指针一样运算，比如 p + 1 指向下一个元素，所以可能限制颇多.因此,要实现链表的操作,不能和c一样直接对指针进行操作.
1. 单向链表的实现
1.1 Node实现
每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。
classNode():__slots__=[‘_item’,’_next’] #限定Node实例的属性
def __init__(self,item):
self._item=item
self._next=None #Node的指针部分默认指向None
defgetItem(self):returnself._itemdefgetNext(self):returnself._nextdefsetItem(self,newitem):
self._item=newitemdefsetNext(self,newnext):
self._next=newnext
1.2 SinglelinkedList的实现
classSingleLinkedList():def __init__(self):
self._head=None #初始化链表为空表
self._size=0
1.3 检测链表是否为空
defisEmpty(self):return self._head==None
1.4 add在链表前端添加元素
defadd(self,item):
temp=Node(item)
temp.setNext(self._head)
self._head=temp
1.5 append在链表尾部添加元素
defappend(self,item):
temp=Node(item)ifself.isEmpty():
self._head=temp #若为空表，将添加的元素设为第一个元素
else:
current=self._headwhile current.getNext()!=None:
current=current.getNext() #遍历链表
current.setNext(temp) #此时current为链表最后的元素
1.6 search检索元素是否在链表中
defsearch(self,item):
current=self._head
founditem=Falsewhile current!=None and notfounditem:if current.getItem()==item:
founditem=Trueelse:
current=current.getNext()return founditem
1.7 index索引元素在链表中的位置
defindex(self,item):
current=self._head
count=0
found=Nonewhile current!=None and notfound:
count+=1
if current.getItem()==item:
found=Trueelse:
current=current.getNext()iffound:returncountelse:raise ValueError,’%s is not in linkedlist’%item
1.8 remove删除链表中的某项元素
defremove(self,item):
current=self._head
pre=Nonewhile current!=None:if current.getItem()==item:if notpre:
self._head=current.getNext()else:
pre.setNext(current.getNext())break
else:
pre=current
current=current.getNext()
1.9 insert链表中插入元素
definsert(self,pos,item):if pos<=1:
self.add(item)elif pos>self.size():
self.append(item)else:
temp=Node(item)
count=1pre=None
current=self._headwhile count
count+=1pre=current
current=current.getNext()
pre.setNext(temp)
temp.setNext(current)