什么是算法和数据结构？
你可能会在网上看到这句话：
程序 = 算法 + 数据结构
算法（Algorithm）：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
数据结构（Data Structures）：是计算机存储和组织数据的一种方式，可以用来高效地处理数据。
举个例子：二分查找就是一个非常经典的算法，而二分查找经常需要作用在一个有序数组上。这里二分就是一种折半的算法思想， 而数组是我们最常用的一种数据结构，支持根据下标快速访问。很多算法需要特定的数据结构来实现，所以经常把它们放到一块讲。
实际上，在真正的项目开发中，大部分时间都是 从数据库取数据 -> 数据操作和结构化 -> 返回给前端，在数据操作过程中需要合理地抽象， 组织、处理数据，如果选用了错误的数据结构，就会造成代码运行低效。这也是我们需要学习算法和数据结构的原因。Python一切皆对象
举个例子，在 python 中我们经常使用的 list
l = list() # 实例化一个 list 对象 ll.append(1) # 调用 l 的 append 方法l.append(2)l.remove(1)print(len(l)) # 调用对象的 `__len__` 方法在后面实现新的数据类型时，我们将使用 python 的 class 实现，它包含属性和方法。 属性一般是使用某种特定的数据类型，而方法一般是对属性的操作。 这里你只需了解这么多就行了， 我们不会使用继承等特性。
什么是抽象数据类型 ADT
实际上 python 内置的 list 就可以看成一种抽象数据类型。
ADT: Abstract Data Type，抽象数据类型，我们在组合已有的数据结构来实现一种新的数据类型， ADT 定义了类型的数据和操作。
我们以抽象一个背包(Bag) 数据类型来说明，背包是一种容器类型，我们可以给它添加东西，也可以移除东西，并且我们想知道背包里 有多少东西。于是我们可以定义一个新的数据类型叫做 Bag.
class Bag: """ 背包类型 """ pass实现一个 Bag ADT
视频中我们将使用 python 的 class 来实现一个新的容器类型叫做 Bag。
实现 ADT 我们应该注意什么？
如何选用恰当的数据结构作为存储？选取的数据结构能否满足 ADT 的功能需求实现效率如何？线性结构
本节我们从最简单和常用的线性结构开始，并结合 Python 语言本身内置的数据结构和其底层实现方式来讲解。 虽然本质上数据结构的思想是语言无关的，但是了解 Python 的实现方式有助于你避免一些坑。
我们会在代码中注释出操作的时间复杂度。
数组 array
数组是最常用到的一种线性结构，其实 python 内置了一个 array 模块，但是大部人甚至从来没用过它。 Python 的 array 是内存连续、存储的都是同一数据类型的结构，而且只能存数值和字符。
我建议你课下看下 array 的文档：https://docs.python.org/2/library/array.html
你可能很少会使用到它(我推荐你用 numpy.array)，我将在视频里简单介绍下它的使用和工作方式，最常用的还是接下来要说的 list， 本章最后我们会用 list 来实现一个固定长度、并且支持所有 Python 数据类型的数组 Array.
列表 list
如果你学过 C++，list 其实和 C++ STL（标准模板库）中的 vector 很类似，它可能是你的 Python 学习中使用最频繁的数据结构之一。 这里我们不再去自己实现 list，因为这是个 Python 提供的非常基础的数据类型，我会在视频中讲解它的工作方式和内存分配策略， 避免使用过程中碰到一些坑。当然如果你有毅力或者兴趣的了解底层是如何实现的，可以看看 cpython 解释器的具体实现。
用 list 实现 Array ADT
讲完了 list 让我们来实现一个定长的数组 Array ADT，在其他一些语言中，内置的数组结构就是定长的。 这里我们会使用 list 作为 Array 的一个成员（代理）。具体请参考视频讲解和代码示例，后边我们会使用到这个 Array 类。
单链表
和线性结构不同，链式结构内存不连续的，而是一个个串起来的，这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。
这里可不要混淆了列表和链表（它们的中文发音类似，但是列表 list 底层其实还是线性结构，链表才是真的通过指针关联的链式结构）。 看到指针你也不用怕，这里我们用的 python，你只需要一个简单赋值操作就能实现，不用担心 c 语言里复杂的指针。
先来定义一个链接表的节点，刚才说到有一个指针保存下一个节点的位置，我们叫它 next， 当然还需要一个 value 属性保存值
class Node(object): def __init__(self, value, next=None): self.value = value self.next = next然后就是我们的单链表 LinkedList ADT:
class LinkedList(object): """ 链接表 ADT [root] -> [node0] -> [node1] -> [node2] """实现我们会在视频中用画图来模拟并且手动代码实现，代码里我们会标识每个步骤的时间复杂度。
这里请高度集中精力， 虽然链表的思想很简单，但是想要正确写对链表的操作代码可不容易，稍不留神就可能丢失一些步骤。 这里我们还是会用简单的单测来验证代码是否按照预期工作。
来看下时间复杂度：
双链表
上边我们亲自实现了一个单链表，但是能看到很明显的问题，单链表虽然 append 是 O(1)，但是它的 find 和 remove 都是 O(n)的， 因为删除你也需要先查找，而单链表查找只有一个方式就是从头找到尾，中间找到才退出。
这里我之前提到过如果要实现一个 lru 缓存（访问时间最久的踢出），我们需要在一个链表里能高效的删除元素， 并把它追加到访问表的最后一个位置，这个时候单链表就满足不了了， 因为缓存在 dict 里查找的时间是 O(1)，你更新访问顺序就 O(n)了，缓存就没了优势。
这里就要使用到双链表了，相比单链表来说，每个节点既保存了指向下一个节点的指针，同时还保存了上一个节点的指针。
class Node(object): # 如果节点很多，我们可以用 __slots__ 来节省内存，把属性保存在一个 tuple 而不是 dict 里 # 感兴趣可以自行搜索 python __slots__ __slots__ = ('value', 'prev', 'next') def __init__(self, value=None, prev=None, next=None): self.value, self.prev, self.next = value, prev, next对， 就多了 prev，有啥优势嘛？
看似我们反过来遍历双链表了。反过来从哪里开始呢？我们只要让 root 的 prev 指向 tail 节点，不就串起来了吗？直接删除节点，当然如果给的是一个值，我们还是需要查找这个值在哪个节点？ - 但是如果给了一个节点，我们把它拿掉，直接让它的前后节点互相指过去不就行了？哇欧，删除就是 O(1) 了，两步操作就行啦
我是白又白i，一名喜欢分享知识的程序媛❤️
如果没有接触过编程这块的朋友看到这篇博客，发现不会编程或者想要学习的，可以直接留言+私我呀~【非常感谢你的点赞、收藏、关注、评论，一键四连支持】
网友评论