Python数据结构与算法之链表,无序链表详解

小鹿同学

发布时间：2026-10-15 | 5人浏览过

原创

本文详细解析Python中无序链表的实现原理。从Node节点类的数据与引用构建，到LinkList类的头指针管理，深入讲解add、length、search及remove方法的具体实现。重点剖析节点添加时的引用指向顺序、遍历查找逻辑以及移除节点时双指针“蠕动”机制与头节点特殊处理，帮助开发者掌握链表核心操作。

链表由一系列元素组成，这些元素在内存中的存储位置是分散且不连续的。

无序链表是指逻辑上元素顺序无特定规律的集合，仅通过链表结构进行连接。尽管元素整体分布看似随机，但每个元素都包含指向其他元素的相对位置信息。因此，链表需维护元素间的相对顺序，而无需在特定内存块中集中存储位置信息。

以图中元素集合为例，各元素位置看似随机。若为每个元素附加指向下一个元素位置的信息，即可通过自身指向下一元素的链接来表示相对位置。

附加该信息后，结构可表示为：

使用链表时，必须明确链表中第一个元素的位置。确定首元素位置后，即可依据其中的链接信息依次访问后续元素。指向链表首个元素的引用被称为“头”（head）。最后一个元素需标识其无后续节点。

观察链表可知，每个元素被视为一个节点，链表通过节点间的相对位置关系将这些节点串联。每个节点至少包含两个基本属性：一是存储数据的变量，二是指向下一个节点位置的引用。

首先构造节点。

节点（Node）是构建链表的基础数据结构。每个节点对象需持有至少两项信息：一是数据元素，称为节点的数据变量；二是指向下一个节点的引用。以下代码展示了Node类的Python实现。构建节点时需传入初始值，Node类还需包含访问和修改数据的方法，以及指向下一个元素的引用。

class Node:
    def __init__(self, initdata):
        self.data = initdata  # 数据元素
        self.next = None      # 指向下一节点的引用
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newdata):
        self.data = newdata
    def setNext(self, newnext):
        self.next = newnext

需注意，None在Node类及后续链表中至关重要。节点指向None的引用表示后续无新节点。因此，在Node的构造方法中，将next的初始值设为None。

节点（Node）类构建完成后，接下来构建整个链表（LinkList）类。

如前所述，链表基于节点集合构建，每个节点通过显式引用指向下一个节点。只要知晓第一个节点的位置（包含第一个元素），后续元素均可通过对下一节点的引用找到。因此，LinkList类必须包含指向第一个节点的引用。下列代码展示了LinkList类的构造方法。

class LinkList:
    def __init__(self):
        self.head = None

下图展示了链表无节点和有节点的两种情况：

我们已具备创建链表头的方法，规定链表头初始指向为None；当链表包含内容（节点）时，链表头则指向该节点。

此外，还需提供一个方法来判断链表头的指向状态。

使用isEmpty方法检查链表头部是否指向None。布尔表达式self.head == None仅在链表中无节点时为真。由于新链表初始为空，构造方法必须与检查是否为空的方法保持一致，这体现了使用None表示链表末尾的优势。

class LinkList:
    def isEmpty(self):
        return self.head == None

接下来构建链表节点的添加方法。

为实现将节点添加到链表的功能，需实现add方法。但在实现前，需解决一个重要问题：新节点应置于链表的何处？由于链表是无序元素集合，新元素相对于已有元素的位置并不重要，可置于任意位置。因此，将新元素置于最简便位置最为合理。由于链表仅提供一个入口（头部），其他所有节点均需通过第一个节点及next链接访问。这意味着添加新节点最简便的位置是头部，即链表的起点。我们将新节点作为链表的第一个节点，并将已有节点链接到该元素之后。

下列代码展示了add方法的实现：

class LinkList:
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

代码第3行创建新节点，并将item作为其数据。接下来需将新节点与现有链表结构链接，此过程分两步，如下图所示。图中第1步（代码第4行），将新节点的next引用指向当前链表中的第一个节点，从而使原链表与新节点正确链接。图中第2步，修改链表头的指向，使其指向新创建的节点。代码第5行的赋值语句完成此操作。

