Python学习
一、学前花絮
数据结构是所有的计算机语言中非常重要的一部分，上篇文章专门讲述了“栈”的实现和用途。分别用C语言和python实现“栈”的后进先出的功能。今天我们继续数据结构部分的学习，重点讲述一下数组和链表，也以C语言和python进行对比。
二、Python和C语言如何实现“线性数据结构”的数组和链表
2.1 线性数据结构的数组和链表介绍
数组（Array）和链表（Linked List）是计算机科学中最基础、最核心的线性数据结构。理解它们的差异，就像是理解“火车”和“一列并排的房间”的区别一样。
简单来说，数组讲究“整齐划一”，而链表讲究“灵活连接”。为了更直观地理解，下面有一个核心对比表，随后详细拆解它们的优缺点和适用场景。
1. 数组 (Array)：整齐的“一排房间”
核心原理：
想象一下酒店的一层楼，房间号是 0, 1, 2, 3... 这些房间在物理上是挨在一起的。数组就是这样，它在内存中占据一段连续的空间。因为这种连续性，我们可以通过“首地址 + 偏移量”直接计算出任意元素的位置。
优点：
l随机访问（Random Access）： 这是数组最大的杀手锏。如果你知道元素的下标（比如第 5 个元素），你可以瞬间找到它，时间复杂度是 O(1)。
l缓存友好： 由于内存连续，CPU 预取数据时命中率很高，遍历数组的速度通常非常快。
l空间利用率高： 只需要存储数据本身，不需要额外的指针信息。
缺点：
l大小固定： 传统数组一旦定义，大小就无法改变（虽然现代语言如 Python 列表、Java ArrayList 提供了动态扩容，但这其实是通过申请新空间、拷贝旧数据实现的，会有性能损耗）。
l插入/删除低效： 如果你想在中间插入一个新元素，后面所有的元素都要向后“挪一步”；删除时则都要向前“补位”。这非常耗时，时间复杂度是 O(n)。
适用场景：
l需要频繁根据下标查询数据（如：矩阵运算、图像处理）。
l数据量大小已知且变动不大的情况。
2. 链表 (Linked List)：灵活的“火车”
核心原理：
想象一列火车，车头连着车厢1，车厢1连着车厢2... 这些车厢在物理位置上不一定挨着，它们通过“挂钩”（指针）连接起来。链表的每个节点包含两部分：数据域（存数据）和指针域（存下一个节点的地址）。
常见变体：
单向链表： 只能从头走到尾。
双向链表： 每个节点有两个指针，既能指向前一个，也能指向后一个，方便来回移动。
循环链表： 尾巴连回了头，形成一个环。
优点：
l动态大小： 不需要预先分配内存，想加节点就加节点，想删就删，内存利用率非常灵活。
l插入/删除高效： 只要你找到了目标节点，插入或删除只需要修改相邻节点的“指针”（挂钩），不需要移动数据，时间复杂度是 O(1)。
缺点：
l访问慢： 如果你想找第 1000 个元素，你不能直接跳过去，必须从车头开始，一个一个车厢找过去，时间复杂度是 O(n)。
l额外空间开销： 每个节点都要额外存储指针信息，如果数据本身很小，指针的开销占比就会很大。
l缓存不友好： 节点在内存中是零散分布的，遍历时 CPU 缓存命中率低，实际运行速度可能比数组慢。
适用场景：
l需要频繁在头部或中间插入、删除数据（如：实现栈、队列、LRU 缓存淘汰算法）。
l数据量动态变化且无法预估的情况（如：实时日志记录）。
2.2 以C语言和python语言举例说明数组和链表
1. 数组与列表比较
用过C语言的数组和python的列表的朋友会觉得，二者感觉上是一样的？只能说大体上可以这么认为，但python的list要比C语言的数组功能上丰富很多。
应该说Python 的 list 在使用体验上替代了 C 语言中数组的角色，但从底层实现来看，它其实是一种动态数组（Dynamic Array），而不是 C 语言那种纯粹的静态数组。
数组 vs Python 的 List：
在 C 语言中，数组是“死”的；在 Python 中，List 是“活”的。
代码对比：
C 语言 (静态，需指定大小)：
int arr[5]; // 必须先说好大小是 5 arr[0] = 10; // 赋值 // 如果想加第6个元素？不行！除非重新 malloc 申请内存并拷贝。 |
Python (动态，随用随取)：
my_list = [] 空列表my_list.append(10) # 自动扩容 my_list.append("hello") # 还能存字符串 |
2.链表在python中是什么
Python 的标准库中没有原生的链表类型。
如果你需要使用链表，通常有两种选择：自己用 Class 实现，或者在特定场景下用 collections.deque（双向队列，底层是双向链表）来“模拟”链表的功能。
C语言的链表：
首先需要一个结构体，里面包含数据和指向下一个节点的指针：
#include #include// 必须包含 malloc 和 free // 定义链表节点结构 struct Node { intdata;// 数据域：存储整数 structNode* next;// 指针域：指向下一个节点的地址 }; |
下一步要编写核心操作函数，比如“头插法”。代码详见后面示例。
如果在 Python 中需要链表，通常的做法是：
A. 手动实现 (学习/面试常用)
定义节点class ListNode: definit(self, val=0, next=None): self.val= val self.next= next # 这里的 next 就是引用，相当于 C 的指针 <o:p> # 定义链表 (可以封装插入、删除方法) class LinkedList: definit(self): self.head= None |
B. 使用 collections.deque (实际开发常用)
如果你需要的是链表那种“在头尾快速插入删除”的特性，Python 提供了 deque (双端队列)，它的底层是用双向链表实现的。
from collections import deque dq = deque([1, 2, 3]) dq.appendleft(0) #在头部快速插入 dq.pop() # 在尾部快速弹出 |
C. 为什么 Python 不内置链表？
Guido (Python 之父) 认为，99% 的场景下，动态数组 (List) 的性能已经足够好，且使用起来比链表简单得多。 只有在特定的高性能需求或算法题中，才需要手动处理链表。
一句话总结：
在 Python 中，List 就是你平时干活用的“数组”；而链表通常是为了学习算法、或者在极少数需要极致插入性能时，才需要自己写或者用 deque 的东西。
2.3 示例
1. Python实现链表：
Python 代码说明：
Node 类：模拟了 C 语言中的结构体，包含 data 和 next。
None：相当于 C 语言中的 NULL，表示指针结束。
输出结果：
2.C语言实现链表
C 语言使用 struct 和指针来实现，需要手动管理内存
C 语言代码说明：
struct Node：定义了节点的数据结构。
& (取地址符)：&second 表示获取 second 变量的内存地址，赋值给指针。
-> 操作符：用于通过指针访问结构体成员（current->data 等价于 (*current).data）。
NULL：宏定义，表示空指针。
malloc: 在堆上申请一块内存。作用: 这块内存在函数结束时不会自动消失，可以被程序长期持有，这才是链表动态增长的基础。
如果不调用 free，程序运行期间占用的内存会一直累积，导致内存泄漏。
编译方式：使用 gcc filename.c -o output 编译，然后运行 ./output。
以上程序是 C 语言链表的标准范式：
定义结构体 (struct Node)。
动态申请 (malloc) 内存创建节点。
操作链表 (遍历、插入、删除)。
动态释放 (free) 内存回收资源。
输出结果如下：
我们从输出结果上看，C语言与python语言实现链表功能一样。但是二者还是有很大的区别：
三、小结
通过数据结构“数组和链表”的学习，并以python和C语言实现进行了对比。我们深刻体会到为什么说python语言易学易用，python语言不用指针和手动分配/释放内存，这对于程序员来说是大大简化了编程难度。
让我们保持学习热情，多做练习。我们下期再见！
#python
10个月宝宝每天需要喝多少奶粉？