四、链表————相关概念详解

前言

• 在上一章我们学习了数组相关知识，我们知道数组在内存中是连续存在的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

一、链表是什么？

• 链表是一种线性的数据结构，其每个节点都都分为数值域与地址域，数值域中存储的是节点的数据，地址域中存储的是下一个 节点的地址，这样就可以把各个节点链接起来。
• 链表的设计如下图所示：
  
• 观察上图我们发现，链表由节点对象组成的，每个对象有两个属性：一个是数值域，一个是地址域。
  • 链表的首个节点称为头节点，最后一个节点叫做尾节点
  • 尾节点指向空，在Python中被记作None

代码演示 创建节点类 ：

class SingleNode(object):"""创建节点类"""def __init__(self, val = None):"""节点的 初始化方法  :param item: 接受这个节点 数值域的数据"""self.val = val  self.next = None  # 将 节点的地址域先定义为None

二、链表的类型

2.1 单向链表

• 即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
• 

2.2 环形链表

• 如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
• 

2.3 双向链表

• 与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
• 

三、链表中常用操作 (以单向列表为例)

3.1 初始化链表

• 首先是要初始化链表属性，使用虚拟头节点，头节点指向链表的第一个节点

代码如下（示例）：

class SingleLinkedList(object):# 初始化属性.def __init__(self, node = None):self.head = node   # head: 代表头结点

3.2 判断链表是否为空

代码如下（示例）：

def is_empty(self):# 思路1: 判断头结点(self.head) 是否为 None, 是: 空, 否: 不为空.# if self.head == None:#     return True# else:#     return False# 思路2: 上述代码的, 三元写法.return True if self.head == None else False# 思路3: 最终版, ==的结果本身就是: True 或者 False, 直接返回.# return self.head == None

3.3 获取链表长度

代码如下（示例）：

class SingleLinkedList(object):def length(self):# 1. 定义变量 cur, 记录当前节点, 从头结点开始.cur = self.head  # current: 当前# 2. 定义count变量, 计数.count = 0# 3. 判断当前节点是否为None, 如果不是, 就循环.while cur is not None:# 4. 每次循环, 计数器都+1, 然后获取下个节点.count += 1cur = cur.next  # 获取下个节点.# 5. 走到这里, 循环结束, 即: 链表长度统计完成, 返回结果即可.return count

3.4 插入节点

在链表节点 n0 和 n1 之间插入新节点N：

3.4.1 链表头部添加节点

代码如下（示例）：

class SingleLinkedList(object):# 定义  函数 head_add 用来在链表头部添加节点def head_add(self, val):# 1. 把要添加的元素封装成 新节点.new_node = SingleNode(val)# 2. 用 新节点的地址域 指向 头结点的地址.new_node.next = self.head# 3. 设置 新节点为 新的头结点即可.self.head = new_node

3.4.2 链表尾部添加节点

代码如下（示例）：

class SingleLinkedList(object):# 定义  函数 tail_add 用来在链表尾部添加节点def tail_add(self, val):# 1. 把要添加的元素封装成 新节点.new_node = SingleNode(val)# 2. 如果链表为空，则新节点直接充当头结点（使用上边我们定义的获取长度的函数）if self.length() == 0:self.head = new_nodeelse:# 3 走这里, 链表不为空, 获取链表的最后一个节点即可# 使用 cur 来充当指针cur = self.head# 4. 设置循环 从头边遍历到尾部while cur is not None：cur = cur.next# 5. 走到这里 , cur.next = None, 也就是最后一个节点cur.next = new_node 

3.4.3 指定位置添加节点

代码如下（示例）：

class SingleLinkedList(object):# 定义  函数 head_add 用来在链表尾部添加节点# pop 表示索引  val 表示要插入的元素值def insert(self, pop, val):# 1. 把要添加的元素封装成 新节点.new_node = SingleNode(val)# 2. 如果 插入的位置是否 小于等于 链表长度， 如果小于链表长度的话，# 那就说明是空链表，此时应该插入到最前面，也就是上边我们的往头部插入元素。if pop <= 0:self.head_add(val)# 3. 如果 插入的位置 大于或者等于 链表长度 ， 那就往尾部插入元素elif pop >= self.length():self.tail_add(val)		else:# 4. 如果是中间插入, 就走如下的逻辑.# 5. 把要插入的元素封装成: 新节点.new_node = SingleNode(val)# 6. 定义变量cur, 表示: 插入位置前的那个节点.cur = self.head# 7. 定义变量count, 初值为0, 表示插入位置前的哪个"索引"count = 0# 8. 只要 count < pos - 1 就一直循环, 并逐个获取下个节点.while count < pos - 1:  # 因为我们获取的地址域(即: 下个节点的地址), 只要找到前前对象, 它的地址域, 就是前对象.# 比如说: 要第2个节点, 只要找到第1个节点即可, 它的地址域(next)就是: 第2个节点.cur = cur.nextcount += 1          # 计数器+1# 9. 循环结束后, cur就是要插入位置前的 那个节点. 把它(cur)的地址域赋值 给 新节点的地址域.new_node.next = cur.next# 10. 把新节点的 地址 赋值给 cur节点的 地址域.cur.next = new_node

3.5 删除节点

删除链表中的节点的示意图如下：

代码如下（示例）：

class SingleLinkedList(object):def remove(self, val):# 1. 定义变量cur, 代表: 当前节点, 即: 要删除的节点.cur = self.head# 2. 定义变量pre(previous), 代表: 当前节点的前一个节点.pre = None# 3. 遍历链表, 获取到每个节点.while cur is not None:# 4. 判断当前节点的 数值域 是否和要被删除的内容一致.if cur.val== val:# 5. 如果一致, 判断当前节点是否是头结点, 是, 就直接指向它的地址域(第2个节点)即可.if cur == self.head:self.head = cur.next        # 如果要删头结点, 直接让 head指向 第2个节点即可.else:# 6. 如果要删除的节点不是头结点,pre.next = cur.next# 核心细节: 删除完毕后, 记得: break, 结束删除操作.breakelse:# 7. 如果不一致, 当前就是(前1个节点了), 然后当前节点为: 它的下个节点.pre = cur       # 当前节点: 就是下次判断的 前个节点cur = cur.next  # 当前节点: 变更为它的下个节点.

• 但是删除完成之后， 虽然 N 仍然指向 n1，但是遍历链表已经找不到该节点，因此我们认为这个节点已经被删除了（也可以多加一步，让 N.next = None 虽然会让 N 不再指向 n1 ，但实际上没什么用）

3.6 查找节点是否存在

代码如下（示例）：

class SingleLinkedList(object):def search(self, val):# 1. 定义变量cur, 表示当前节点, 默认从: 头结点开始.cur = self.head# 2. 遍历链表, 获取到每个节点.while cur is not None:# 3. 判断当前节点的数值域 是否和 要查找的值一致, 如果一致, 就返回Trueif cur.val== val:return True# 4. 如果没找到, 当前节点就变更为: 它的下个节点cur = cur.next# 5. 走到这里, 循环结束, 表示没有找到. 返回False即可.return False

3.7 遍历整个链表

代码如下（示例）：

class SingleLinkedList(object):def travel(self):# 1. 获取头结点, 充当: 当前节点.cur = self.head# 2. 只要当前节点不为空, 就一直遍历.while cur is not None:# 3. 先打印当前节点的 数值域, 然后获取下个节点.print(cur.val)cur = cur.next

四、数组跟链表的区别

• 由于它们采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。

总结

• 以上就是链表的概念跟基本操作。