Android 优化 - 数据结构
一、概念
数据结构：数据存储在内存中的顺序和位置关系，选择合适的数据结构能提高内存的利用率。
| 线性结构 | |
| 链表结构 | |
| 树形结构 |
二、线性结构
| 结构 | 优点 | 缺点 | |
| 数组 | 数据呈线性排列，初始化时就要指定长度且无法更改，会开辟一块连续的内存空间，元素有序可以重复且只能是同一种类型（Object类型数组除外）。 | 查询快：由于元素是存储在一块连续的内存中，每个元素的地址值都可以通过索引算出。 | 增删慢：由于初始化后长度固定无法更改，增删元素只能用一个新的数组去存储。 |
| 链表 | 数据呈线性排列，初始化时无需指定长度，节点分散在内存中无须存储在连续的空间内，可以随意改变长度，由一系列节点（每个节点包括数值和指向下一个节点地址的指针）组成，节点有序可以重复。 | 增删快：只需要修改节点指针的指向，不需要移动复制节点。 | 查询慢：由于节点是分散在内存中的，只能从第一个元素开始顺着指针往后一个一个查起。 |
| 栈 | 数据呈线性排列，只能在头部操作元素的存取，最后添加的数据最先被取出，LIFO。 | 优先获取最新数据。 | 获取旧数据需要先取出新数据。 |
| 队列 | 数据呈线性排列，只能在头部存数据尾部取数据，最先添加的数据最先被取出，FIFO。 | 优先获取最早数据。 | 获取旧数据需要先取出新数据。 |
| Map字典（映射） | |||
| Set集合 |
链表
环形链表：尾部节点使用指针指向头部节点，将链表变成环形，这样就没有了首尾的概念，适用于保存固定数量的最新数据。
双向链表：在节点使用两个指针，这样能从前往后也能从后往前遍历，但会增加存储空间，增删也会更耗时。
三、树形结构
| 结构 | 优点 | 缺点 | |
| 堆 | 数据成树形排列，自由添加数据但每次都取出最小值。每个节点最多只有两个分支，节点排序顺序为从上到下从左到右，子节点的值大于父节点。因此最小值存储在顶端，增加元素会被放在最后的位置（最下面一行从左往右的空位上，没有就另起一行），然后跟父节点比较，父节点更大就互换位置。取出元素后会将最后位置的元素放在顶点，然后跟子节点比较，子节点更小就互换位置。 | 每次都取出最小值。 | 数据越多越慢，树越高，增删后位移比较的次数越久。 |
| 二叉树 | 数据呈树形排列，每个节点最多只有两个分支，节点排序为父节点的值大于左子树上的所有值，小于右子树上的所有值。增加元素从上往下比较，小于节点往左移，大于节点往右移。取出元素如果没有子节点就直接删掉，如果只有一个子节点就直接替代被删除节点的位置，如果有两个子节点就用左子树中最大的节点替代（即左子树一直往右的那个根节点）也能用右子树中最小的值替代（右子树最小值最接近左子树最大值且更大所以没问题）。查找和新增一样。 | 数据多的时候查找快：二分查找法的树形结构体现。 | 数据不均衡朝单侧纵向延伸，树变高耗时久。 |
二叉树
平衡二叉树可以修正形状不均匀的树提高查找效率，也可以增加子节点数。子节点数可以自由设定并且形状均衡的树叫B树。