Python单链表原理与实现方法详解

Evan

发布时间：2026-10-12 | 3人浏览过

原创

本文详细介绍Python中单链表的原理与实现方法。内容涵盖链表基本概念、节点定义、头指针作用，以及头部插入、头部删除、尾部添加、指定位置插入和按值删除等核心操作的代码实现与逻辑解析，帮助读者深入理解链表数据结构。

本文通过具体实例，深入解析Python中单链表的原理及其实现方式，旨在为读者提供清晰的参考与学习思路。

关于链表

链表（Linked List）是一种由相同数据类型的数据项按特定顺序排列组成的线性表。
与数组在内存中连续存储不同，链表中的数据项在计算机内存中的位置是不连续且随机的。
链表在数据的插入和删除操作上具有显著优势，操作便捷；然而，其数据查找效率相对较低，且无法像数组那样实现随机读取。

单链表的实现

单向链表的节点由数据字段和指针两部分组成，其中指针指向下一个元素所在的内存地址。
在实现链表节点类时，需定义实例属性self.value用于存储节点数据，以及self.next表示指向下一节点的指针，初始值设为None。

class Node(object):
  def __init__(self, value=None, next=None):
    self.value = value
    self.next = next

在单链表中，第一个节点由头(head)指针指向，该节点被称为头指针节点。从该节点出发，可以遍历整个链表，执行元素查找、插入和删除等操作，因此头指针节点至关重要。通常情况下，我们不会移动head头指针本身。
单链表的最后一个节点称为尾节点，其指针域值为None，以此标识链表的结束。
构建单链表时，首先需要创建头指针节点。引入头指针的主要目的是简化链表操作；该头指针节点仅包含指向链表第一个实际节点的指针，其自身不包含实际数据值。

class linkedList(object):
  def __init__(self):
    self.head = Node()	# 创建头指针结点
    self.length = 0	# 初始链表长度，头指针节点不计入长度
  def __len__(self):	# 重写特殊方法返回self.length
    return self.length

完成链表初始化后，接下来定义链表的各种操作方法。
链表头部插入节点的操作步骤如下：
- 首先调用Node()构造函数，传入待插入的值value，创建新的待插入节点。
- 接着判断当前链表是否为空状态：
  - 若链表为空，则新插入的节点既是链表的头指针指向的节点，也是尾节点（其next指向None）。
- 若链表不为空：
  - 新插入节点的指针域指向原来的头指针节点，随后头指针重新指向新插入的节点。
  - 具体操作中，需先将原头指针节点保存到临时变量中，这是为了防止在head指针变更时发生指针断裂导致后续数据丢失。链表中的指针如同连接的纽带，若其中某个纽带断裂（即指针指向其他位置），则后续所有数据都将无法访问。
  - 随后，将头指针指向新插入的节点。
  - 最后，将新插入节点的指针指向原头指针节点。
  - 完成插入后，链表长度加1。
- ```
  def head_insert(self, value): # 链表头部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指针域指向原head元素
      tmp_head = self.head.next # 原头指针节点存储到tmp_head
      self.head.next = node # 新head指针指向node
      node.next = tmp_head # 新插入节点指向原头指针节点
    self.length += 1
```
链表头部删除节点的操作步骤如下：
- 同样先判断链表是否为空，若为空则返回False。
- 当链表不为空时：
  - 将头指针的指针域（即存放下一节点内存地址的部分）指向头指针本身。这意味着链表的第一个实际节点变成了新的头指针head。由于头指针节点本身不计入链表长度，这种操作等效于删除了第一个实际节点。
  - 同时，返回被删除节点的值。
- ```
  def head_del(self): # 删除头结点,返回头结点的值
    if self.head.next == None:
      return False
    else:
      # 头指针指针域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value
```

链表尾部添加节点的操作步骤如下：

首先创建待插入的节点对象。
判断链表是否为空，若为空，则头指针节点直接指向该待插入节点，此时该节点既是头也是尾。
若链表不为空：
- 通过while循环（判断条件为节点指针是否为None）找到当前链表的最后一个元素。
- 将当前最后一个元素的指针指向待插入节点。
- 链表长度加1。

  def append(self, value):  # 链表尾部添加结点
    # 创建新插入的结点对象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一个节点，指针指向自己
    else:
      curnode = self.head.next  # 变量curnode存放指针
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 当为最后一个节点时，指针指向新插入节点
    self.length += 1

