小白学数据结构之【线性表----顺序表，链表】的Python表示笔记
前言，数据结构分为：结构性数据结构、功能性数据结构其中，结构性数据结构有：集合机构、顺序结构、层次结构、树形结构、图结构；功能性数据结构有：栈、队列、优先队列、字典。由于功能性数据结构只有功能性要求，所以它们可以采用任何技术实现，通常把它们映射到某种结构性数据结构，再采用相应技术实现。
1.线性表
前言:线性表分为：顺序表、链接表。
顺序表：表中元素的顺序为它们的存储顺序，元素之间的逻辑顺序关系通过元素在存储区里的物理位置表示。
链接表：元素的顺序通过“链接”构造
1.1顺序表（tuple、list）
1、顺序表的两种布局：表中元素类型相同、表中元素类型不相同
PS:b图中的c不是数据元素的大小，而是存储一个链接所需要的存储量，通常很小。
2、在建立一个顺序表时，一种可能是按建立时确定的元素个数分配存储。这种做法适合创建不变的顺序表，例如tuple对象。如果考虑的是变动的表，就必须区分表中（当前的）元素个数和元素存储区的容量。在建立这种表时，一个合理的办法是分配一块足以容纳当前需要记录的元素的存储块，还应该保留一些空位，以满足增加元素需要。
3、顺序表的优缺点：
优点：O（1）时间复杂度的按位置访问元素；元素在表里存储紧凑着，除表元素储存区之外只需要O（1）空间存放少量辅助信息。
缺点：需要连续的存储区存放表中的元素，如果表很大，需要大片的连续内存空间。一旦确定了存储块的大小，可容纳单元个数并不随着插入/删除操作的进行而变化。如果很大的存储区里只保存了少量数据项，就会有大量空闲单元，造成表内的存储浪费。另外，在执行加入或删除操作时，通常需要移动许多元素，效率低。还要事先考虑元素存储区的大小，这很难估计。
4、顺序表list和tuple
5、顺序表的简单总结
1.2 链表（单）
1、单向链接表的结点是一个二元组，包括数据域和链接域。从表中任一结点可以找到保存着该表下一个元素的结点，这样，从第一个结点出发，可以找到这个表里的任一结点。
2、一个链表的结点类的PYTHON表示如下：
3、单链表类的PYTHON实现
4、人们把线性表一类的对象称为汇集器(collection)对象，它们本身是对象，其中又包含着一组元素对象。显然，python里的list、tuple等都是汇集器对象。对于汇集器对象，最经典的使用方法就是遍历，逐个使用其元素。Python语言为内部汇集器类型提供的遍历机制是迭代器，标准使用方式是在for语句头部，在循环体中逐个处理汇集器对象的元素，这样就可以方便的实施各种操作。例如：
5、筛选生成器：
1.3、带尾结点引用的单链表
1、单链表实现有一个缺点：尾端加入元素操作的效率很低，因为这时只能从表头开始查找，直至找到表的最后一个结点，而后才能链接新结点。如果在表对象增加一个表尾结点引用域，只需常量时间就能找到尾结点，在表尾加入新结点的操作可能做到O（1）。
2、
3、带尾结点引用的单链表的Python类实现:
1.4、循环链表（单）
1、单链表的另一常见变形是循环单链表，其中最后一个结点的next域不用None，而是指向表的第一个结点。如果在链表对象里记录表尾结点更合适，这样可以同时支持O（1）时间的表头/表尾插入和O（1）时间的表头删除。由于循环链表里的结点连成一个圈，哪个结点算是表头或表尾，主要是概念问题，从表的内部形态上无法区分。
2、一个循环单链表类的PYTHON实现
1.5 带尾结点引用的双链表
1、单链表只有一个方向的链接，只能做一个方向的扫描和逐步操作。即使增加了尾结点引用，也只能支持O（1）时间的首端元素加入/删除和尾端加入（尾端删除需要O（n）时间开销）。如果希望两端插入和删除操作都能高效完成，就必须修改结点（从而也是链表）的基本设计，加入另一方向的链接。这样就得到了双链表。这样做的好处是，支持两端的高效操作，一般结点操作也会更加方便。代价是，每个结点增加一个链接域，增加的空间开销和结点数成正比，O（n）。
2、
3、双链表的python类实现：