Python 数据结构入门 - 链表（Linked List）
18年9月10日 · Python123 6258 人阅读
 |
什么是链表
链表由结点组成
每个结点包括 数据（value）和一个指向另一个结点的 指针（pointer）
链表的特点
优点
能够快速进行结点的插入、删除与移动操作
不要求数据在内存中连续存放（这也是链表重要特征）
缺点
查找和访问一个数据需要线性时间：访问某个结点必须从链表第一个结点开始，依次寻找下一个结点位置，直到到达目标结点。且无法有效利用 CPU 缓存放大了这一缺点。
浪费内存（特别是在 64 位架构中）
链表的应用
链表通常会在需要动态分配内存的场景下使用，实现一些复杂的数据结构，例如树和图时也会使用到链表。
顺带一提，Python 的 list 不是链表，而是使用动态数组实现的。
动手试一试
（提示：点击交互式代码框右上角绿色三角按钮可运行代码）
定义一个链表结点结构：
创建三个结点：
通过指针链接三个结点：
这样就构成了一个简单的链表 3->6->1
定义一个打印链表的方法，之后你可以使用这个方法查看一个链表：
尝试在 node 1 后插入一个结点 node 4：
删除 node 2：
统计链表有几个结点：
查找链表中有没有某个数据：
掌握了这些操作后，试着实现一个真正的链表：
编码挑战
完成上面定义的 LinkedList 并实现以下功能：
1. 链表反转
定义一个 reverse 方法，将一个3->2->1 的链表转换为 1->2->3 的形式
思考：上面的代码并没有修改原来的链表，如果需要直接反转原来的链表要怎么实现？
2. 链表元素去重
定义一个 removeDuplicates 方法，去除链表中的重复数据
思考：上面的代码也没有修改原来的链表，如果需要直接在原来的链表上去重要怎么实现？
3. 链表加法
定义一个 add 方法，实现两个链表相加，例如：1->2->3 + 4->5 = 321 + 54 = 375
思考：如何实现1->2->3 + 4->5 = 123 + 45 = 168 这样形式的加法？如何实现链表的乘法和减法？除法也能够采用近似的方法实现吗？
扩展：使用链表实现一个高精度运算库，精确计算例如
213874501923412351237501239.87519236 + 23512331.5839205819203213451581236345的值。
Python3Turtle
