【大模型2609·数据结构算法·03】离散指针进阶：单向链表CRUD与内存设计实战

专栏导读：突破物理连续内存的物理边界。本篇深入单向链表的分散式节点架构与指针引用模型，全面实现头插、尾插、指定索引插入/删除等核心操作，并通过严谨的指针穿针引线逻辑杜绝内存悬挂与空指针异常，附赠完整可运行的手写链表源码。

链表

链表的概述

链表（Linked List）是一个线性结构，由一系列节点（Node）组成，每个节点包含一个数据元素和一个指向下一节点的指针（Pointer）。所有节点通过指针相连，形成一个链式结构。通常我们将链表中的第一个节点称为头结点，并将头结点的位置作为整个链表的位置标识。与数组不同，链表中每个节点分散的存储在内存中，每个节点都保存了当前节点的数据和下一节点的地址（指针）。

image7.png

由于链表中节点通过指针相连，插入和删除节点只需要修改指针的指向即可，而不需要像数组那样移动数据。且链表不需要像数组那样预先指定大小，而是可以随时动态的增长或缩小。由于链表使用分散存储的方式，因而无需使用大段连续的内存空间。

由于链表中的节点不是连续存储的，无法像数组一样根据索引直接计算出每个节点的地址。必须从头节点开始遍历链表，直到找到目标节点，这导致了链表的随机访问效率较低。链表的每个节点都需要存储指向下一个节点的指针，这会占用额外的存储空间。相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。

常见的链表包括三种：

单向链表：单向链表的节点包含值和指向下一节点的引用。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。

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

双向链表：双向链表记录了两个方向的引用，同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用。

链表的功能定义

方法 说明
size() 返回链表中元素个数
is_empty() 判断链表是否为空
insert(index, item) 在指定位置插入元素
append(item) 在末尾插入元素
remove(index) 删除指定位置的元素
set(index, item) 修改指定位置的元素
get(index) 获取指定位置的元素
find(item) 查找链表中某个元素的位置
for_each(func) 遍历链表

链表的创建

实现一个单向链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        """初始化链表"""
        self.__head = None
        self.__size = 0

    def __str__(self):
        """打印链表"""
        result = []
        current = self.__head
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result)

    @property
    def size(self):
        """获取链表元素个数"""
        return self.__size

    def is_empty(self):
        """判断链表是否为空"""
        return self.__size == 0

插入元素

image8.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def insert(self, index, item):
    """插入元素"""
    if index < 0 or index > self.__size:
        raise IndexError
    if index == 0:
        # 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
        self.__head = Node(item, self.__head)
    else:
        # 插入到中间，先找到index-1位置的节点
        node = self.__head
        for i in range(index - 1):
            node = node.next
        # 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
        node.next = Node(item, node.next)
    self.__size += 1

在末尾插入元素时，使用insert()并将index设置为链表长度。

1
2
3
def append(self, item):
    """末尾插入元素"""
    self.insert(self.__size, item)

删除元素

image9.png

1
2
3
4
5
6
7
8
9
10
11
12
13
def remove(self, index):
    """删除元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    if index == 0:
        self.__head = self.__head.next
    else:
        # 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
        node = self.__head
        for i in range(index - 1):
            node = node.next
        node.next = node.next.next
    self.__size -= 1

修改元素

1
2
3
4
5
6
7
8
def set(self, index, item):
    """修改元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    node = self.__head
    for i in range(index):
        node = node.next
    node.data = item

访问元素

1
2
3
4
5
6
7
8
def get(self, index):
    """访问元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    node = self.__head
    for i in range(index):
        node = node.next
    return node.data

查找元素

1
2
3
4
5
6
7
8
def find(self, item):
    """查找元素"""
    node = self.__head
    while node:
        if node.data == item:
            return True
        node = node.next
    return False

遍历链表

1
2
3
4
5
6
def for_each(self, func):
    """遍历链表"""
    node = self.__head
    while node:
        func(node)
        node = node.next

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        """初始化链表"""
        self.__head = None
        self.__size = 0

    def __str__(self):
        """打印链表"""
        result = []
        current = self.__head
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result)

    @property
    def size(self):
        """获取链表元素个数"""
        return self.__size

    def is_empty(self):
        """判断链表是否为空"""
        return self.__size == 0

    def insert(self, index, item):
        """插入元素"""
        if index < 0 or index > self.__size:
            raise IndexError
        if index == 0:
            # 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
            self.__head = Node(item, self.__head)
        else:
            # 插入到中间，先找到index-1位置的节点
            node = self.__head
            for i in range(index - 1):
                node = node.next
            # 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
            node.next = Node(item, node.next)
        self.__size += 1

    def append(self, item):
        """末尾插入元素"""
        self.insert(self.__size, item)

    def remove(self, index):
        """删除元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        if index == 0:
            self.__head = self.__head.next
        else:
            # 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
            node = self.__head
            for i in range(index - 1):
                node = node.next
            node.next = node.next.next
        self.__size -= 1

    def set(self, index, item):
        """修改元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        node = self.__head
        for i in range(index):
            node = node.next
        node.data = item

    def get(self, index):
        """访问元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        node = self.__head
        for i in range(index):
            node = node.next
        return node.data

    def find(self, item):
        """查找元素"""
        node = self.__head
        while node:
            if node.data == item:
                return True
            node = node.next
        return False

    def for_each(self, func):
        """遍历链表"""
        node = self.__head
        while node:
            func(node)
            node = node.next