Python链表实现详解：从单链表到循环链表的边界处理

洛溪

发布时间：2026-10-13| 2人浏览过

原创

本文深入解析Python中链表的数据结构设计与算法实现。从基础的单链表节点定义出发，详细讲解头部与尾部插入、删除操作的代码逻辑，重点剖析空链表、单节点及多节点等边界条件下的指针处理。进一步探讨带尾节点的单链表及循环单链表的变体实现，通过具体代码示例展示如何优化插入与删除效率，帮助读者掌握链表核心机制。

本文通过具体实例，详细阐述Python中链表的数据结构定义及其常用用法，旨在为读者提供清晰的参考指南。

接下来将重点讲解以下内容：

（1）首先定义链表节点，采用面向对象编程思想，通过类来构建链表的基本结构。

（2）在实现链表类的插入和删除成员函数时，必须严格处理各种边界条件，具体包括：prepend（头部插入）、pop（头部删除）、append（尾部插入）以及pop_last（尾部删除）。

2.1 插入操作的边界情况：

需要特别考虑的情况包括：空链表状态链表仅包含1个节点在链表末尾进行插入操作

2.2 删除操作的边界情况：

需要特别考虑的情况包括：空链表状态链表仅包含1个节点删除链表末尾的元素

（3）从基础单链表扩展至多种单链表变体：

主要涵盖以下类型：带有尾节点引用的单链表循环单链表双链表

1. 链表节点的定义

class LNode:
 def __init__(self, elem, next_=None):
  self.elem = elem
  self.next = next_

2. 单链表的代码实现

核心在于深入理解插入与删除操作的实现逻辑，以及程序中必须考虑的各类边界条件：

class LinkedListUnderflow(ValueError):
 pass
class LList:
 def __init__(self):
  self._head = None
 def is_empty(self):
  return self._head is None
 def prepend(self, elem):
  self._head = LNode(elem, self._head)
 def pop(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop')
  e = self._head.elem
  self._head = self._head.next
  return e
 def append(self, elem):
  if self._head is None:
   self._head = LNode(elem)
   return
  p = self._head
  while p.next is not None:
   p = p.next
  p.next = LNode(elem)
 def pop_last(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop_last')
  p = self._head
  if p.next is None:
   e = p.elem
   self._head = None
   return e
  while p.next.next is not None:
   p = p.next
  e = p.next.elem
  p.next = None
  return e

简要总结关键点如下：

（0）访问 p.next.next 之前，必须确保 p.next 不为空；（1）执行尾部插入时，若链表非空，仅需修改尾部节点的指针指向；（2）执行尾部删除时，若链表长度非空，仅需修改倒数第二个节点的指针指向。

单链表的一种简单变体：带有尾部节点引用的单链表

class LList1(LList):
 def __init__(self):
  LList.__init__(self)
  self._rear = None
 ...

对于此类链表，我们主要需要重写以下三个方法：头部插入、尾部插入以及尾部删除。

def prepend(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._head = LNode(elem, self._head)
def append(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._rear.next = LNode(elem)
  self._rear = self._rear.next
def pop_last(self):
 if self._head is None:
  raise LinkedListUnderflow('in pop_last')
 p = self._head
 if p.next is None:
  e = p.elem
  self._head = None
  return e
 while p.next.next is not None:
  p = p.next
 e = p.next.elem
 self._rear = p
 p.next = None
 return e

单链表的另一种变体：循环单链表

class LCList:
 def __init__(self):
  self._rear = None
 def prepend(self, elem):
  if self._rear is None:
   self._rear = LNode(elem)
   self._rear.next = self._rear
  else:
   self._rear.next = LNode(elem, self._rear.next)
 def append(self, elem):
  self.prepend(elem)
  self_rear = self._rear.next
 def pop(self):
  if self._rear is None:
   raise LinkedListUnderflow('in pop')
  p = self._rear.next
  if p is None:
   self._rear = None
  else:
   self._rear.next = p.next
  return p.elem
 def printall(self):
  if self._rear is None:
   raise ...
  p = self._rear.next
  while True:
   print(p.elem)
   if p is self._rear:
    break
   p = p.next

如需了解更多Python相关知识，建议查阅本站系列专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》以及《Python文件与目录操作技巧汇总》。

希望本文所述内容能对各位的Python程序设计学习有所帮助。