2016-05-10 07:55:39
线性结构
数组是一种常见的数据结构，在初始化数组的时候，我们需要指定数组的长度，计算机会为这个数组开辟出对应长度的内存。根据数组的地址引用和索引值，我们可以很方便的访问和操作数组内的元素，因此数组也具有访问快的特点。当然数组也有一些特点，比如需要事先指定数组的长度，因此当你不知道数组确定长度的时候，为了避免数组长度不够用，你可能会声明一个比较大的长度，导致了内存的浪费。声明小了，在数组长度不够用的情况下，会出现数组下标越界的问题，因此你需要再创建一个更大的数组，然后把现在数组内的数据拷贝到新的数组上，数组拷贝的成本也是比较大的。在对数组做添加和删除操作的时候，也会需要数组拷贝的问题。
同样为线性的数据结构，链表有效的避免了数组的缺点。链表有单向链表和双向链表两种。链表在初始化的时候，并不需要给定链表的长度。
对于单向链表，链表中的每个节点都有一个指针指向下一个节点的地址，我们称为 next 指针，在需要往链表尾部添加节点的时候，只需要获取当前链表的最后一个节点，把最后一个节点的 next 指针指向要添加的节点上。往链表的中间插入和删除也是相似的，只需要修改对应节点的 next 指针。双向列表则是每个节点都有一个指针指向下一个节点（称为 next 指针），一个指针指向上一个节点（称为 previous 指针）。相比单向链表，在插入和删除的时候，双向链表要同时修改 next 指针和 previous 指针。
链表在删除和插入具有比数组更加高的效率，但是在访问上，要比数组慢一些。比如我们在获取链表的某个索引位置的节点，我们需要从链表的开始节点，找到下一个节点，再找下下个节点，这样一步一步到达我们想要的位置的节点。这个效率要比数组直接通过偏移量计算要低很多。对于单向链表，我们要获取最后一个节点的元素，那么咱们就需要遍历一整遍链表，双向链表就付出在每个节点多维护一个 previous 指针的代价下，提高了遍历的效率。
Java 中的 LinkedList 是一个双向列表的实现。ArrayList 是另外一种 List 的实现，集合了数组和链表的优点和缺点～～
队列具有先进先出的特点（FIFO），队列的具体实现可以是数组，也可以是链表，但这些都不重要，重要的是先进先出。每次只能从队列的最尾部添加节点，从最底部取走节点。
在多线程开发中，队列是必不可少的重要数据结构。一般我们会有若干个任务的生产者，产生任务，放入到队列中；同时我们有若干个任务的消费者，从队列中拉取任务。
栈具有先进后出的特点（FILO），栈的实现可以是数组，也可以是链表，同样的，怎么实现不重要，重要的是先进后出。每次添加的节点被放在栈的顶端，每次也只能从栈的顶端取走节点。
平时咱们在开发中很少用到栈，但是程序的底层设计是离不开栈的，比如方法调用栈。
树的每个节点都有若干个子节点，树的最顶端是树的根（～～不搞 IT 的人理解不了的）。
一般的应用开发中，涉及树的场景很少，涉及比较多的主要是在面试的时候。
图中的每个节点都有若干个指针指向其他节点。
一般以 key-value 存储的数据结构就是散列表，在 Java 中常见的就是 HashMap 等各种 Map 了。LinkedHashMap 是一个链表散列表，继承于 HashMap，并且封装了一个链表，LinkedHashMap 是实现 LRU 算法的思路。
- EOF -
本站文章除注明转载外，均为本站原创或编译。欢迎任何形式的转载，但请务必注明出处，尊重他人劳动。
转载请注明：文章转载自 Binkery 技术博客 [https://binkery.com]
本文标题： 数据结构：表、栈和队列
本文地址： https://binkery.com/archives/560.html