写点什么

如何用 Python 实现一个单链表

作者:宇宙之一粟
  • 2022 年 2 月 13 日
  • 本文字数:5622 字

    阅读完需:约 18 分钟

单链表

在本博客中,我们介绍单链表这种数据结构,链表结构为基于数组的序列提供了另一种选择(例如 Python 列表)。

基于数组的序列也会有如下缺点:

  1. 一个动态数组的长度可能超过实际存储数组元素所需的长度

  2. 在实时系统中对操作的摊销边界是不可接受的

  3. 在一个数组内部执行插入和删除操作的代价太高

基于数组的序列和链表都能够对其中的元素保持一定的顺序,但采用的方式截然不同。

  • 数组是采用一整块的内存,能够为许多元素提供存储和引用。

  • 链表则是用更为分散的结构,采用称为节点的轻量级对象,分配给每一个元素。每个节点维护一个指向它的元素的引用,并含一个或多个指向相邻节点的引用。

链式结构

什么是线性表的链式存储,即采用一组任意的存储单元存放线性表的元素,这组存储元素可以是连续的,也可以是不连续的。连续的我们当然好理解,那如果不连续呢?就可以通过一条链来连接,什么是链?最直观的感受如下图:



我们知道,C 语言中有指针,指针通过地址来找到它的目标。如此说来,一个节点不仅仅有它的元素,还需要有一个它的下一个元素的地址。这两部分构成的存储结构称为节点(node),即节点包含两个域:数据域和指针域,结构的结构图如下:



Python 中的引用

那么,这里需要指针和地址,我们在学习基础的时候没听说 Python 有 C 或 C++中的指针啊,Python 中指针是什么?我们先把这个概念放一放,一提到指针可能初学 C 和 C++的人都害怕(本人也害怕),先来理解一下 Python 里面变量的本质。

 >>> a = 100 >>> b = 100 >>> id(a) 4343720720 >>> id(b) 4343720720 >>> >>> a, b = 10, 20 >>> id(a) 4343717840 >>> id(b) 4343718160 >>> a, b = b, a >>> id(a) 4343718160 >>> id(b) 4343717840 >>>
复制代码
  1. 当声明a = 100b = 100的时候,能发现id(a) == id(b),为什么 a 和 b 的 id 值是一样的呢?我们来看一下这个图:


我们利用上图来打一个比喻,可能不是很准确但方便我们进行理解。如果计算机被当成是一栋楼,那么内存空间就相当楼中的每个房间,内存地址就是这个房间的门牌号,这个房间内可以存储数据(比如数字 100,数字 10 或者其他类型)。

假如有一天,来了个要租房的小 a,小 a 说:“我看中了门牌号为(内存地址 4343720720)的这个房间”,并且放心的租用了这个房,所以 a = 100。小 a 就住在了这个房间里,当我们查询 id(a)的时候,计算机就返回给我们这个房间的门牌号(也就是内存地址 4343720720)。 同理,小 b 也看中了这个房子,并且也放心的住了下来。而且因为房间里存储的数据都是 100,即使虽然 a 和 b 的名字不同,但他们住同一房间,所以内存地址就相同。



  1. 当声明a = 10b = 20的时候,情况发生了改变,这个过程其实也好理解,就是相当于小 a 和小 b 分别看中了不同的房间(小 a 看中的是门牌号 4343717840 的房间,小 b 看中的是门牌号 4343718160),当他们住下来后,这个房间存着不同数据(a=10, b=20)。当他们进行交换的时候a, b = b, a,就相当于交换了房间,但是房间里的数据是没有变。最后a=20, b =10,因为内存地址 4343717840 存的数字就是 10,4343718160 存的数字是 20。

本来是要介绍单链表的,为什么讲到 Python 中的引用呢?因为我们要介绍的单链表这一数据结构就要利用到对象的引用 这一概念。变量本身就存储的一个地址,交换他们的值就是把自己的指向更改。Python 中没有指针,所以实际编程一般用引用来代替。这里对 Python 引用的介绍不是很详细,如果读者还是不明白,可以通过其他的资料进行深入了解。

