链表的基本结构

概念： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 简单来讲，链表由一个个独立的节点组成，以单向链表为例，每个节点的数据结构都是类似的：

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

其中最重要的是next节点，该节点指向的是与当前节点相连的下一个节点的地址。例如当前节点currentNode地址是0x11ff44，下一个节点的地址是0x12ff44，那么currentNode.next的值就是0x12ff44。

链表的基本结构

在实际应用过程中，根据数据结构的不同，链表的种类可以有很多。 1. 单向链表 单向链表就是节点的.next只指向链表中的下一个节点。 2. 双向链表 在双向链表中，除了子节点一般还存在其父节点，就是说一个双向链表节点中会存两个地址，通常的表示方法是：.parent和.children，表示父节点和子节点。 3. 循环链表 循环链表主要的特点是，最后一个节点的子节点指向第一个节点 此外，还会有一些链表会专门有一个HeadNode，由此还可以分出带头的和不带头的链表。一般带头节点的作用是作为链表的虚拟启动节点，因为头节点的数据结构和主干节点的数据结构通常不一样，用一个虚拟节点可以使得对链表主干数据进行处理的时候可以不需要进行额外的判断。

链表的功能函数

申请结点

申请结点是所有链表操作的基础，本质就是创建一个新的节点对象，并对其初始化。在Python中，我们可以通过类的实例化来完成节点的申请。

class LinkNode:
    def __init__(self, value):
        self.value = value
        self.next = None
'''
申请一个新节点
'''
new_node = LinkNode(10)

申请完成后，新节点的value被赋值为传入的数据，next默认指向None，表示该节点暂时没有后继节点。

注意： 在C/C++等语言中，节点通常通过malloc从堆上动态申请；在Python中则由解释器自动管理内存分配，底层同样是在堆上分配空间。

插入结点

1. 头插 头插法是指将新节点插入到链表的头部，使其成为新的第一个节点（即头节点之后第一个有效节点）。 以带头节点的单向链表为例：

def head_insert(head, value):
    """
    头插法：将新节点插入到头节点之后
    :param head: 头节点（虚拟节点）
    :param value: 新节点的值
    """
    new_node = LinkNode(value)
    '''
    新节点的next指向原头节点的下一个节点
    '''
    new_node.next = head.next
    '''
    头节点的next指向新节点
    '''
    head.next = new_node

图解：

插入前：Head -> A -> B -> None
插入C：Head -> C -> A -> B -> None

关键点： 必须先让新节点的next指向原第一个节点，再让头节点的next指向新节点。顺序不能反，否则原链表的第一个节点会丢失。

2. 尾插 尾插法是指将新节点插入到链表的末尾，使其成为最后一个节点。

def tail_insert(head, value):
    """
    尾插法：将新节点插入到链表末尾
    :param head: 头节点（虚拟节点）
    :param value: 新节点的值
    """
    new_node = LinkNode(value)
    '''
    遍历到链表的最后一个节点
    '''
    cur = head
    while cur.next is not None:
        cur = cur.next
    '''
    将最后一个节点的next指向新节点
    '''
    cur.next = new_node

图解：

插入前：Head -> A -> B -> None
插入C：Head -> A -> B -> C -> None

关键点： 尾插需要遍历整个链表找到最后一个节点，时间复杂度为O(n)。如果频繁进行尾插操作，可以额外维护一个tail尾指针，将时间复杂度降为O(1)。

3. 中间插入 中间插入是指在链表的指定位置（某个节点之后）插入新节点。

def insert_after(node, value):
    """
    在指定节点之后插入新节点
    :param node: 指定节点（在该节点之后插入）
    :param value: 新节点的值
    """
    if node is None:
        print("指定节点不存在，无法插入")
        return
    new_node = LinkNode(value)
    '''
    新节点的next指向指定节点的下一个节点
    '''
    new_node.next = node.next
    '''
    指定节点的next指向新节点
    '''
    node.next = new_node

图解：

插入前：Head -> A -> B -> C -> None
在A后插入X：Head -> A -> X -> B -> C -> None

关键点： 与头插类似，同样需要先处理新节点的next指针，再修改前驱节点的next指针，避免链表断裂。

删除结点

1. 头删 头删法是指删除链表中第一个有效节点（头节点之后的那个节点）。

def head_delete(head):
    """
    头删法：删除链表第一个有效节点
    :param head: 头节点（虚拟节点）
    :return: 被删除节点的值
    """
    if head.next is None:
        print("链表为空，无法删除")
        return None
    '''
    保存被删除节点
    '''
    del_node = head.next
    '''
    头节点的next跳过被删除节点，指向被删除节点的下一个节点
    '''
    head.next = del_node.next
    '''
    释放被删除节点的next指针
    '''
    del_node.next = None
    return del_node.value

图解：

删除前：Head -> A -> B -> C -> None
删除A：Head -> B -> C -> None

关键点： 使用虚拟头节点的好处在这里体现得淋漓尽致——不需要对"删除第一个节点"做特殊处理，逻辑与删除中间节点完全一致。

2. 尾删 尾删法是指删除链表的最后一个节点。

def tail_delete(head):
    """
    尾删法：删除链表最后一个节点
    :param head: 头节点（虚拟节点）
    :return: 被删除节点的值
    """
    if head.next is None:
        print("链表为空，无法删除")
        return None
    '''
    遍历到倒数第二个节点
    '''
    cur = head
    while cur.next.next is not None:
        cur = cur.next
    '''
    保存被删除节点
    '''
    del_node = cur.next
    '''
    倒数第二个节点的next置为None
    '''
    cur.next = None
    return del_node.value

