顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。
顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
图a是顺序表数据存储的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc(ei) = Loc(e0) + c*i。访问指定元素时无需遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。
如果元素的大小不统一，则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量(通常很小)。图b这样的顺序表也被称为对实际数据索引，这是最简单的索引结构。
一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，包括元素存储区的容量和当前表中已有的元素个数等信息。
图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
图b为分离式结构，表对象里只保存与整个表有关的信息（即容量，元素个数和元素存储首地址），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。
当顺序表中需要添加新的元素进来时，由于元素存储区地址要保持连续性，所以就需要重新申请更大的存储空间，将现有元素全部迁移到新地址，再加入后来的元素，最后将原元素存储区释放。
一体式结构中扩充后，顺序表地址也随之被改变，而分离器结构中，则只需要将表头中元素存储首地址修改为新的地址即可，顺序表地址不变。这种保持地址不变且容量可以动态扩充的顺序表称为动态顺序表。
存储区扩充有以下两种常用策略:
- 线性扩充。每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置。其特点为节省空间，但扩充频繁，操作次数多。
- 倍速扩充(推荐)。每次扩充容量加倍，如每次扩充增加一倍存储空间。可以减少操作的次数，但可能会浪费空间资源。是一种以空间换时间的放回寺。
集合对象最常见的操作就是CRUD，顺序表亦是如此。由于顺序表顺序利用内存空间的特性，其查询和修改操作可直接利用索引定位元素，所以其时间复杂度均为O(1)。
顺序表新增元素有两种方式，一种是在尾部新增元素，另一种则是在特定位置新增元素。
如上图所示，在尾部新增元素，直接根据索引定位尾部，加入新元素即可，其时间复杂度为O(1)。在特定位置新增元素分为保序和非保序两种方式。保序方式需先根据索引定位，然后将此位置后所有元素全部后移，最后将新的元素插入到之前的位置，如果要在第0个元素处新增，则全部元素需要后移，故而其最坏事件复杂度为O(n)。非保序插入的则将指定位置元素移到尾部，然后将新元素插入空出的位置即可，其时间复杂度为O(1)。多数情况下，顺序表都是固定元素顺序的，非保序方式使用较少。
顺序表删除元素的过程与新增原理完全相同。时间复杂度分别为，尾部删除O(1),删除特定元素，保序为O(n)非保序为O(1)。
Python中list和tuple两种类型均采用顺序表的实现。tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其与list的性质相同。下面我们主要以list为例讲解。
在Python的官方实现中，list就是一种元素外置存储的采用分离式技术实现的动态顺序表。因此可以使用下标方式访问元素，扩充后地址(id)不变。list采用保序方式操作元素，所以新增和删除元素后其元素顺序保持不变。
list内存使用策略如下。在建立空表(或者很小的表)时，系统直接申请8个元素的存储区；在执行插入操作(insert或append)时，如果8个存储区满，以4倍倍增扩充，如存储区达到50000的阈值，则改用一倍倍增。
关于顺序表更多内容，请参阅 https://python.a-nomad.com/datastructure/sequencelist.html
链表(linked list)是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表定位元素只能按照指针链，逐个查找，没有顺序表的索引结构。链表中CRUD操作的时间复杂度分别为，头插法O(1),尾插法和定位插入O(n),删除O(n)，修改和查询均为O(n)。
单向链(Single Linked List)表也叫单链表，是链表中最简单的一种形式，单链表中的数据是以结点来表示的，每个结点的构成：元素 + 指针，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。终端结点无后继，故终端结点的指针域为空(None)。
单向循环链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
顺序表与链表同属线性表。
顺序表利用连续内存地址关联元素，可以迅速定位元素位置，查询和更新操作比较高效，但大量频繁的扩充元素则需要重新申请大块连续内存迁移所有的元素，执行效率偏低，删除操作则需要将删除元素后的所有元素前移。
链表通过节点指针串联元素，可以更好地利用非连续内存，但定位节点只能顺着指针连逐次查找，因此查询很更新操作比较低效。但新增节点则只需要申请新的内存挂在到现有链表中，删除元素则只需要修改前驱和后继节点的指针指向即可，因此新增和删除操作更加灵活高效。
在数据元素较少且规模相对固定，更多执行查询和更新操作的场景中，推荐使用稳定性更好的顺序表；相反的，数据规模未知且变动频繁，更多执行插入和删除操作的场景中推荐使用链表。
链表结构在不同的开发平台都有各自语言的版本实现，如链表在C#当中实现为LinkedList<T>，而Python并没有内建链表实现，需要我们自定义实现。linkedlist.py即是一种链表的自定义实现。
关于链表更多内容，请参阅 https://python.a-nomad.com/datastructure/linkedlist.html
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
栈在Python中也没有默认提供，需要我们自定义实现。linearcollection.py演示了中使用顺序表实现栈。
队列(queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
队列在Python中也没有默认提供，需要我们自定义实现。linearcollection.py演示了中使用顺序表实现队列。
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。Redis的List类型就是双端队列。
双端队列在Python中也没有默认提供，需要我们自定义实现。linearcollection.py演示了中使用顺序表实现双端队列。
关于栈和队列的更多内容，请参阅 https://python.a-nomad.com/datastructure/stackqueue.html
树(tree)是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树具有以下的特点：
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
| 术语 | 含义 |
|---|---|
| 节点的度 | 一个节点含有的子树的个数称为该节点的度 |
| 树的度 | 一棵树中，最大的节点的度称为树的度 |
| 叶节点或终端节点 | 度为零的节点 |
| 父节点 | 若一个节点含有子节点，则这个节点称为其子节点的父节点 |
| 子节点 | 一个节点含有的子树的根节点称为该节点的子节点 |
| 兄弟节点 | 具有相同父节点的节点互称为兄弟节点 |
| 节点层次 | 从根开始定义起，根为第1层，根的子节点为第2层，以此类推 |
| 树高度或深度 | 树中节点的最大层次 |
| 堂兄弟节点 | 父节点在同一层的节点互为堂兄弟 |
| 节点祖先 | 从根到该节点所经分支上的所有节点 |
| 子孙 | 以某节点为根的子树中任一节点都称为该节点的子孙 |
| 森林 | 由m（m>=0）棵互不相交的树的集合称为森林 |
树有以下常用分类。
- 有序树。树中任意节点的子节点之间有顺序关系，这种树称为有序树；
- 二叉树。每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树。除最后一层外，其它各层的节点数目均已达最大值，且最后一层从左向右连续地紧密排列，这样的二叉树被称为完全二叉树
- 满二叉树。所有叶节点都在最底层的完全二叉树。如下图所示。
- 平衡二叉树(AVL树)。当且仅当任何节点的两棵子树的高度差不大于1的二叉树
- 排序二叉树(二叉查找树，也称二叉搜索树、有序二叉树）
- 霍夫曼树(用于信息编码)。带权路径最短的二叉树称为哈夫曼树或最优二叉树
- B树。一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树
- 二叉树。每个节点最多含有两个子树的树称为二叉树；
- 无序树。树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
以下业务场景中，需要是哟功能树结构：
- xml，html结构
- 路由协议
- mysql 数据库索引
- 文件系统目录结构
- 很多经典AI算法使用树搜索。机器学习中的
decision tree也是树结构
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
二叉树有以下特性：
- 第 n 层最多有 2n-1 个结点(n>0)
- 深度为 n 的二叉树最多有 2n-1 个结点(n>0)
- 叶结点数为 n0，而度数为2的结点总数为 n2，则 n0 = n2+1
- 具有 n 个结点的完全二叉树的深度为 log2(n+1)
一般情况下，二叉树多使用完全二叉树方式存储，如下图就是一个完全二叉树。
我们可以仿照链表的数据结构方式，构建完全二叉树。我们首先构建一个只有根节点的二叉树，然后逐个挂载节点。定义一个待处理节点队列(默认加入根节点)。出队一个待分析节点，先判断其左子树是否为None，如果是则直接挂载新节点并退出，否则判断其柚子树是否为None，如果是则直接挂载新节点并退出，否则将其左右节点都入队。然后重复以上操作直到挂载成功。详细代码参见 binarytree.py
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。
广度优先遍历也称层次遍历，其策略是从树的根节点开始，从上到下从从左到右遍历整个树的节点，与构建完全二叉树的思路一致,此处不再赘述。
上图二叉树，广度优先遍历结果为 ABCDEFGHIJ
深度遍历根据访问根节点的次序不同分为三种方法，先序遍历(preorder)，中序遍历(inorder)和后序遍历(postorder)
- 先序遍历。先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树。
- 中序遍历。递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树。
- 后序遍历。先递归使用后序遍历访问左子树和右子树，最后访问根节点。
遍历操作详细代码参见 binarytree.py
上图二叉树，先序遍历结果为 ABDHIEJCFG，中序遍历结果为 HDIBJEAFCG，后序遍历结果为 HIDJEBFGCA。
二叉树遍历过程中，所有节点会作为一个序列输出，左右子树的节点是同级的且有序的(先左后右)，如果可以确定根节点，那就可以使用根节点递归划分左右子树来，这样就可以唯一确定、一棵二叉树树的结构。
简单讲，只要确定中序遍历结果，结合先序或后序遍历结果任意一种，就能确定一个二叉树。
如：有先序遍历结果为 ABDHIEJCFG，中序遍历结果为 HDIBJEAFCG。我们来尝试构建完全二叉树。
先序规则为根左右，首个节点A就是树的根节点，依此中序结果以A为界分为HDIBJE(左子树)和FCG(右子树)。先序第二个节点B为左子树节点HDIBJE的根节点，以B为界分为HDI(左子树)和JE(右子树)。依此类推，逐层确定根节点，最终分组小于等于2时，每组一个元素，根节点左侧为左树，右侧为右树，这样就可以确定如上图所示的二叉树。
关于树结构的更多内容，请参阅 https://python.a-nomad.com/datastructure/tree.html