#encoding:utf-8
import sys
class Lnode():
def __init__(self,elem,next=None):
self.elem = elem #节点的值
self.next = next #指向下一个节点
def getelem(self):
return self.elem
def getnext(self):
return self.next
class linklist(object):
def __init__(self):
L = Lnode(None,None)
self.head = L #定义头节点
self.length = 0 #链表元素个数
# 链表是否为空
def isempty(self):
if self.head.next is None:
return True
else:
return False
def getlength(self):
return self.length
#尾部添加
def append(self,elem):
newNode = Lnode(elem)
if self.head.next is None:
self.head.next = newNode
else:
p = self.head
while p.next is not None:
p = p.next
p.next = newNode
self.length += 1
#头部添加
def headpush(self,elem):
newNode = Lnode(elem)
if self.isempty():
self.head.next = newNode
else:
newNode.next = self.head.next
self.head.next = newNode
self.length += 1
#在指定元素的位置后面插入
def insertafter(self,elem,newelem):
newNode = Lnode(newelem)
if self.find(elem) == -1:
print "%s in the link list" %elem
return -1
else:
#如果在链表中找到元素elem
p = self.find(elem)
if p.next is None:
p.next = newNode
else:
newNode.next = p.next
p.next = newNode
self.length += 1
# 在指定元素的位置前面插入
def insertbefor(self,elem,newelem):
newNode = Lnode(newelem)
if self.find(elem) == -1:
print "%s in not the link list" % elem
return -1
else:
p = self.head
q = self.find(elem)
while p is not None:
if p.next == q:
break
p = p.next
newNode.next = q
p.next = newNode
self.length += 1
#遍历链表
def for_each(self):
if self.head.next is None:
print "empty"
return
else:
p = self.head
while p.next is not None:
p = p.next
sys.stdout.write("%s " %(p.elem))
print
return
#查找元素，返回指向该元素的节点
def find(self,elem):
#找到元素返回节点，未找到返回-1
if self.isempty():
print "sorry,is empty"
return -1
else:
p = self.head
while p is not None:
if p.elem == elem:
return p
else:
p = p.next
return -1
#修改指定元素
def modify(self,elem,newelem):
if self.find(elem) != -1:
#如果找到
p = self.find(elem)
p.elem = newelem
return 0
else:
print "%s is not in the linklist" %elem
return -1
#删除指定元素
def delnode(self,elem):
if self.find(elem) != -1:
#如果找到
p = self.find(elem)
q = self.head
while q.next != p:
q = q.next
q.next = p.next
p.next = None
else:
print "%s is not in the linklist" %elem
return -1
def main():
#创建链表
ll = linklist()
print ll.isempty()
#尾部添加元素
ll.append(3)
ll.append(4)
ll.append(5)
ll.for_each()
print ll.getlength()
#首部添加元素
ll.headpush(2)
ll.for_each()
print ll.getlength()
#查找元素
print ll.find(3).elem
ll.insertafter(3,3.3)
ll.for_each()
print ll.getlength()
#测试后插法
ll.insertafter(1,1.1)
#测试前插法
ll.insertbefor(5,3.9)
ll.for_each()
print ll.getlength()
#修改指定元素
ll.modify(3.9,44)
ll.for_each()
ll.modify(3.8,88)
#删除指定元素
ll.delnode(3.3)
ll.for_each()
ll.delnode(2)
ll.delnode(2)
ll.delnode(3)
ll.delnode(4)
ll.delnode(44)
ll.delnode(5)
ll.for_each()
if __name__ == '__main__':
main()运行结果
True
3 4 5
3
2 3 4 5
4
3
2 3 3.3 4 5
5
1 in the link list
2 3 3.3 4 3.9 5
6
2 3 3.3 4 44 5
3.8 is not in the linklist
2 3 4 44 5
2 is not in the linklist
empty
Process finished with exit code 0
