当前位置： 首页 > article >正文

Python 数据结构 4.单向链表

article 2025/3/3 6:21:44

惟愿春日不迟，相逢终有时

                                            —— 25.3.2

一、单向链表的基本概念

1.单向链表的概念

        对于顺序存储的结构，最大的缺点就是：插入 和 删除 的时候需要移动大量的元素，所以基于前人的智慧，他们发明了链表。

        链表是由一个个结点组成，每个结点之间通过链接关系串联起来，每个结点都有一个后继结点，最后一个结点的后继结点为空结点，如图所示：

        由链接关系 A ->B 组织起来的两个结点，B 被称为 A的后继结点，A 被称为 B 的前驱结点。链表分为：单向链表、双向链表、循环链表等等。

        一个链表结点由两部分组成：数据域 和 指针域。数据可以是任意类型，由编码的人自行指定。指针域 指向 后继结点 的地址。一个结点包含的两部分，如下图所示：

2.单向链表的元素插入

        单向链表的元素插入，就是指给定一个索引 i 和一个元素 data，生成一个值为 data 的结点，并且插入到第i个位置上。

元素插入的步骤

第1步：判断插入位置是否合法，如果不合法则抛出异常（比如:原本只有5个元素，给定的索引是100，那显然这个位置是不合法的）

第2步：对给定的元素，生成一个链表结点。

第3步：如果插入位置是 0，则直接把生成的结点的后继结点，设置为当前的链表头结点，并且把生成的结点设置为新的链表头，

第4步：如果插入位置不是 0，则遍历到插入位置的前一个位置，把生成的结点插入进来

第5步：更新链表的大小，即对链表的元素执行加一操作。

3.单向链表的元素删除

        单向链表的元素删除，就是指给定一个索引 i，将从链表头开始数到的第 i 个结点删除。

元素删除的步骤

第1步：判断删除位置是否合法，如果不合法则抛出异常。

第2步：如果删除位置为首个结点，直接把链表头更新为它的后继结点，

第3步：如果删除位置非首个结点，则遍历到要删除位置的前一个结点，并且把前一个结点的后继结点设置为它后继的后继。

第4步：更新链表的大小，也就是将链表的大小执行减一操作。

4.单向链表的元素查找

        单向链表的元素查找，是指在链表中查找指定元素 x 是否存在，如果存在则返回该结点，否则返回 null。由于需要遍历整个链表进行元素对比，所以查找的时间复杂度为 (n)。

元素查找的步骤

第1步：遍历整个链表，对链表中的每个元素，和指定元素进行比较，如果相等则返回当前遍历到的结点;

第2步：如果遍历完整个链表，都没有找到相等的元素，则返回 NULL;

5.单向链表的元素索引

        单向链表的元素索引，是指给定一个索引值 i，从链表头结点开始数，数到第 i 个结点并且返回它，时间复杂度 O(n)。

元素索引的步骤

第1步：首先判断给定的索引是否合法，不合法就抛出异常

第2步：直接通过索引访问即可获得对应的元素;

6.单向链表的元素修改

        单向链表的元素修改是指将链表中指定索引的元素更新为新的值。

元素修改的步骤

第1步：直接通过索引访问即可获得对应的结点，修改成指定的值;

二、Python中的单向链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.len = 0

    def size(self):
        return self.len

    def insert(self, pos, val):
        if pos < 0 or pos > self.len:
            raise ValueError("index out of range")
        new_node = ListNode(val)

        if pos == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            prev = self.head
            for _ in range(pos - 1):
                prev = prev.next
            new_node.next = prev.next
            prev.next = new_node
        self.len += 1

    def delete(self, pos):
        if pos < 0 or pos >= self.size():
            raise ValueError("index out of range")

        if pos == 0:
            self.head = self.head.next
        else:
            prev = self.head
            for _ in range(pos - 1):
                prev = prev.next
            prev.next = prev.next.next
        self.len -= 1

    def update(self, pos, val):
        if pos < 0 or pos >= self.size():
            raise ValueError("index out of range")

        curr = self.head
        for _ in range(pos):
            curr = curr.next
        curr.val = val

    def search(self, val):
        curr = self.head
        while curr:
            if curr.val == val:
                return curr
            curr = curr.next
        return None

    def index(self, val):
        index = 0
        curr = self.head
        while curr:
            if curr.val == val:
                return index
            curr = curr.next
            index += 1
        return -1

    def print(self):
        curr = self.head
        while curr:
            print(curr.val, end=" -> ")
            curr = curr.next
        print(None)

def Test():
    list = LinkedList()
    list.insert(0, 1)
    list.print()
    list.insert(1, 1)
    list.print()
    list.insert(2, 4)
    list.print()
    list.insert(0, 1)
    list.print()
    list.insert(1, 1)
    list.print()
    list.insert(2, 4)
    list.print()
    list.update(2, 5)
    list.print()
    list.delete(2)
    list.print()
    list.insert(2, 4)
    list.print()
    list.update(4, 1)
    list.print()

    node = list.search(4)
    if node:
        print("Node found:", node.val)
    else:
        print("Node not found")

    x = list.index(4)
    print("Index of 4:", x)

    x = list.index(5)
    print("Index of 5:", x)

Test()

三、单向链表实战

1.面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

快慢指针法

思路与算法

① 初始化两个指针：fast 和 slow，它们都指向链表的头节点 head。

② 移动快指针：让 fast 指针先向前移动 k 步。

③ 同步移动快慢指针：当 fast 指针移动到链表的末尾时，slow 指针正好指向倒数第 k 个节点。

④ 返回结果：返回 slow 指针所指向节点的值。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def kthToLast(self, head: Optional[ListNode], k: int) -> int:
        fast = head
        slow = head
        while k > 0:
            fast = fast.next
            k -= 1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow.val

