下载掌阅APP，畅读海量书库
立即打开
这一节笔者将教导读者使用Python建立链表指标及遍历链表。
想要建立链表，首先要建立此链表的 节点 ，我们可以使用下列 Node 类别建立此节点。
Node类别有2个属性，其中data是存储节点数据，next是存储指标，此指标未来可指向下一个节点，在尚未设定前我们可以使用None。
程序实例ch3_1.py： 建立一个含3个节点的链表，然后打印此链表。
执行结果
上述执行第8～10行后，可以在内存内建立下列3个节点。
执行第11行后链表节点内容如下：
执行第12行后链表节点内容如下：
执行第13行后会多一个指标ptr：
第14～16行可以打印此链表，得到5、15、25。
其实前一节笔者已经用实例讲解了建立链表的方式，也说明了遍历链表，这一节主要讲解建立一个链表 Linked_list 类别，在这个类别内我们使用__init__（ ）设计链表的第一个节点，同时使用print_list（ ）打印链表。
程序实例ch3_2.py： 以建立Linked_list类别方式重新设计ch3_1.py。
执行结果 与ch3_1.py相同。
在链表的应用中，常常需要插入新的节点数据，这一节重点是将新节点插入链表的第一个节点之前，也就是插在链表开头的位置。
程序实例ch3_3.py： 扩充ch3_2.py，新建数据是100的节点，同时将100插入链表开头的位置。
执行结果
上述程序第34行是调用begining（ ）方法，同时传递新节点值100，当执行第22行后，链表节点内容如下：
当执行第23行后，链表节点内容如下：
当执行第24行后，链表节点内容如下：
程序实例ch3_4.py： 在链表的末端插入新的节点。
执行结果
对于在链表末端插入节点，程序在第20～29行使用了ending（ ）方法，当执行第26行后，链表节点内容如下：
当执行第27～28行后，链表节点内容如下：
当执行第29行后，链表节点内容如下：
程序实例ch3_5.py： 在链表n2节点的后面插入新的节点。
执行结果
对于在链表中间插入节点，程序在第20～28行使用了between（ ）方法，调用这个方法需要使用2个参数，第1个参数pre_node是指出要将新数据插入哪一个节点，第2个参数是新节点的值，当执行第26行后，链表节点内容如下：
当执行第27行后，链表节点内容如下：
当执行第28行后，链表节点内容如下：
程序实例ch3_6.py： 在链表中删除指定的节点前，先建立链表，此链表含有5、15、25这3个节点，然后删除15这个节点。
执行结果
上述程序第33行是建立暂时指标ptr，指向链表的第一个节点，第41～42行是建立暂时指标的前一个指标prev，未来找到删除节点时（ptr所指的节点），prev.next指向ptr.next，这样就算是删除暂时指标ptr所指的节点了，可以参考第45行。第43～44行主要是用在找不到指定节点时，可以直接返回。
如果想要建立循环链表，只要将链表末端节点指向第1个节点即可。
程序实例ch3_7.py： 建立循环链表，此列表有3个节点，打印6次。
执行结果
上述执行第12行后链表节点如下所示：
上述执行第13行后链表节点如下所示：
这样就完成了循环链表。
如果要建立双向链表，每个节点必须有向前指标和向后指标，可以使用下列方式定义此节点。
程序实例ch3_8.py： 建立双向链表，在建立节点过程中，每次均从头部打印一次双向链表，最后从尾部打印一次双向链表。
执行结果
这个程序第15～27行使用了add_double_list（ ）方法，将每个节点加入链表，第17行主要是确定所增加的数据是双向链表的节点，再执行18～26行。其中19～22行是增加第一个节点，当执行完第19行，链表节点内容如下：
当执行完第20行，链表节点内容如下：
当执行完第21行，链表节点内容如下：
当执行完第22行，链表节点内容如下：
上述就是建立双向链表的第一个节点过程。程序第24～26行是建立双向链表第2个（含）以后的节点过程，当执行完第24行，链表节点内容如下：
当执行完第25行，链表节点内容如下：
当执行完第26行，链表节点内容如下：
程序第29～34行的print_list_from_head（ ）是从双向链表 前端打印到末端 ，程序第36～41行的print_list_from_tail（ ）是从双向链表 末端打印到前端 。