class Node:
"""先定一个node的类""" def __init__(self, value=None, next=None):
self.value = value
self.next = next def getValue(self):
return self.value def getNext(self):
return self.next def setValue(self, new_value):
self.value = new_value def setNext(self, new_next):
self.next = new_next class LinkedList:
"""实现一个单向链表及其各类操作方法""" def __init__(self):
"""初始化空链表"""
self._head = Node()
self._tail = None
self._length = 0 def isEmpty(self):
"""检测是否为空"""
return self._head is None def add(self, value):
"""add在链表前端添加元素:O(1)"""
newnode = Node(value)
newnode.setNext(self._head)
# 注意这里的顺序不能和setNext()颠倒不然新增的节点找不到next
self._head = newnode def append(self, value):
"""append在链表尾部添加元素:O(n)
思路：遍历链表，在原链尾next指向新节点"""
newnode = Node(value)
if self.isEmpty():
# 若为空表，将添加的元素设为第一个元素
self._head = newnode
else:
# 从链首遍历链表
current = self._head
while current.getNext() is not None:
current = current.getNext()
# 找到最后一个，直接设置它的next指向新增的节点
current.setNext(newnode) def size(self):
"""获取链表的元素个数
从链头head开始遍历到链尾，同时用变量累加经过的节点个数"""
current = self._head
while current is not None:
current = current.getNext()
self._length += 1
return self._length def search(self, value):
"""查找元素是否在链表，找到返回True，否则返回False
从链头head开始遍历到链尾，并判断当前节点的数据是否为目标value"""
current = self._head
found = False
while current is not None and not found:
if current.getValue() == value:
found = True
else:
current = current.getNext()
return found def remove(self, value):
"""删除一个元素
遍历链表"""
current = self._head
previous = None
found = False while not found:
if current.getValue() == value:
found = True
# 找到后判断value是不是链首，是的话，head为value的下个节点
if not previous:
self._head = current.getNext()
else:
# 不是的话，将前一个节点的next指向要删除的节点的下一个节点
previous.setNext(current.getNext())
elif current.getNext() is not None:
# 之前的节点指向当前节点
previous = current
# 并找下一个节点作为循环的当前节点
current = current.getNext()
else:
raise ValueError('{} is not in LinkedList'.format(value)) def index(self, value):
"""返回元素在链表的位置，找不到抛出ValueError错误
遍历链表，并用count累加遍历过的每一个节点位置"""
current = self._head
count = 0
found = False while current is not None and not found:
if current.getValue() == value:
found = True
else:
current = current.getNext()
count += 1
if found:
return count
else:
raise ValueError('{} is not in LinkedList'.format(value)) def insert(self, position, value):
"""往链表position位置插入一个元素value"""
# 如果是链首，直接add添加
if position <= 1:
self.add(value)
# 如果是链尾，直接append
elif position > self.size():
self.append(value)
# 中间位置插入，思路也是从头遍历，找到position位置之前一个节点插入
# 并修改previous节点next指向新节点，新节点next指向position位置的节点
else:
temp = Node(value)
previous = None
count = 1
current = self._head
while count < position:
count += 1
previous = current
current = current.getNext() previous.setNext(temp)
temp.setNext(current) if __name__ == '__main__':
link = LinkedList()
link.add(4)
link.add(5)
link.add(6)
link.add(7)
print(link.remove(4))
print(link.size())