3-8　与链表有关的Python程序

这一节笔者将教导读者使用Python建立链表指标及遍历链表。

3-8-1　建立链表

想要建立链表，首先要建立此链表的节点，我们可以使用下列Node类别建立此节点。

Node类别有2个属性，其中data是存储节点数据，next是存储指标，此指标未来可指向下一个节点，在尚未设定前我们可以使用None。

程序实例ch3_1.py：建立一个含3个节点的链表，然后打印此链表。

执行结果

上述执行第8～10行后，可以在内存内建立下列3个节点。

执行第11行后链表节点内容如下：

执行第12行后链表节点内容如下：

执行第13行后会多一个指标ptr：

第14～16行可以打印此链表，得到5、15、25。

3-8-2　建立链表类别和遍历此链表

其实前一节笔者已经用实例讲解了建立链表的方式，也说明了遍历链表，这一节主要讲解建立一个链表Linked_list类别，在这个类别内我们使用__init__（ ）设计链表的第一个节点，同时使用print_list（ ）打印链表。

程序实例ch3_2.py：以建立Linked_list类别方式重新设计ch3_1.py。

执行结果　与ch3_1.py相同。

3-8-3　在链表第一个节点前插入一个新的节点

在链表的应用中，常常需要插入新的节点数据，这一节重点是将新节点插入链表的第一个节点之前，也就是插在链表开头的位置。

程序实例ch3_3.py：扩充ch3_2.py，新建数据是100的节点，同时将100插入链表开头的位置。

执行结果

上述程序第34行是调用begining（ ）方法，同时传递新节点值100，当执行第22行后，链表节点内容如下：

当执行第23行后，链表节点内容如下：

当执行第24行后，链表节点内容如下：

3-8-4　在链表末端插入新的节点

程序实例ch3_4.py：在链表的末端插入新的节点。

执行结果

对于在链表末端插入节点，程序在第20～29行使用了ending（ ）方法，当执行第26行后，链表节点内容如下：

当执行第27～28行后，链表节点内容如下：

当执行第29行后，链表节点内容如下：

3-8-5　在链表中间插入新的节点

程序实例ch3_5.py：在链表n2节点的后面插入新的节点。

执行结果

对于在链表中间插入节点，程序在第20～28行使用了between（ ）方法，调用这个方法需要使用2个参数，第1个参数pre_node是指出要将新数据插入哪一个节点，第2个参数是新节点的值，当执行第26行后，链表节点内容如下：

当执行第27行后，链表节点内容如下：

当执行第28行后，链表节点内容如下：

3-8-6　在链表中删除指定内容的节点

程序实例ch3_6.py：在链表中删除指定的节点前，先建立链表，此链表含有5、15、25这3个节点，然后删除15这个节点。

执行结果

上述程序第33行是建立暂时指标ptr，指向链表的第一个节点，第41～42行是建立暂时指标的前一个指标prev，未来找到删除节点时（ptr所指的节点），prev.next指向ptr.next，这样就算是删除暂时指标ptr所指的节点了，可以参考第45行。第43～44行主要是用在找不到指定节点时，可以直接返回。

3-8-7　建立循环链表

如果想要建立循环链表，只要将链表末端节点指向第1个节点即可。

程序实例ch3_7.py：建立循环链表，此列表有3个节点，打印6次。

执行结果

上述执行第12行后链表节点如下所示：

上述执行第13行后链表节点如下所示：

这样就完成了循环链表。

3-8-8　双向链表

如果要建立双向链表，每个节点必须有向前指标和向后指标，可以使用下列方式定义此节点。

程序实例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（ ）是从双向链表末端打印到前端。