在指定位置后面插入节点的操作步骤如下：
- 该方法接收两个位置参数：index表示插入位置，value表示插入值。
- 首先创建新节点对象。
- 判断链表是否为空。
- 在链表不为空的条件下：
  - 定义一个变量表示当前节点，以及一个索引比较数i。
  - 使用while循环，当索引比较数i不等于目标index时，更新当前节点以推进遍历。
  - 找到目标索引位置的节点后，首先让插入节点的指针指向该索引位置节点的下一个节点。
  - 然后让索引位置节点的指针指向插入节点。
  - 链表长度加1。
- ```
def insert(self, index, value):
	node = Node(value)
  if self.length == 0:
    self.head.next = node
  else:
    i = 0
    cur_node = self.head.next
    while i != index:
      cur_node = cur_node.next
      i += 1
    node.next = cur_node.next
    cur_node.next = node
  self.length += 1
```

给定值删除该值节点的操作步骤如下：

要删除链表中给定值的节点，需要遍历整个链表，因此需要创建一个可迭代对象。
定义节点迭代方法。

def iter_node(self):
  cur_node = self.head.next	#当前节点
  while cur_node.next != None:	# 对除最后一个节点进行可迭代化处理
    yield cur_node
    cur_node = curnode.next
  if cur_node.next == None:	# 对尾节点进行可迭代化处理
    yield cur_node

重写特殊方法__iter__，用于声明该类为迭代器。

def __iter__(self): # 遍历列表节点
  for node in self.iter_node():
     yield node.value

首先定义一个Flag变量（默认为False），用于表示删除操作是否成功。
同样先判断链表是否为空。
当链表不为空时：
- 设置一个前驱节点（当找到需要删除的节点时，先让前驱节点的指针指向删除节点的后继节点）。
- for循环遍历链表
  - 找到符合条件的值后，让前驱节点指向删除节点的后继节点，然后使用del删除node对象，并将Flag更改为True。
  - 若未找到符合条件的值，则更新前驱节点，继续遍历后续节点。

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置节点为头结点
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置节点的值
      return Flag

完整代码：

# 定义链表节点类
class Node(object):
  def __init__(self, value=None, next=None):
    self.value = value # 节点元素
    self.next = next  # 指针


# 单链表类
class LinkedList(object):
  def __init__(self):
    self.head = Node() # 创建头结点
    self.length = 0 # 初始化链表长度

  def __len__(self):
    return self.length

  def __iter__(self): # 遍历列表节点
    for node in self.iter_node():
      yield node.value

  def iter_node(self):
    curnode = self.head.next
    while curnode.next != None:
      yield curnode
      curnode = curnode.next
    if curnode.next == None:
      yield curnode

  def head_insert(self, value): # 链表头部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指针域指向原head元素
      tmp_head = self.head.next # 原头指针节点存储到tmp_head
      self.head.next = node # 新head指针指向node
      node.next = tmp_head # 新插入节点指向原头指针节点
    self.length += 1

  def head_del(self): # 删除头结点,返回头结点的值
    if self.head.next == None:
      return False
    else:
      # 头指针指针域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value

  def append(self, value):  # 链表尾部添加结点
    # 创建新插入的结点对象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一个节点，指针指向自己
    else:
      curnode = self.head.next  # 变量curnode存放指针
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 当为最后一个节点时，指针指向新插入节点
    self.length += 1
	
  # 这里的insert是指定值后面插入不是指定位置
  def insert(self, index, value):
    node = Node(value)
    if self.length == 0:
      self.head.next = node
      self.length += 1
    else:
      for nd in self.iter_node():
        if nd.value == index:  # 如果nd节点值等于index，则插入到nd后
          tmp_node = nd.next # 将nd的指针存放到中间变量
          nd.next = node # nd节点指向插入节点
          node.next = tmp_node  # 插入节点指向原nd.next节点
          self.length += 1
          return True
      return False

  def replace(self, old_value, new_value):
    index = 0
    if self.length == 0:
      return False
    else:
      for node in self.iter_node():
        if node == old_value:
          node.value = new_value
          index += 1
    if index != 0:
      return index # 替换节点数量(存在节点值相同情况)
    else:
      return False  # 替换失败，未找到替换值

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置节点为头结点
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置节点的值
      return Flag



# 测试
l = LinkedList()
l.append(1)
l.append(2)
l.append(7)
l.append(5)
l.append(6)
l.append(7)
l.head_insert(3)
print("当前链表长度：%s" %l.length)
#print("删除头结点为：%d"% l.head_del())
print("当前链表长度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
  print("第%d个链表节点的值: %d"%(i, node))
  i += 1

运行结果：