上述两步的执行顺序至关重要。若颠倒代码第4行和第5行的顺序，即先修改链表头指向，由于头节点是唯一指向链表节点的外部引用，所有已有节点将丢失且无法访问。

接下来需实现length、search及remove方法，这些方法均基于链表遍历。遍历指系统性地访问每个节点，具体做法是使用额外外部引用从链表的头节点开始访问。随着访问每个节点，将该外部引用通过“遍历”下一个引用指向下一个节点。

实现length方法（计算链表中节点的个数/链表长度）。

class LinkList:
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

为实现length方法，需遍历链表并记录访问过的节点数量。上述代码展示了计算链表中节点个数的Python代码。current即为外部引用，在第3行初始化为链表头的引用。若链表中无节点，current将指向None；若有节点，current此时指向链表中的第一个节点。

计算开始时，因未访问任何节点，count初始化为0。第5~7行实现遍历过程。只要current指向的不是链表结尾（None），就将其指向下一个节点（第7行）。每当current指向新节点时，将count加1。最终，循环完成后返回count。

实现search方法（搜索链表中的某个节点）。

在链表中搜索值同样需用到遍历。每访问一个节点时，检查该节点中的元素是否与要搜索的元素相同。搜索时，可能无需完整遍历链表即可找到该元素。事实上，若遍历至链表末尾仍未找到，则意味着目标元素不在链表中。若在遍历过程中找到所需元素，则无需继续遍历。

class LinkList:
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

上述代码展示了search方法的实现。与length方法类似，遍历从列表头部开始（第3行）。使用布尔型变量found标记是否找到所需元素。由于初始未找到，第4行将found初始化为False。

第5行的循环既考虑是否到达链表末尾，也考虑是否已找到目标元素。只要还有未访问节点且未找到目标元素，就继续检查下一个节点。第6行检查当前节点中的元素是否为目标元素。若是，将found设为True。

实现remove方法（移除链表中的某个节点）。

remove方法在逻辑上需分两步执行。

第1步，遍历列表并查找要移除的元素（节点）。一旦找到该元素（假设元素在链表中），就必须将其移除。第1步与search非常相似。从一个指向链表头节点的外部引用开始，遍历整个链表，直到遇到需移除的元素。假设目标元素已在链表中，因此预测循环会在current抵达None之前结束。这意味着可在判断条件中使用布尔型变量found。

第2步，移除元素（节点）。当found被设为True时，current将指向需移除的节点。如何移除它？一种做法是将节点包含的值替换为表示其已被移除的标识值（如None或Null，可自定义）。但此做法的问题是节点数量与元素数量不再匹配。更好的做法是移除整个节点。

为将包含元素的整个节点移除，需将其前一个节点中的next引用指向current之后的节点。然而，链表不支持反向遍历。由于current已指向需修改节点之后的节点，此时直接修改为时已晚。

解决此困境的方法是在遍历链表时使用两个外部引用。current与之前一样，标记在链表中的当前位置。新增引用previous总是指向current上一次访问的节点。这样一来，当current指向需被移除的节点时，previous就刚好指向真正需要修改next引用的节点。

class LinkList:
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
                if current == None:
                	return found
        if previous == None:
            self.head = current.getnext()
        else:
            previous.setNext(current.getNext())

上面的代码展示了完整的remove方法。第3~4行对两个引用进行初始赋值。注意，current与其他遍历例子一样，从链表的头节点开始。由于头节点之前无其他节点，previous的初始值为None。

第7~8行检查当前节点中的元素是否为要移除的元素。若是，设found为True。若否，则将previous和current往下一个节点的方向各移动一次。这两条语句的顺序至关重要。必须先将previous移动到current的位置，然后再移动current。此过程常被称为“蠕动”，因为previous必须在current移动之前指向其当前位置。

下图展示了这一过程：

一旦搜索过程结束，即需执行移除操作。如移除图中数据值为17的节点，修改过程如下：