2.83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列 

方法一 双指针判断

思路与算法

① 初始化指针：curr 指针从链表的头节点 head 开始。prev 指针初始化为 None，用于记录当前节点的前一个节点。

② 遍历链表：外层 while 循环用于遍历整个链表，直到 curr 为 None。内层 while 循环用于处理当前节点 curr 与前一个节点 prev 值相同的情况。如果发现重复，则将 prev.next 指向 curr.next，从而跳过重复的节点。

③ 更新指针：如果没有发现重复，则更新 prev 为当前节点 curr，并将 curr 移动到下一个节点。​

④ 返回结果：最终返回处理后的链表头节点 head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr:
            while prev != None and curr.val == prev.val:
                prev.next = curr.next
                curr = prev.next
                if curr == None:
                    break
            if curr == None:
                break
            prev = curr
            curr = curr.next
        return head

方法二 一次遍历进行判断

思路与算法

① ​初始化：curr指针指向链表的头节点head。

② 空链表处理：如果链表为空（curr == None），直接返回head。

​③ 遍历链表：如果当前节点的值curr.val与下一个节点的值curr.next.val相同，则通过curr.next = curr.next.next删除下一个节点。如果值不相同，则移动curr指针到下一个节点。

④ 返回结果：最终返回处理后的链表头节点head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        if curr == None:
            return head
        while curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next
        return head

3.面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1：

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

示例2：

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

提示：

  1. 链表长度在[0, 20000]范围内。
  2. 链表元素在[0, 20000]范围内。

方法一、哈希表标记法

思路与算法

① 哈希表标记法​：利用数组模拟哈希表（大小20001），用于记录节点值是否已存在。数组下标对应节点值，元素值为1表示该值已出现过

② 双指针遍历：

        tmp指针：指向当前已去重链表的尾节点，用于连接新节点。

   curr指针：遍历原链表，检查当前节点是否重复。

③ 边界处理：​若链表为空直接返回；初始化时先将头节点加入哈希表，避免后续判空操作

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeDuplicateNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return None
        # 哈希表
        hash = [0 for i in range(20001)]
        tmp = head
        curr = head.next
        hash[head.val] = 1
        while curr:
            if hash[curr.val] == 0:
                hash[curr.val] = 1
                tmp.next = curr
                tmp = tmp.next
            curr = curr.next
        tmp.next = None
        return head

方法二、字典

思路与算法

① ​初始化字典：首先，代码创建了一个空字典 dict，用于存储已经出现过的节点值。如果链表为空（head == None），则直接返回 None，因为空链表不需要去重。​

② 处理头节点：将头节点的值 head.val 存入字典，表示该值已经出现过。

③ 遍历链表：使用 curr 指针遍历链表，初始时 curr 指向头节点。在遍历过程中，检查 curr.next 的值是否已经存在于字典中：如果 curr.next.val 不在字典中，说明该值尚未出现过，将其存入字典，并将 curr 指针移动到下一个节点。如果 curr.next.val 已经在字典中，说明该值是重复的，跳过该节点，即将 curr.next 指向 curr.next.next，从而删除重复节点。

④ 返回结果：遍历结束后，返回去重后的链表头节点 head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeDuplicateNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dict = {}
        if head == None:
            return None
        dict[head.val] = 1
        curr = head
        while curr.next:
            if curr.next.val not in dict:
                dict[curr.next.val] = 1
                curr = curr.next
            else:
                curr.next = curr.next.next  
        return head

四、单向链表的应用

链表相比于顺序表的优点在于：对于给定的结点，删除操作优于顺序表

MMO游戏开发 —— AOI（Area of Interest）

简单来说，每个玩家只关心他周围的玩家的数据同步，而不关心整个世界的数据，有一种经典的实现方式：双向十字链表

所有玩家被串联在一个十字链表上，玩家移动其实就是链表上节点交换位置的过程，每个玩家想获取其他玩家的数据，只需要在十字链表上进行遍历即可，而服务器同步给客户端的数据，受AOI控制，所以可以根据客户端实际能够承受的性能，调整AOI的半径

通过有效的实现AOI技术，游戏开发中可以：

① 减少服务器负载 ② 降低网络延迟 ③ 提升游戏性能 ④ 增强玩家用户体验

 


http://www.kler.cn/a/568378.html

相关文章：

  • PHP：IDEA开发工具配置XDebug，断点调试
  • Android Coil3配置Application单例ImageLoader，Kotlin
  • upload
  • python流水线自动化项目教程
  • 从零开始开发纯血鸿蒙应用之语音朗读
  • Python核心技术，Django学习基础入门教程（附环境安装包）
  • 国自然面上项目｜基于多模态MR影像的胶质母细胞瘤高危区域定位及预后预测研究｜基金申请·25-02-28
  • LINUX基础 - 网络基础 [一]
  • 【ComfyUI】[进阶工作流] 高级采样器与Refiner的工作流优化
  • 6.6.5 SQL访问控制
  • 鸿蒙启动页开发
  • 【音视频】SIP（推流中涉及SIP信息分析）
  • 【软路由】ImmortalWrt 编译指南：从入门到精通
  • SQL Server 视图的更新排查及清除缓存
  • agent实现路径规划
  • ZYNQ-PL实践课堂（三）IP核之MMCM/PLL
  • 想学大模型，但分不清longchain，huggingface，ollama各种工具之间区别？
  • 机器学习的三个基本要素
  • 每天一个Flutter开发小项目 (9) : Flutter状态管理进阶 - Provider构建你的简易购物车应用
  • go如何排查某个依赖是哪里引入的