1. 首页
  2. web前端

用 python 学习数据结构(一)链表

一、为什么要学习数据结构

python 语言和标准库自带了很多数据结构,比如 list、set、dict、tuple、queue、heapq等,所以很在标准库或者第三方库提供的数据结构够用的情况下,不需要自己再写数据结构。

当然,掌握了数据结构的原理之后,面对大量数据的时候,可以更轻松地选择合适的数据结构,以及在标准数据结构不够用的情况下,可以定制化实现自己的数据结构。

为什么要有数据结构呢? 可以考虑在不使用数据结构的情况下,如果需要处理100个数据,是不是就需要使用100个变量来表示它们,如果是10000个数据呢,直接就没法玩儿了。

所以,数据结构就是把大批量要处理的数据组织起来,方便编程的时候使用。数据组织的方式(结构)不同,就形成了多种多样的数据结构。每种结构都有各自的特点以及适用场景。比如,链表只能顺序存取一个数据,二叉搜索树可以 O(log(n))的时间复杂度存取数据,哈希表 可以使用 O(log(1))的复杂度存取数据但是比较适用于 key->value的数据类型。

二、链表是一种什么样的数据结构

接下来就讲一下 链表(List)这个数据结构的原理。
List是一种比较简单的数据结构,把数据通过指针(引用)串起来,组成一个链,操作者只需要拿着 head 或者 tail(双向链表) 就可以操作所有数据了。

ListNode1 –> ListNode2 –> ListNode3 –> ListNode4

每个 ListNode 包含 数据 以及对下一个 ListNode 的引用,如果我们要在某个位置上插入一个节点,比如在 ListNode3后面插入 ListNode5, 插入之后的情况就是:
ListNode1 –> ListNode2 –> ListNode3 –> ListNode5 –> ListNode4

三、python 语言实现简单的 List 结构

我们使用 python 一步步来实现一下这个数据结构,主要实现 find、insertBefore、insertAfter、remove、append、count 这几种操作。
这里主要是学习之用,所以这里的操作和一些标准库的 List 提供的操作接口不太一样。对于高级语言标准容器的List, 一般不会暴露内部的 ListNode。
关于List 的可迭代性,以及更标准的操作封装,放在下一次实现吧。
下面就是代码了,如果有些不对的地方,欢迎大家指正。

欢迎加入免费的 Python 学习交流群,扫描下面二维码加入社群或者搜索公众号“码农进步”

用 python 学习数据结构(一)链表

#  -*- coding: utf-8 -*- class ListNode():     """     定义链表节点的class,表示链表中的一个节点,其中存储了数据以及下一个节点的指针     """       def __init__(self,value):         self.value = value         self.next = None  class List():     """     定义链表类,初始化函数中定义了 head、tail 和 count 变量      head 是头结点,并不用来保存数据,所以,真正数据从 head.next开始     这样做的好处,在链表头部插入节点或者最后一个节点被删除之后,     链表的 head 应用不需要变化,简化的代码的编写。     """     def __init__(self):         self.head = ListNode(0)         self.tail = self.head         self.count = 0      def __len__(self):         """         返回链表的长度,len( listA) 函数会调用链表对象  __len__()函数              """         return self.count      def append(self, value):         """         在链表的结尾添加一个节点,节点的数据为 value         因为 List 类保存链表的末尾节点,因此直接加入到tail 的后面         """         self.tail.next = ListNode(value)         self.tail = self.tail.next         self.count+=1         return self.tail      def find(self, value):         """         查找第一个值为 value的几点,并返回ListNode         """         cur = self.head.next         while cur and cur.value != value:             cur = cur.next         return cur      def remove(self, node):         """         将某个 ListNode 从链表中删除,需要找到这个节点的         上一个节点,然后将上一个几点的 next 指向被删除节点的下一个节点。         """         pre = self.head         while pre and pre.next != node:             pre = pre.next          if pre:             pre.next = node.next             if node == self.tail:                 self.tail = pre             self.count -= 1              return node         else:             return None      def insertBefore(self, node, value):         """         在指定节点 node 之前插入值为 value 的新节点,         需要找到 node 节点的前一个节点,然后 node 和前一个节点之间插入新节点。         这里需要处理 node 为 None 的时候,插入到链表的最后位置。         """         if node is None:             return self.append(value)          pre = self.head         while pre and pre.next != node:             pre = pre.next                  if pre:             newNode = ListNode(value)             pre.next,newNode.next = newNode,node             self.count+=1             return newNode         else:             return None      def insertAfter(self, node, value):         """         在指定节点 node 之后插入值为 value 的新节点,         这里需要处理 node 为 None 的时候,插入到链表的最前位置。         """         if node is self.tail:             return self.append(value)          newNode = ListNode(value)         newNode.next = self.head.next         self.count +=1         if node is None:             self.head.next = newNode             if self.tail is self.head:                 self.tail = newNode         else:             node.next,newNode.next = newNode, node.next             if self.tail is node:                 self.tail = newNode         return newNode      def count(self):         return self.count if __name__ == '__main__':     # append     l = List()     l.append(1)     l.append(2)     l.append(3)      # find     v1 = l.find(1)     v2 = l.find(2)     v3 = l.find(3)     print(v1.value)     print(v1.value)      #remove     l.remove(v1)     l.remove(v2)      #insert before      v22 = l.insertBefore(v3, -2)     v33 = l.insertBefore(v22, -3)      #insert after     v4 = l.insertAfter(v3, 4)     v5 = l.insertAfter(v4, 5)      #count 5     print(len(l))      #遍历输出链表的各个节点,链表的遍历,冲 head.next 开始     #print list -3, -2, 3, 4, 5     cur = l.head.next     while cur:         #这里用来判断是否是最后一个节点,最后一个节点输出的时候不需要添加逗号         if cur.next:             print "%d,"%(cur.value),         else:             print cur.value         cur = cur.next 

原文始发于:用 python 学习数据结构(一)链表

主题测试文章,只做测试使用。发布者:开发工程师,转转请注明出处:http://www.cxybcw.com/3973.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code