「漫步计算机系统」之数据结构与算法(5):Array、List和Map等

java中主要有数组Array、链表List、栈Stack、队列Queue、哈希表Map、树Tree、堆Heap和图Graph。下面一一介绍这些数据结构：

数组Array

数组在内存中是按序一个元素接一个元素存储的，这些元素可以是基本数据类型，如int、double，也可以是对象，如Integer、String，也可以是用户自定义的对象。访问数组中某个元素非常方便，只需要给出索引即数组下标即可。但数组在定义时就确定了大小，如果要扩充就得新建一个更大数组，然后将旧元素拷贝到新数组，这带来了很大的开销。除了一维数组，也可定义任意维数组。例如，

链表List

链表不像数组可以随机访问，它在内存中的存储方式是，链接中有若干个节点，每个节点包含数据域和指向下一个节点的指针，头节点指向第一个节点，尾节点指向空，所有节点通过指针域相连，所以访问链表中某一个节点需要从表头节点开始。但是链表可动态增减，所以插入和删除节点很方便。链表还包括双向链表和循环链表等类型。

栈Stack

栈可以用数组和链表实现，操作方式需满足各自的特性。栈最大的特点就是“后进先出”，它包括两种基本操作：入栈和出栈，当有元素要添加到栈中时，将元素压到栈顶。当有元素要删除时，它从栈顶弹出。这种操作方式在很多应用中都常见，比如子程序调用，每调用一个子程序，需要将当前方法的参数、局部变量、返回地址等压入栈。返回时，通过出栈回到程序调用处。

队列Queue

队列的操作方式和栈相反，队列是“先进先出”。队列有两种基本操作：入队和出队，很容易理解，先入队的也先出队。队列在计算机中的应用就更广泛了，比如中断处理，硬件中断出现一个便将其插入中断队列，处理器按照先后顺序一个一个地处理，直到队列为空。也可设置队列元素的优先级，优先级高的可以抢占优先级低的先被处理，这在操作系统中的线程调度中就很常见。

哈希表Map

Map在java中应用很普遍，程序员常常需要在程序中设置多个键值对，键为字符串，值可为基本数据类型、字符串和任意对象。Map的最大特点就是可以很快的搜索到键所对应的值，在计算机中，不同的键通过哈希函数计算出存储地址，在该地址存放值。这样，每次查找值时，只需要计算一次哈希函数即可。哈希查找的时间复杂度为O(1)。

树Tree

树是一种非线性数据结构，树中有一个根节点，根节点可以有多个子节点，依次扩展便形成一棵树。计算机中应用的最多的是二叉树，一般的树也可以转换成二叉树。二叉树中的节点有三个域，一个为指向左子树的指针域，一个为数据域，一个为指向右子树的指针。二叉树应用在编译器的语法分析中，对一个程序进行语法分析时，可将每一条语句对应为一棵二叉树，可检查程序是否出错。

堆Heap

堆是一种特殊的二叉树。堆的特点是，其中任意一个节点数据域的值大于左右子节点数据域的值，这样的特点使堆适合排序。排序的过程是，先将所有元素生成一个堆，然后抽取根节点，根节点为最大值元素，再将右子树最后一个节点插入到根节点，重新整理堆，最后得到的根节点为数据域值第二大的节点。堆排序的时间复杂度为O(log n)。

图Graph

图也是一种非线性数据结构。很容易想到，计算机网络就是一张图，可能这是地球上最复杂的一张图。同样地，社交网络也是一张很复杂的图。图分为无向图、有向图、带权重的图等，图中一个节点的度表示和这个节点相连的边的条数，入度表示以这个节点为目的节点的边的条数，出度表示以这个节点为起点的边的条数。研究图可以得到一个节点到另一个节点的最短路径，可以知道两个节点是否可达，是否存在一个孤立的子图等。

下一篇开始详细介绍每一种数据结构与其算法。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。