用最容易的方式学会单链表（Python实现）

  • 2019 年 10 月 30 日
  • 筆記

单链表与数组

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

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

  1. 一个动态数组的长度可能超过实际存储数组元素所需的长度
  2. 在实时系统中对操作的摊销边界是不可接受的
  3. 在一个数组内部执行插入和删除操作的代价太高

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

  • 数组是采用一整块的内存，能够为许多元素提供存储和引用。
  • 链表则是用更为分散的结构，采用称为节点的轻量级对象，分配给每一个元素。每个节点维护一个指向它的元素的引用，并含一个或多个指向相邻节点的引用。

链式结构

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

chains_1251px_1205993_easyicon.net.png

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

节点.png

Python中的引用

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

>>> a = 100  >>> b = 100  >>> id(a)  4343720720  >>> id(b)  4343720720  >>>

我们能看到id(a) == id(b)，为什么a和b的ID是一样的呢？我们来看一下这个图：

id.png

我们利用上图来打一个比喻，可能不是很准确方便我们进行理解。如果计算机中当成是一栋房屋，那么内存地址（4343720720）就应该是其中的一个房子，这个房子可以存储数据（100，也可以存10），而房名就是变量名（a、b）。房子被小a买走了（利用起来），小a就指向这个房子，同理，小b也指向这个房子。房子里存储的数据都是100，所以虽然a和b的名字不同，但他们住同一房子。

我们再来看一下下面这个代码：

>>> a, b = 10, 20  >>> id(a)  4343717840  >>> id(b)  4343718160  >>> a, b = b, a  >>> id(a)  4343718160  >>> id(b)  4343717840  >>>

2.png

是不是也非常好理解了，小a和小b买了不同的房子（4343717840和4343718160），存着不同的数据（a=10, b=20）。最后他们交换了房子，同时交换了房里的数据。

变量本身就存储的一个地址，交换他们的值就是把自己的指向更改。Python中没有指针，所以实际编程一般用引用来代替。这里对Python引用的介绍不是很详细，如果读者还是不明白，可以通过其他的资料进行深入了解。

节点定义与Python代码实现

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

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

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

timg.jpeg

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

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

那么，什么是单链表

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

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

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

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

  • 尾节点：链表的最后一个节点

    从头节点开始，通过每个节点的“next”引用，可以从一个节点移动到另一个节点，从而最终到达列表的尾节点。

    若当前节点的“next”引用指向空时，我们可以确定该节点为尾节点。这一过程，我们通过叫做遍历链表。

单链表有哪些操作

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

增

  • 头插法
  • 尾插法
  • 指定位置将元素插入

删

  • 删除头结点
  • 删除尾节点
  • 删除指定元素

改

  • 修改指定位置上的元素

查

  • 遍历整个单链表

  • 查询指定元素是否存在

其他操作

  • 链表判空
  • 求链表长度
  • 反转整个链表（面试高频考点）

Python实现单链表的上述操作

# -*- coding: utf-8 -*-  # @Time      : 2019-10-30 15:50  # @Author    : yuzhou_1su  # @ContactMe : https://blog.csdn.net/yuzhou_1shu  # @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 != Node:              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）上与单链表相关的习题进行练习。具体有哪些好的习题呢？等后面写博客找一些经典的题并把思路写出来，如果你找到了好的题欢迎分享给我，一起学习探讨。

VirMach 便宜 VPS

QNews

QNews