有一种特殊情况需注意，若被移除的节点正好是链表的第一个节点，那么current会指向链表中的第一个节点，previous的值则是None。在这种情况下，需修改链表的头节点，而非previous指向的节点，如图所示：

代码第13行检查是否遇到上述特殊情况。若previous未移动，当found被设为True时，其值仍为None。在这种情况下（第13行），链表的头节点指向被修改成指向当前头节点的下一个节点，从而达到移除头节点的效果。但若previous的值不是None，则说明需移除的节点在链表结构中的某位置。此时，previous指向了next引用需被修改的节点。第16行使用previous的setNext方法完成移除操作。注意，在两种情况中，修改后的引用均指向current.getNext()。

代码汇总

# 构造节点
class Node:
    def __init__(self, initdata):
        self.data = initdata      # 数据元素
        self.next = None          # 指向下一节点的引用（python变量赋值的本质是引用）
    def getData(self):            # 获取节点的数据元素值
        return self.data
    def getNext(self):            # 获取下一节点的引用 若有节点则直接视作为下一节点
        return self.next
    def setData(self, newdata):   # 给节点的数据元素设置值
        self.data = newdata
    def setNext(self, newnext):   # 给节点设置对下一节点的引用
        self.next = newnext

# 构造链表
class LinkList:
    def __init__(self):            # 设置链表的头部指向 无节点时为None 
        self.head = None
    def isEmpty(self):             # 判断链表是否为空（是否有节点）
        return self.head == None
    def add(self, item):           # 给链表增加新节点（从链表头位置增加）
        temp = Node(item)            # 创建节点并对新节点数据元素赋值
        temp.setNext(self.head)      # 新节点指向当前链表中的第一个节点
        self.head = temp             # 链表头指向新节点
    def length(self):               # 计算链表长度（节点个数）
        current = self.head           # 引入current作为指向标识 指向第一个节点 或者None
        count = 0                     # 引入count作为计数变量
        while current != None:        # 当指向标识指向的不是链表末尾的None时
            count = count + 1           # 节点计数加一
            current = current.getNext() # 指向标识向后移动
        return count
    def search(self, item):                   # 搜索链表中节点
        current = self.head                     # 引入current作为指向标识 指向第一个节点
        found = False                           # 引入found作为寻找状态标识
        while current != None and not found:    # 当current没有指向None 并且 未找到节点
            if current.getData() == item:         # 如果current当前指向的节点是寻找的节点
                found = True                        # 找到
            else:                                 # 否则
                current = current.getNext()         # 指向标识向后移动 
        return found
    def remove(self, item):                 # 从链表中移除节点
        current = self.head                   # 引入current指向标识指向第一个节点
        previous = None                       # 引入previous指向标识指向current的上一个节点 所以当current指向第一个节点时 previous初始化指向的是None
        found = False                         # 引入寻找状态标识 寻找需要移除的节点
        while not found:                      # 遍历节点 以找到为循环结束条件
            if current.getData() == item:       # 如果当前节点是目标节点
                found = True                      # 找到
            else:                               # 当前节点不是目标节点
                previous = current                # previous指向当前节点
                current = current.getNext()       # current指向移动到下一个节点
                if current == None:               # 如果到最后都没找到目标节点
                    return found	 
                                              # 搜索过程结束
        if previous == None:                  # 如果previous目前指向的是None 代表current指向的是链表的第一个节点 也就是说删除的目标节点就是第一个节点
            self.head = current.getnext()        # 链表头直接指向None表示删除第一个节点
        else:                                 # 其他情况下
            previous.setNext(current.getNext())  #  当前节点的上一个节点指向当前节点的下一个节点

无注释版：

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newdata):
        self.data = newdata
    def setNext(self, newnext):
        self.next = newnext

class LinkList:
    def __init__(self):
        self.head = None
    def isEmpty(self):
        return self.head == None
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
				if current == None:
					return found
        if previous == None:
            self.head = current.getnext()
        else:
            previous.setNext(current.getNext())

代码运行结果如下图：