链表
- 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求==待查表为有序表、顺序存储结构==，且插入删除困难。
- 线性表中利用==带头结点的双循环链表==存储方式最省时间。
- 线性表的顺序存储结构是一种==随机存取、顺序存储==的存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问。
- 线性表有两种存储结构： 1.==顺序存储结构—顺序表==。顺序表以数组形式出现，可以取任意下标访问，所以是一种随机存取的存储结构。 2.==链式存储结构—链表==。链表以链表的形式出现，必须从头开始访问，所以是一种顺序存取的存储结构。
- 链表head为空的判定条件：==带头结点单链表==：head->next == NULL；==带头结点循环链表==：head->next == head；==不带头结点单链表==：head==NULL。
- 顺序存储结构在物理上一般是连续存储，而链式存储一般不占用连续空间，相对而言，顺序存储的存储密度就大，链式存储不但要存储节点的值，还有对应的指针信息。 同样的内存空间，顺序存储不需要额外的信息。
- 链表方便删除和插入，只需知道结点和要插入的信息即可；长度可变，一般链表是动态分配内存空间；链表的结点信息至少包含数据域和指针域，相同数据下：数组的大小是链表大小的子集。
-
广义表：表==头可以为表或单元素值==，表==尾是指除去表头后剩下的元素组成的表==（即使只剩一个元素也视为表），可以为空表。
- ==线性结构==指的是数据元素之间存在着“一对一”的线性关系的数据结构。 常用的线性结构有：==线性表，栈，队列，双队列，数组，串。== ==非线性结构==的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。 如==树，表，多维数组==等。
- 区别==长度无穷大和无限列表==，由于计算机资源的限制，长度无穷大的广义表==不能==在计算机中实现。 但是如果考虑这样一个广义表 E = (a, E) ——这是一个==递归的表==，它的长度是 2 。E相当于一个无限的列表 E = (a, (a, (a, …)))，这个广义表是==可以在计算机中实现==的。
- ArrayList由数组实现，LinkedList由链表实现，数组的访问速度比链表快，==HashMap允许将null用作键或值。==
- ==链接存储结构==是在计算机中用一组任意的存储单元存储线性表的数据元素。
链式存储结构特点：
1、比顺序存储结构的==存储密度小== (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。 2、逻辑上相邻的节点物理上不必相邻。 3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。 4、查找结点时链式存储要比顺序存储慢。 5、每个结点是由数据域和指针域组成。 - 广义表中：==长度==：去掉一层括号剩下的是几部分。 ==深度==：去掉几层括号可以到最后一部分。
