力扣刷题记录---利用python实现链表的基本操作

---

前言

如何使用python实现链表的基本操作，包括结点的定义，链表的定义，求链表长度，链表是否为空等等一系列函数

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、利用python实现链表的基本操作

链表中的节点应该包含数值和指向下一个元素的地址。

1.节点的定义使用类实现：

class Node():def __init__(self,elem):self.elem = elemself.next = None

由于python万物皆对象，变量实际上是对象的引用，相当于就保存了对象的地址

1.链表的定义使用类实现：

链表的定义如下，也是使用类实现：

class Single_LinkList():def __init__(self,node = None):self.head = node

初始化时会自动生成一个空链表，其中head指向None

3.判断是否为空函数实现：

    def is_empty(self):"""链表是否为空"""if self.head == None:return Trueelse:return False

4.链表长度函数实现：

    def length(self):"""链表长度"""len = 0cur = self.headwhile cur != None:len = len + 1cur = cur.nextreturn len

5.遍历链表函数实现：

    def travel(self):"""遍历链表"""cur =  self.headwhile cur != None:print(cur.elem)cur = cur.next

6.头插法函数实现：

    def add(self,item):"""链表头部进行添加元素"""node = Node(item)node.next = self.headself.head = node

7.尾插法函数实现：

    def append(self,item):"""链表尾部进行添加元素"""node = Node(item)cur = self.headif self.is_empty():self.head = nodeelse:while cur.next != None:cur = cur.nextcur.next = nodenode.next = None

8.在链表指定位置插入值函数实现：

    def insert(self,pos,item):"""在指定位置上添加元素:param pos: 从0开始:param item::return:"""node = Node(item)count = 0cur = self.headwhile cur != None:if count == pos - 1:node.next = cur.nextcur.next = nodebreakcur = cur.nextcount = count + 1

9.删除某一个值函数实现：

    def remove(self,item):"""删除某一个节点"""cur = self.headcount = 0if self.is_empty():print("删除失败")elif self.head.elem == item:self.head = self.head.nextelse:while cur.next != None:if cur.next.elem == item:cur.next = cur.next.nextbreakcur = cur.next

10查看某个节点是否存在函数实现：

    def search(self,item):"""查看某个节点是否存在"""cur = self.headwhile cur != None:if cur.elem == item:return Truecur = cur.nextreturn False

完整代码如下：

class Node():def __init__(self,elem):self.elem = elemself.next = Noneclass Single_LinkList():def __init__(self,node = None):self.head = nodedef is_empty(self):"""链表是否为空"""if self.head == None:return Trueelse:return Falsedef length(self):"""链表长度"""len = 0cur = self.headwhile cur != None:len = len + 1cur = cur.nextreturn lendef travel(self):"""遍历链表"""cur =  self.headwhile cur != None:print(cur.elem)cur = cur.nextdef add(self,item):"""链表头部进行添加元素"""node = Node(item)node.next = self.headself.head = nodedef append(self,item):"""链表尾部进行添加元素"""node = Node(item)cur = self.headif self.is_empty():self.head = nodeelse:while cur.next != None:cur = cur.nextcur.next = nodenode.next = Nonedef insert(self,pos,item):"""在指定位置上添加元素:param pos: 从0开始:param item::return:"""node = Node(item)count = 0cur = self.headwhile cur != None:if count == pos - 1:node.next = cur.nextcur.next = nodebreakcur = cur.nextcount = count + 1def remove(self,item):"""删除某一个节点"""cur = self.headcount = 0if self.is_empty():print("删除失败")elif self.head.elem == item:self.head = self.head.nextelse:while cur.next != None:if cur.next.elem == item:cur.next = cur.next.nextbreakcur = cur.nextdef search(self,item):"""查看某个节点是否存在"""cur = self.headwhile cur != None:if cur.elem == item:return Truecur = cur.nextreturn False

测试代码如下：

if __name__ == "__main__":Linklist = Single_LinkList()print(Linklist.is_empty())print(Linklist.length())print(Linklist.append(1))print(Linklist.is_empty())print(Linklist.length())print(Linklist.append(2))print(Linklist.append(3))print(Linklist.append(4))print(Linklist.append(5))Linklist.add(8)Linklist.insert(1,10)Linklist.remove(8)# Linklist.remove(8)Linklist.travel()print(Linklist.search(1))

结果如下：