本文实例讲述了Python实现的数据结构与算法之链表。分享给大家供大家参考。具体分析如下：
一、概述
链表（linked list）是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。
根据结构的不同，链表可以分为单向链表、单向循环链表、双向链表、双向循环链表等。其中，单向链表和单向循环链表的结构如下图所示：
二、ADT
这里只考虑单向循环链表ADT，其他类型的链表ADT大同小异。单向循环链表ADT（抽象数据类型）一般提供以下接口：
① SinCycLinkedlist() 创建单向循环链表
② add(item) 向链表中插入数据项
③ remove(item) 删除链表中的数据项
④ se本文来源gao@!dai!ma.com搞$$代^@码网*arch(item) 在链表中查找数据项是否存在
⑤ empty() 判断链表是否为空
⑥ size() 返回链表中数据项的个数
单向循环链表操作的示意图如下：
三、Python实现
Python的内建类型list底层是由C数组实现的，list在功能上更接近C++的vector（因为可以动态调整数组大小）。我们都知道，数组是连续列表，链表是链接列表，二者在概念和结构上完全不同，因此list不能用于实现链表。
在C/C++中，通常采用“指针+结构体”来实现链表；而在Python中，则可以采用“引用+类”来实现链表。在下面的代码中，SinCycLinkedlist类代表单向循环链表，Node类代表链表中的一个节点：
#!/usr/bin/env python# -*- coding: utf-8 -*-class Node: def __init__(self, initdata): self.__data = initdata self.__next = None def getData(self): return self.__data def getNext(self): return self.__next def setData(self, newdata): self.__data = newdata def setNext(self, newnext): self.__next = newnextclass SinCycLinkedlist: def __init__(self): self.head = Node(None) self.head.setNext(self.head) def add(self, item): temp = Node(item) temp.setNext(self.head.getNext()) self.head.setNext(temp) def remove(self, item): prev = self.head while prev.getNext() != self.head: cur = prev.getNext() if cur.getData() == item: prev.setNext(cur.getNext()) prev = prev.getNext() def search(self, item): cur = self.head.getNext() while cur != self.head: if cur.getData() == item: return True cur = cur.getNext() return False def empty(self): return self.head.getNext() == self.head def size(self): count = 0 cur = self.head.getNext() while cur != self.head: count += 1 cur = cur.getNext() return countif __name__ == '__main__': s = SinCycLinkedlist() print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) s.add(19) s.add(86) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) print('86 is%s in s' % ('' if s.search(86) else ' not',)) print('4 is%s in s' % ('' if s.search(4) else ' not',)) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size())) s.remove(19) print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
运行结果：
$ python sincyclinkedlist.pys.empty() == True, s.size() == 0s.empty() == False, s.size() == 286 is in s4 is not in ss.empty() == False, s.size() == 2s.empty() == False, s.size() == 1
希望本文所述对大家的Python程序设计有所帮助。
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Python实现的数据结构与算法之链表详解
转载请注明原文链接：Python实现的数据结构与算法之链表详解