图解：

删除前：Head -> A -> B -> C -> None
删除C：Head -> A -> B -> None

关键点： 尾删需要找到倒数第二个节点，因此需要遍历到cur.next.next is None的位置。时间复杂度为O(n)。

3. 中间删除 中间删除是指删除链表中指定的某个节点。

def delete_node(head, value):
    """
    删除链表中值为value的第一个节点
    :param head: 头节点（虚拟节点）
    :param value: 要删除节点的值
    :return: 是否删除成功
    """
    cur = head
    '''
    遍历链表，找到目标节点的前驱节点
    '''
    while cur.next is not None:
        if cur.next.value == value:
            '''
            保存被删除节点
            '''
            del_node = cur.next
            '''
            前驱节点的next跳过被删除节点
            '''
            cur.next = del_node.next
            '''
            释放被删除节点的next指针
            '''
            del_node.next = None
            return True
        cur = cur.next
    print(f"未找到值为 {value} 的节点")
    return False

图解：

删除前：Head -> A -> B -> C -> None
删除B：Head -> A -> C -> None

关键点： 单向链表的删除需要找到被删除节点的前驱节点，因为单向链表的节点只有next指针，无法直接回溯到前一个节点。这也是双向链表存在的意义之一——双向链表可以直接通过.parent找到前驱节点，删除操作更加高效。

完整示例

下面用一个完整的示例来演示上述所有操作：

class LinkNode:
    def __init__(self, value):
        self.value = value
        self.next = None
class LinkedList:
    def __init__(self):
        '''
        创建虚拟头节点
        '''
        self.head = LinkNode(None)
    def head_insert(self, value):
        """头插"""
        new_node = LinkNode(value)
        new_node.next = self.head.next
        self.head.next = new_node
    def tail_insert(self, value):
        """尾插"""
        new_node = LinkNode(value)
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = new_node
    def insert_after(self, target_value, value):
        """在指定值节点后插入"""
        cur = self.head.next
        while cur is not None:
            if cur.value == target_value:
                new_node = LinkNode(value)
                new_node.next = cur.next
                cur.next = new_node
                return True
            cur = cur.next
        return False
    def head_delete(self):
        """头删"""
        if self.head.next is None:
            return None
        del_node = self.head.next
        self.head.next = del_node.next
        del_node.next = None
        return del_node.value
    def tail_delete(self):
        """尾删"""
        if self.head.next is None:
            return None
        cur = self.head
        while cur.next.next is not None:
            cur = cur.next
        del_node = cur.next
        cur.next = None
        return del_node.value
    def delete_node(self, value):
        """删除指定值节点"""
        cur = self.head
        while cur.next is not None:
            if cur.next.value == value:
                del_node = cur.next
                cur.next = del_node.next
                del_node.next = None
                return True
            cur = cur.next
        return False
    def print_list(self):
        """打印链表"""
        cur = self.head.next
        elements = []
        while cur is not None:
            elements.append(str(cur.value))
            cur = cur.next
        print(" -> ".join(elements) + " -> None")
if __name__ == '__main__':
    ll = LinkedList()
    '''
    尾插 1, 2, 3
    '''
    ll.tail_insert(1)
    ll.tail_insert(2)
    ll.tail_insert(3)
    print("尾插 1,2,3 后：")
    ll.print_list()
    '''
    预期输出: 1 -> 2 -> 3 -> None
    '''
    
    '''
    头插 0
    '''
    ll.head_insert(0)
    print("头插 0 后：")
    ll.print_list()
    '''
    预期输出: 0 -> 1 -> 2 -> 3 -> None
    '''
    '''
    在值为2的节点后插入5
    '''
    ll.insert_after(2, 5)
    print("在2后插入5：")
    ll.print_list()
    '''
    预期输出: 0 -> 1 -> 2 -> 5 -> 3 -> None
    '''
    print(f"头删，删除了：{ll.head_delete()}")
    ll.print_list()
    '''
    预期输出: 1 -> 2 -> 5 -> 3 -> None
    '''
    '''
    尾删
    '''
    print(f"尾删，删除了：{ll.tail_delete()}")
    ll.print_list()
    '''
    预期输出: 1 -> 2 -> 5 -> None
    '''
    '''
    删除值为2的节点
    '''
    ll.delete_node(2)
    print("删除值为2的节点后：")
    ll.print_list()
    '''
    预期输出: 1 -> 5 -> None
    '''

运行结果：

尾插 1,2,3 后：
1 -> 2 -> 3 -> None
头插 0 后：
0 -> 1 -> 2 -> 3 -> None
在2后插入5：
0 -> 1 -> 2 -> 5 -> 3 -> None
头删，删除了：0
1 -> 2 -> 5 -> 3 -> None
尾删，删除了：3
1 -> 2 -> 5 -> None
删除值为2的节点后：
1 -> 5 -> None

一些注意点

注意：

1. 链式结构在逻辑上是连续的，但在物理上不一定连续。就是说在内存空间中，当前节点的地址和其子节点的地址不一定是相邻的两个数。
2. 现实中的节点一般都是从堆上申请出来的。
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。在应用链表结构的时候，链表节点的数据结构中除了存储父子节点的变量结构一般不会变化，其他的都可以根据实际需要来变化。例如在存储机器人运动轨迹的点位的时候，数据节点就可以用下面的这种形式来表示：

class Position:
    def __init__(self, x, y, z):
        self.X = x
        self.Y = y
        self.Z = z
        self.next = None

总结