'# -*- coding: utf-8 -*-'
class Lnode(object):
# data:节点保存的数据
# next:相当于next指针，指向下一个节点
def __init__(self, data, pnext=None):
self.data = data
self.next = pnext
def __repr__(self):
# 用来定义node的字符输出
return str(self.data)
class Linklist(object):
def __init__(self):
self.head = None
self.length = 0
# 在链表头部添加节点
def prepend(self, value):
if self.head is None:
self.head = Lnode(value, None)
else:
newhead = Lnode(value, None)
newhead.next = self.head
self.head = newhead
self.length += 1
# 在链表尾部添加节点
def append(self, value):
if self.head is None:
self.head = Lnode(value, None)
else:
cursor = self.head
while cursor.next is not None:
cursor = cursor.next
cursor.next = Lnode(value, None)
self.length += 1
# 在链表的指定位置插入节点
def insert(self, index, value):
if self.head is None and index != 1:
return
if index <= 0 or index > self.getlength():
return
elif index == 1:
self.prepend(value)
elif index == self.getlength():
self.append(value)
else:
cursor = self.head
node = Lnode(value, None)
for i in range(1, index - 1):
cursor = cursor.next
node.next = cursor.next
cursor.next = node
# 删除指定位置的节点
def delnode(self, index):
if self.head is None:
return
if index <= 0 or index > self.getlength():
return
elif index == 1:
self.head = self.head.next
self.length -= 1
elif index == self.getlength():
cursor = self.head
for i in range(1, self.getlength() - 1):
cursor = cursor.next
cursor.next = None
self.length -= 1
else:
cursor = self.head
for i in range(1, index - 1):
cursor = cursor.next
t = cursor.next
cursor.next = t.next
self.length -= 1
# 删除值为value的链表节点元素
def delvalue(self, value):
if self.head is None:
return
elif self.head.data == value:
self.head = self.head.next
self.length -= 1
else:
pre = self.head
cursor = pre.next
while cursor is not None:
if cursor.data == value:
pre.next = cursor.next
cursor = cursor.next
self.length -= 1
else:
pre = cursor
cursor = cursor.next
# 按序号查找节点值
def getindex(self, index):
if self.head is None:
return
elif index <= 0 or index > self.getlength():
return
elif index == 1:
return self.head.data
else:
cursor = self.head
for i in range(1, index):
cursor = cursor.next
return cursor.data
# else:
# counter = 1
# cursor = self.head
# while cursor is not None:
# if index == counter:
# return cursor.data
# else:
# counter += 1
# cursor = cursor.next
# 求链表的长度
def getlength(self):
if self.head is None:
return 0
else:
count = 1
cursor = self.head
while cursor.next is not None:
count += 1
cursor = cursor.next
return count
# 单链表逆序
def diverse(self):
if self.head is None:
return
elif self.head.next is None:
return self.head
else:
pre = None
cursor = self.head
while cursor is not None:
ne = cursor.next
cursor.next = pre
pre = cursor
cursor = ne
self.head = pre
# 删除链表中重复元素
def delrepret(self):
if self.head is None:
return
if self.head.next is None:
return self.head
else:
data = self.head.data
# print(data)
count = 1
dic = {data: 1}
pre = self.head
cursor = pre.next
while cursor is not None:
print(cursor.data)
if dic.get(cursor.data) is None:
dic[cursor.data] = dic.setdefault(cursor.data, 1)
pre = cursor
cursor = cursor.next
print(dic)
else:
pre.next = cursor.next
cursor = cursor.next
self.length -= 1
# 判断链表是否为空
def isempty(self):
if self.head is None or self.getlength() == 0:
return True
else:
return False
# 删除列表
def dellist(self):
if self.head is None or self.getlength() == 0:
return
else:
cursor = self.head
while cursor is not None:
cursor.data = None
cursor = cursor.next
self.head = None
# 打印链表元素
def print(self):
if self.head is None:
return
else:
cursor = self.head
while cursor is not None:
print(cursor.data, end=' ')
cursor = cursor.next
print()
if __name__ == "__main__":
linklist = Linklist()
print(linklist.isempty())
for i in range(1, 5):
linklist.append(i)
linklist.prepend(1)
linklist.print()
print("按序号查找")
print(linklist.getindex(4))
print("&&&&&&&&&&&&&&&&")
linklist.insert(3, 5)
linklist.print()
linklist.insert(1, 1)
linklist.print()
linklist.insert(2, 2)
print(linklist.isempty())
linklist.print()
print("删除重复元素")
linklist.delrepret()
print("输出删除元素后的链表")
linklist.print()
# linklist.diverse()
# linklist.print()
linklist.delnode(5)
# linklist.delvalue(5)
# print("&&&&&&&&&&&&")
# linklist.print()
# print("**********")
# linklist.dellist()
# print("@@@@@@@@@@@@")
# length = linklist.getlength()
# print(length)
linklist.print()
网友评论