前序
现在毕业之后工作已有一年 当年在学校中的意气风发现在已经渐渐被磨平 平常的工作更多的也只是做着一些重复性的工作 能好好学习和反刍的时间也比较少 现在也只能抓住一些日常闲暇的时间去学一下前沿领域的技术 同时也做做小笔记 以防健忘和以备日后查询使用。
我如今在某中国头部城商行做数据分析方面的工作 其实日常工作接触较多的是sql和sas这类语言 python虽然作为公司推广使用的未来之星 但其实也很少有人去系统性地学了。我在大学期间学过大约两年的python 主要是python的基础语法 数据处理和机器学习方面的。现在除了一些基本语法 其他那些比如使用pandas处理数据 或者手撕一个机器学习算法其实已经忘的差不多了。但面对这个日新月异的社会 不断的学习进步对于我们做技术的人来说其实非常重要 在学习的过程中 如果能留下一些记录 对于自我的理解会更有帮助 甚至能供他人参考那就更加好了。所以想通过这些笔记去重拾python这门技术。
今天先写一个使用python实现链表这样的数据结构 对于写编程的人来说 链表应该是不陌生的 基本是必学必会的基础。何为数据结构 可以理解为计算机存储数据以及建立数据间的联系的一种方式。程序在电脑上跑的时候 数据是在内存单元中去存储和计算的 此时 如果你新建一个变量a 1 那就是在内存单元中开辟了一块内存空间 针对python这类面向对象语言来说 这块内存空间就会存储一个整数对象 该对象的值是1 而a是一个标签 它会指向这个内存空间 通过a可以访问到这个内存空间中的值 以此类推 如果你再定义一个b 1 那其实就是新增了一个标签 名字是b 它也会指向1这个内存空间 a和b都能访问到相同的对象。
当有多个数据在内存空间中的时候 并且数据之间存在关联性 需要能相互访问 这个时候就需要用到如数组和链表这些数据结构。数组这种数据结构存储的数据在内存中是连续的 也就是说它们在内存中的id值是连续的。而链表在内存中是“飘忽不定”的 但是它依然能做到关联性访问 原因就在于它的next指针。
以下是数组的数据模型
以下是链表的数据模型
如上图所示 箭头其实就是链表中的next指针 它会对当前节点的下一个节点做一个指向 指明其下一个节点所在的位置。
在这里 我们运用python面向对象的特性 将链表拆解成两块对象去理解 一个是链表的整体作为一个对象 一个是链表中每个节点又是一个独立的对象。对象来源于类的实例化。
类 其实就是事物的抽象 世间万物都可以分门别类。比如人 有黄种人、白种人、黑种人的分别 但是其都归属于人类这个类别 这类别下的实例都是有相同的属性的 只不过属性间的值有所不同而已。就好比人类中的黄种人和白种人 都是有皮肤的 但是皮肤的颜色不同 这就是属性一样 但是属性的特性不一样。
图中链表这里的每个节点都是Node类的一个实例化 它具有自身的值val和next的属性 val的取值有1 2 3的区别 同时next指针指向也有不同。链表这个对象也有相应的属性 这里的1节点是链表的头节点 head 3是链表的尾节点 tail 。同时类还可以拥有类方法 方法是类中的一个操作性的功能 相当于是所有人类都会吃饭、睡觉这类基本操作 我们也可以定义某个类它拥有这样的能力。这里我们会定义链表类拥有添加自身节点和遍历节点的能力。
关于类的详细知识在这里不赘述了 往后可能也会更新这类知识进来 接下来就直接上链表的python实现代码
#定义节点类 class Node(): def __init__(self,val): self.val val self.next None #定义链表类 add_node是添加节点的方法 travle_node是遍历链表中所有节点的方法 class List_tb(): def __init__(self): self.head None self.tail None def add_node(self,val): n Node(val) if self.head is None: self.head n self.tail n else: tmp_tail self.tail self.tail n tmp_tail.next self.tail def travle_node(self): tmp_head self.head while tmp_head is not None: print(tmp_head.val) tmp_head tmp_head.next #实例化一个链表对象 lt List_tb()
#调用方法添加节点 lt.add_node(1) lt.add_node(2) lt.add_node(3) #调用方法遍历节点 下面是输出结果 lt.travle_node() 3
这只是链表里面最简单的一种形式 链表的变形很多 有双向指针链表 有头尾连在一起的环形链表 也有尾部连在中间的变幻式 总之 编程的世界很宽广 还是需要保持好学和谦虚的态度不断拾珍的。
