Android 数据结构与特点

Android数据结构有数组，栈，队列，链表，树，图，堆，散列表（hash表）。

图1

数组 图2

• 数组具有下标，下标从0开始计数，用于快速获取数组中的数据
• 数组在创建的时候，需要在内存中申请一段固定长度的内存，如果申请的长度超过内存剩余长度，则容易产生碎片导致存储败；
• 数组便于查找和修改数据，不便于增删数据；
• 数组分为数值数组，字符数组，指针数组，结构数组等；

栈

• 按照先进后出的原则存储数据；
• 栈分为顺序栈和链式栈；

队列

• 遵循先进先出的原则存储数据；
• 队列分为顺序队列和循环队列；

链表

• 在创建的时候，不需要指定长度，可以动态调整长度，不易产生碎片；
• 链表的每个元素分为数据和指针，指针指向下一个数据的地址，从而形成串联；
• 便于数据增删，不便于数据查询；

• 链表分为单向链表，双向链表（LinkedList），循环列表；

  
  图3

树

图4

• 有且仅有一个根节点；
• 子树之间不可以有交集；
• 树分为无序树，有序树，二叉树等；
• 树的深度指的是树的有多少层；
• 一个节点的度指的是该节点下有多少个子节点；
• 二叉树指的是每个结点的度≤2的树。
• 树的遍历方式分为三种，分别是前序遍历（根左右），中序遍历（左根右），后序遍历（左右根）；

图

图5

• 图分为有向图和无向图，区别在于边是否有方向；
• 图主要涉及到的内容是最短路径；

堆

图6

• 堆分为最小堆和最大堆，区别在于所有父节点是否大于等于其子节点，是则是最大堆，否则反之；
• 堆是一颗完全二叉树；

散列表（hash表）

图7

• 便于插入，查找等操作；
• key以数组的方式存储在栈内存中，value以链表的方式存储在堆空间中；
• 不同的key通过哈希函数可能得到相同的结果，这时候就发生了哈希碰撞；