节点定义与 Python 代码实现

节点,用于构建单链表的一部分,有两个成员:元素成员、指针域成员。

元素成员:引用一个任意的对象,该对象是序列中的一个元素,下图中的 a1、a2、…、an

指针域成员:指向单链表的后继节点,如果没有后继节点,则为空。



熟悉完链式结构,我们就能很好的写出节点的 Python 代码了。

 class Node(object):     """声明节点"""      def __init__(self, element):         self.element = element  # 给定一个元素         self.next = None  # 初始设置下一节点为空
复制代码

那么,什么是单链表

单链表 最简单的形式就是由多个节点的集合共同构成一个线性序列。每个节点存储一个对象的引用,这个引用指向序列中的一个元素,即存储指向列表的下一个节点。

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

其实,上面的术语用生活中的大白话来解释,就是我们现在有三个人——我、你、他。当我用手指指向你(注意:因为是单链表,所以你不能指向我),你用手指指向他,这样就形成了一个单链表。手指就是一个引用,而“我、你、他”就是序列中的元素。“我->你->他”方式就是一个简单单链表,不知道你理解了没有?

  • 头结点:链表的第一个节点

  • 尾节点:链表的最后一个节点 从头节点开始,通过每个节点的“next”引用,可以从一个节点移动到另一个节点,从而最终到达列表的尾节点。 若当前节点的“next”引用指向空时,我们可以确定该节点为尾节点。这一过程,我们通常叫做​​遍历链表​​。

单链表有哪些操作

链表的操作并不是很难,只要明白节点的结构:数据域 element 和指针域 next。而各种操作其实就是对指针的操作,不论是增删改查,都是先找指针,再取元素。具体有哪些基础操作是我实现的呢?如下(当然,还有更多的操作可能使我没想到的,希望你能在评论中提出来。)

  • 头插法

  • 尾插法

  • 指定位置将元素插入

  • 删除头结点

  • 删除尾节点

  • 删除指定元素

  • 修改指定位置上的元素

  • 遍历整个单链表

  • 查询指定元素是否存在

其他操作

  • 链表判空

  • 求链表长度

  • 反转整个链表(面试高频考点)

