数据结构:表、栈和队列

  • 数据结构分类
  • 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 -

本文链接 https://binkery.com/archives/560.html,欢迎转载,转载请注明出处。