class SingleNode(object):
"""单链表的结点"""
def __init__(self,item):
# _item存放数据元素
self.item = item
# _next是下一个节点的标识
self.next = None
class SingleLinkList(object):
def __init__(self):
#初始化
self._head=None
def empty(self):
#判断是否为空
return self._head==None
def length(self):
#判断长度
c=self._head
cou=0
while c !=None:
cou+=1
c=c.next
return cou
def travel(self):
#遍历
c=self._head
while c!=None:
print (c.item)
c = c.next
print("")
def add(self,item):
#头部添加元素
node=SingleNode(item)
node.next=self._head
self._head=node
def append(self,item):
#尾部添加元素
node=SingleNode(item)
if self.empty():
self._head=node
else:
c=self._head
while c.next!=None:
c=c.next
c.next=node
def insert(self, pos, item):
"""指定位置添加元素"""
# 若指定位置pos为第一个元素之前，则执行头部插入
if pos <= 0:
self.add(item)
# 若指定位置超过链表尾部，则执行尾部插入
elif pos > (self.length()-1):
self.append(item)
# 找到指定位置
else:
node = SingleNode(item)
count = 0
# pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
pre = self._head
while count < (pos-1):
count += 1
pre = pre.next
# 先将新节点node的next指向插入位置的节点
node.next = pre.next
# 将插入位置的前一个节点的next指向新节点
pre.next = node
def remove(self,item):
cur=self._head
pre=None
while cur !=None:
if c.item==item:
if not pre:
self._head=cur.next
else:
pre.next=cur.next
break
else:
pre=cur
cur=cur.next
def search(self,item):
#检查链表是否存在
cur=self._head
while cur!=None:
if cur.item==item:
return True
return False
if __name__ == "__main__":
ll = SingleLinkList()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2, 4)
print ("length:",ll.length())
ll.travel()
print (ll.search(3))
print (ll.search(5))
ll.remove(1)
print ("length:",ll.length())
ll.travel()