Python 实现单链表的上述操作

 # -*- coding: utf-8 -*- # @Author    : yuzhou1su # @File      : singly_linked_list.py # @Software  : PyCharm   class Node(object):     """声明节点"""      def __init__(self, element):         self.element = element  # 给定一个元素         self.next = None  # 初始设置下一节点为空   class Singly_linked_list:     """Python实现单链表"""      def __init__(self):         self.__head = None  # head设置为私有属性,禁止外部访问      def is_empty(self):         """判断链表是否为空"""         return self.__head is None      def length(self):         """返回链表长度"""         cur = self.__head  # cur游标,用来移动遍历节点         count = 0  # count记录节点数量         while cur is not None:             count += 1             cur = cur.next         return count      def travel_list(self):         """遍历整个链表,打印每个节点的数据"""         cur = self.__head         while cur is not None:             print(cur.element, end=" ")             cur = cur.next         print("\n")      def insert_head(self, element):         """头插法:在单链表头部插入一个节点"""         newest = Node(element)  # 创建一个新节点         if self.__head is not None:  # 如果初始不为空,就将新节点的"next"指针指向head             newest.next = self.__head         self.__head = newest  # 把新节点设置为head      def insert_tail(self, element):         """尾插法:在单链表尾部增加一个节点"""         if self.__head is None:             self.insert_head(element)  # 如果这是第一个节点,调用insert_head函数         else:             cur = self.__head             while cur.next is not None:  # 遍历到最后一个节点                 cur = cur.next             cur.next = Node(element)  # 创建新节点并连接到最后      def insert(self, pos, element):         """指定位置插入元素"""          # 如果位置在0或者之前,调用头插法         if pos < 0:             self.insert_head(element)         # 如果位置在原链表长度之后,调用尾插法         elif pos > self.length() - 1:             self.insert_tail(element)         else:             cur = self.__head             count = 0             while count < pos - 1:                 count += 1                 cur = cur.next             newest = Node(element)             newest.next = cur.next             cur.next = newest      def delete_head(self):         """删除头结点"""         cur = self.__head         if self.__head is not None:             self.__head = self.__head.next             cur.next = None         return cur      def delete_tail(self):         """删除尾节点"""         cur = self.__head         if self.__head is not None:             if self.__head.next is None:  # 如果头结点是唯一的节点                 self.__head = None             else:                 while cur.next.next is not None:                     cur = cur.next                 cur.next, cur = (None, cur.next)         return cur      def remove(self, element):         """删除指定元素"""         cur, prev = self.__head, None         while cur is not None:             if cur.element == element:                 if cur == self.__head:  # 如果该节点是头结点                     self.__head = cur.next                 else:                     prev.next = cur.next                 break             else:                 prev, cur = cur, cur.next         return cur.element      def modify(self, pos, element):         """修改指定位置的元素"""         cur = self.__head         if pos < 0 or pos > self.length():             return False         for i in range(pos - 1):             cur = cur.next         cur.element = element         return cur      def search(self, element):         """查找节点是否存在"""         cur = self.__head         while cur:             if cur.element == element:                 return True             else:                 cur = cur.next         return False      def reverse_list(self):         """反转整个链表"""         cur, prev = self.__head, None         while cur:             cur.next, prev, cur = prev, cur, cur.next         self.__head = prev   def main():     List1 = Singly_linked_list()     print("链表是否为空", List1.is_empty())      List1.insert_head(1)     List1.insert_head(2)     List1.insert_tail(3)     List1.insert_tail(4)     List1.insert_tail(5)      length_of_list1 = List1.length()     print("插入节点后,List1 的长度为:", length_of_list1)      print("遍历并打印整个链表: ")     List1.travel_list()      print("反转整个链表: ")     List1.reverse_list()     List1.travel_list()      print("删除头节点: ")     List1.delete_head()     List1.travel_list()      print("删除尾节点: ")     List1.delete_tail()     List1.travel_list()      print("在第二个位置插入5: ")     List1.insert(1, 5)     List1.travel_list()      print("在第-1个位置插入100:")     List1.insert(-1, 100)     List1.travel_list()      print("在第100个位置插入2:")     List1.insert(100, 2)     List1.travel_list()      print("删除元素5:")     print(List1.remove(5))     List1.travel_list()      print("修改第5个位置的元素为7: ")     List1.modify(5, 7)     List1.travel_list()      print("查找元素1:")     print(List1.search(1))   if __name__ == "__main__":     main()
复制代码

输出的测试结果

 链表是否为空 True 插入节点后,List1 的长度为: 5 遍历并打印整个链表:  2 1 3 4 5   反转整个链表:  5 4 3 1 2   删除头节点:  4 3 1 2   删除尾节点:  4 3 1   在第二个位置插入5:  4 5 3 1   在第-1个位置插入100: 100 4 5 3 1   在第100个位置插入2: 100 4 5 3 1 2   删除元素5: 5 100 4 3 1 2   修改第5个位置的元素为7:  100 4 3 1 7   查找元素1: True
复制代码

总结

在我们对这些基础操作熟练之后,我推荐的学习方法就是对网上(比如 LeetCode)上与单链表相关的习题进行练习。具体有哪些好的习题呢?等后面写博客找一些经典的题并把思路写出来,如果你找到了好的题欢迎分享给我,一起学习探讨。

发布于: 刚刚阅读数: 2
用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文

评论

发布
暂无评论
如何用 Python 实现一个单链表