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 语言 (静态，需指定大小)：

Python (动态，随用随取)：

2.链表在python中是什么

Python 的标准库中没有原生的链表类型。

如果你需要使用链表，通常有两种选择：自己用 Class 实现，或者在特定场景下用 collections.deque（双向队列，底层是双向链表）来“模拟”链表的功能。

C语言的链表：

首先需要一个结构体，里面包含数据和指向下一个节点的指针：

下一步要编写核心操作函数，比如“头插法”。代码详见后面示例。

如果在 Python 中需要链表，通常的做法是：

A. 手动实现 (学习/面试常用)

B. 使用 collections.deque (实际开发常用)

如果你需要的是链表那种“在头尾快速插入删除”的特性，Python 提供了 deque (双端队列)，它的底层是用双向链表实现的。

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语言不用指针和手动分配/释放内存，这对于程序员来说是大大简化了编程难度。

让我们保持学习热情，多做练习。我们下期再见！