大体思路
需要写两个类：
Node类：用于创建结点，并将结点以（人类）能看懂的字符串形式输出，而不是显示内存地址
LinkedList类：用于将各结点连成链表，并实现对链表进行操作的一些方法
代码
创建Node类：
class Node:
def __init__(self, data, next=None):
self.data = data # 数据，当前结点的元素
self.next = None # 指针，指向下一个结点
def __repr__(self): # 把结点表示为一个字符串
return "NodeValue({})".format(self.data)1234567
调用测试：
n = Node(1)print(n) # 因为写了__repr__方法，所以输出的是Node(1)，而不是内存地址12
创建LinkedList类：
准备工作：初始化方法 & 打印字符串方法
想要达到的输出效果类似于：
NodeValue(1) --> NodeValue(3) --> NodeValue(4) --> END
class LinkedList:
def __init__(self):
self.head = None # 初始化头结点
## 打印链表
def __repr__(self):
cursor = self.head
string_repr = ""
while cursor:
string_repr += f"{cursor} --> "
cursor = cursor.next
return string_repr + "END"123456789101112
「查」：方法
1. is_empty() 判断链表是否为空
def is_empty(self):
return self.head == None12
2. length() 返回链表长度
def length(self):
if self.head is None:
return 0
cursor = self.head
count = 0
while cursor:
count += 1
cursor = cursor.next
return count123456789
3. exist(data) 判断结点是否存在
def exist(self, data):
"""
:return: True or False
:rtype: Boolean
"""
cursor = self.head while cursor:
if cursor.data == data:
return True
else:
cursor = cursor.next
return False123456789101112
4. travel() 遍历整个链表
def travel(self):
if self.head is None:
return None
cursor = self.head while cursor:
print(cursor)
cursor = cursor.next1234567
5. getitem(index) 根据索引，得到链表中该位置的值
def getitem(self, index):
current = self.head if current is None:
raise IndexError("This is an empty linked list.")
for i in range(1, index):
# 目标超过链表范围
if current.next is None:
raise IndexError("Index out of range")
current = current.next
return current12345678910
6. search(data) 返回该结点出现的左数第一个的位置，不存在返回-1
def search(self, data):
if self.exist(data) == False:
return -1
else:
cursor = self.head
count = 0
while cursor:
count += 1
if cursor.data == data:
return count else:
cursor = cursor.next123456789101112
「增」：方法
7. insert_head(data) 在链表头部添加元素
def insert_head(self, data):
new_node = Node(data) # 创建一个新结点
if self.head: # 如果已存在头部结点
# 让新创建的结点的next指向原本的头结点
# 也就是说，新结点成为了原本的头结点的上一个结点
new_node.next = self.head
self.head = new_node # 重置头结点1234567
8. append(data) 在链表尾部添加元素
def append(self, data):
if self.head is None:
# 如果链表目前为空，则在头结点添加该元素
self.insert_head(data)
else:
cursor = self.head while cursor.next: # 遍历链表
cursor = cursor.next
# 创建一个新结点添加到链表尾部
cursor.next = Node(data)12345678910
9. insert(pos, data) 在链表中的指定位置添加元素
def insert(self, pos, data):
"""
:param pos: 要插入结点的位置，从0开始。
pos > 0，代表是从左开始数的位置
pos = 0，代表在头部添加
pos < 0，代表是从右开始数的位置，倒数从-1开始
也就是说 链表长度 + 倒数下标 = 正数下标
:type pos: int
:param data: 要插入的结点值
:type data: int
"""
if pos > 0:
if self.head is None:
# 如果链表目前为空，则在头结点添加该元素
self.insert_head(data)
else:
new_node = Node(data) # 创建一个新结点
# 通过循环，得到新结点的上一个结点
pre = self.head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 让新结点指向原本该位置的结点
new_node.next = pre.next
# 让上一个结点指向新结点
pre.next = new_node elif pos == 0:
self.insert_head(data)
elif pos < 0:
if self.head is None:
# 如果链表目前为空，则在头结点添加该元素
self.insert_head(data)
else:
new_node = Node(data)
# 通过循环，得到新结点正数顺序的上一个结点
leftpos = self.length() + pos
pre = self.head
count = 0
while count < (leftpos - 1):
count += 1
pre = pre.next
# 让新结点指向原本该位置的结点
new_node.next = pre.next
# 让上一个结点指向新结点
pre.next = new_node1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
「删」：方法
10. delete_head() 删除头结点
def delete_head(self):
temp = self.head if self.head:
self.head = temp.next
temp.next = None12345
11. delete_tail() 删除尾结点
cursor = self.head if self.head:
if self.head.next is None:
self.head = None
else:
while cursor.next.next:
cursor = cursor.next
cursor.next, cursor = None, cursor.next
elif self.head == None:
return "This is an empty linked list."12345678910
12. remove(data) 删除结点，若存在值相等的结点，仅删除左起第一个
def remove(self, data):
"""
:return: 返回删除结点后的链表；若传入的数据在链表中不存在，则返回原链表
"""
if self.exist(data) == False:
return self else:
pre = self.head
cursor = pre.next
count = 0
while cursor:
if cursor.data == data:
# 删除，也就是让该结点的上一结点直接连到该结点的下一结点
pre.next = cursor.next
cursor.next = None
return self else:
pre = pre.next
cursor = cursor.next12345678910111213141516171819
13. removeall(data) 删除结点，若存在值相等的结点，删除所有
def removeall(self, data):
"""
:return: 返回删除结点后的链表；若传入的数据在链表中不存在，则返回原链表
"""
while self.exist(data):
self.remove(data)
return self1234567
「改」：方法
14. setitem(index, data) 根据索引，为链表中该位置的值重新赋值
def setitem(self, index, data):
current = self.head if current is None:
raise IndexError("This is an empty linked list.")
for i in range(1, index):
# 目标超过链表范围
if current.next is None:
raise IndexError("Index out of range")
current = current.next
current.data = data12345678910
其他方法
15. linklist(object) 传入对象，一次性将序列中的所有元素构建成一个链表
def linklist(self, object):
self.head = Node(object[0])
temp = self.head for i in object[1:]:
node = Node(i)
# 将上一个结点指向下一个结点
temp.next = node
temp = temp.next
评论（0）