# 浅谈python单向链表的实现

1. 单向链表的实现

1.1 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

def __init__(self):
self._size=0

1.3 检测链表是否为空

def isempty(self):

temp=node(item)

1.5 append在链表尾部添加元素

def append(self,item):
temp=node(item)
if self.isempty():
else:
while current.getnext()!=none:
current=current.getnext() #遍历链表
current.setnext(temp) #此时current为链表最后的元素

1.6 search检索元素是否在链表中

def search(self,item):
founditem=false
if current.getitem()==item:
founditem=true
else:
current=current.getnext()
return founditem

1.7 index索引元素在链表中的位置

def index(self,item):
count=0
found=none
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):
pre=none
while current!=none:
if current.getitem()==item:
if not pre:
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