使用 Python 3 C-API 实现一个单向链表扩展Python 的开发效率很高但在已经通过性能分析确认的热点路径中C 扩展可以减少计算开销。本教程用一个单向链表演示如何通过 Python 3 C-API 创建扩展类型并实现append(value)尾部追加元素len(items)获取元素数量items[index]按下标读取元素支持负索引for value in items独立迭代器Python 对象的正确引用计数与析构。代码地址https://github.com/marskang/python-ext-linklist这是学习 C-API 的示例而非内置list的替代品。链表随机访问需要遍历items[index]的时间复杂度是 O(n)Python 日常业务通常应优先使用内置list。1. 构建与运行需要 Python 3、C 编译器和对应版本的 Python 开发头文件。python3 setup.py build_ext--inplacepython3 test.pybuild_ext --inplace会在当前目录生成与 Python 版本、操作系统和 CPU 架构相关的扩展文件例如linklist.cpython-39-darwin.so。这是构建产物不应提交到 Git项目的.gitignore已忽略所有.so文件。运行示例importlinklist itemslinklist.LinkList()items.append(张三)items.append(12)items.append(666)print(len(items))# 3print(items[1])# 12print(items[-1])# 666print(list(items))# [张三, 12, 666]2. 设计区分 Python 对象和内部 C 节点一个常见误区是让每个链表节点都包含PyObject_HEAD。这会让每个节点都变成 Python 对象不仅增加复杂度也很容易把节点析构和链表析构混在一起。这里分成三种结构typedefstructLinkListItem{PyObject*content;structLinkListItem*next;}LinkListItem;typedefstruct{PyObject_HEAD Py_ssize_t count;LinkListItem*head;LinkListItem*tail;}PyLinkList;typedefstruct{PyObject_HEAD PyLinkList*list;LinkListItem*current;}PyLinkListIter;其中PyLinkList是 Python 中的linklist.LinkList对象因此以PyObject_HEAD开头LinkListItem只是内部 C 节点由PyMem_Malloc分配PyLinkListIter是独立迭代器。它持有链表引用使遍历期间链表不会被提前销毁。3. Python 对象的引用计数C-API 中最重要的规则是明确每个PyObject *的所有权。METH_O方法收到的参数是借用引用不能直接保存。链表追加元素时必须增加引用否则 Python 调用方释放该对象后节点中会留下悬垂指针。staticPyObject*py_link_list_append(PyLinkList*self,PyObject*obj){LinkListItem*itemPyMem_Malloc(sizeof(*item));if(itemNULL){returnPyErr_NoMemory();}Py_INCREF(obj);/* 节点现在拥有 content 的一个引用 */item-contentobj;item-nextNULL;if(self-tailNULL){self-headitem;}else{self-tail-nextitem;}self-tailitem;self-count;Py_RETURN_NONE;}Python 方法必须返回PyObject *成功时返回新引用的Py_None出错时返回NULL且设置异常。不能把返回void的 C 函数强制转换后注册为METH_O。链表销毁时逐个释放节点持有的 Python 对象和 C 内存staticvoidpy_link_list_dealloc(PyLinkList*self){LinkListItem*itemself-head;while(item!NULL){LinkListItem*nextitem-next;Py_XDECREF(item-content);PyMem_Free(item);itemnext;}Py_TYPE(self)-tp_free((PyObject*)self);}析构函数中不能对self再执行Py_DECREF或Py_CLEAR(self)解释器调用tp_dealloc时该对象的引用计数已经降到零。4. 实现长度和下标访问Python 的len(obj)和obj[index]通过序列协议调用。这里仅实现长度和取项staticPySequenceMethods py_link_list_as_sequence{.sq_length(lenfunc)py_link_list_length,.sq_item(ssizeargfunc)py_link_list_item,};sq_item返回给 Python 的对象必须是新引用。下列实现也支持-1这类负索引staticPyObject*py_link_list_item(PyLinkList*self,Py_ssize_t index){LinkListItem*item;if(index0){indexself-count;}if(index0||indexself-count){PyErr_SetString(PyExc_IndexError,link list index out of range);returnNULL;}itemself-head;while(index--0){itemitem-next;}Py_INCREF(item-content);returnitem-content;}len(items)是 O(1)因为链表保存了countitems[index]需要从头遍历因此是 O(n)。5. 实现独立迭代器不要把遍历游标保存到链表对象自身。否则两个iter(items)会共享状态嵌套循环会产生跳项或重复项。每次调用iter(items)创建一个新对象staticPyObject*py_link_list_getiter(PyLinkList*self){PyLinkListIter*iteratorPyObject_New(PyLinkListIter,PyLinkListIterType);if(iteratorNULL){returnNULL;}Py_INCREF(self);iterator-listself;iterator-currentself-head;return(PyObject*)iterator;}迭代器的tp_iternext返回下一个元素的新引用没有元素时返回NULL且不设置异常解释器会将其视为StopIteration。staticPyObject*py_link_list_iter_next(PyLinkListIter*self){LinkListItem*itemself-current;if(itemNULL){returnNULL;}self-currentitem-next;Py_INCREF(item-content);returnitem-content;}迭代器自身在销毁时释放其持有的链表引用staticvoidpy_link_list_iter_dealloc(PyLinkListIter*self){Py_XDECREF(self-list);Py_TYPE(self)-tp_free((PyObject*)self);}6. 注册类型和初始化模块Python 3 的扩展模块入口必须命名为PyInit_模块名并返回PyObject *。这与 Python 2 的init模块名和Py_InitModule3不兼容。本项目先配置两个类型再调用PyType_ReadyPyLinkListType.tp_namelinklist.LinkList;PyLinkListType.tp_basicsizesizeof(PyLinkList);PyLinkListType.tp_dealloc(destructor)py_link_list_dealloc;PyLinkListType.tp_flagsPy_TPFLAGS_DEFAULT;PyLinkListType.tp_as_sequencepy_link_list_as_sequence;PyLinkListType.tp_methodspy_link_list_methods;PyLinkListType.tp_init(initproc)py_link_list_init;PyLinkListType.tp_newPyType_GenericNew;PyLinkListType.tp_iter(getiterfunc)py_link_list_getiter;PyLinkListIterType.tp_namelinklist._LinkListIterator;PyLinkListIterType.tp_basicsizesizeof(PyLinkListIter);PyLinkListIterType.tp_dealloc(destructor)py_link_list_iter_dealloc;PyLinkListIterType.tp_flagsPy_TPFLAGS_DEFAULT;PyLinkListIterType.tp_iterPyObject_SelfIter;PyLinkListIterType.tp_iternext(iternextfunc)py_link_list_iter_next;模块初始化函数如下PyMODINIT_FUNCPyInit_linklist(void){PyObject*module;if(PyType_Ready(PyLinkListType)0||PyType_Ready(PyLinkListIterType)0){returnNULL;}modulePyModule_Create(linklist_module);if(moduleNULL){returnNULL;}Py_INCREF(PyLinkListType);if(PyModule_AddObject(module,LinkList,(PyObject*)PyLinkListType)0){Py_DECREF(PyLinkListType);Py_DECREF(module);returnNULL;}returnmodule;}PyModule_AddObject成功后会接管传入引用因此先对类型对象Py_INCREF失败时则由当前函数负责释放该引用和模块对象。7. 测试重点test.py覆盖了以下行为append、长度、正负索引和越界IndexError两个迭代器分别维护进度链表在外部引用消失后仍持有元素链表销毁后会释放元素引用。修改 C-API 代码后应重新构建并运行测试python3 setup.py build_ext--inplacepython3 test.py总结一个可靠的 Python C 扩展并不只是“把 C 函数暴露给 Python”。需要同时满足 Python 的对象模型正确的函数签名、引用计数、新引用/借用引用约定、异常返回方式、析构逻辑和迭代协议。掌握这些基础后再扩展插入、删除、切片或更复杂的数据结构会更安全。