第19章　Java中的数据结构

上一章重点讲述了数据结构、数据结构接口的基本知识，主要是以理论加上少量的实例进行讲解。本章将继续上一章的内容，通过实例来进一步加深对数据结构的认识。本章的实例分析数据结构、各种不同类型的接口，以及这些结构的具体实现过程。

本章重点：

链表和数组列表。

散列表和散列集。

树集和映像。

枚举和属性集。

19.1　链表

如果把数组作为一种数据结构，可能对读者来说更容易理解。数组这种结构有一个很大的缺点，数组中的所有元素都按序排列，如果要删除其中一个元素，后面的所有元素都需要依次向前方移动一个位置。如果这个数组元素很多，那么依次移动的次数就会明显增多，从而耗费大量的系统资源。

为了能够解决这个问题，数据结构引入了链表这个结构。下面将讲述有关链表这种数据结构的定义和具体实现。

19.1.1　什么是Java中的链表

本节介绍一种新的数据结构：链表。在Java语言中，链表中的元素存储在一条链的节点上，不像数组是按序存储在一系列连续的空间中。仔细分析图19.1，会明白它们的区别所在。

图　19.1　链表结构和数组结构图

分析为什么链表作为一种数据结构比数组要好？如图19.2所示。

从图19.2可以看出，如果在数组中删除一个元素，那么后面所有的元素都必须向前移动一位。如果元素比较多，那么移动的次数就会更多。从图19.3所示的链表图中可以看出，删除一个元素时，只需将被删除元素的前一个元素的指针，指向被删除元素的后一个元素，使得被删除的元素脱离链表，就相当于删除了元素。链表不需要像数组那样移动元素，这样就节约了系统资源。链表的结构如图19.4所示。

当要删除数组第二个元素时

图　19.2　数组的操作数据图

图　19.3　链表的操作数据图

图　19.4　链表的真正结构图

每个元素都拥有两个指针属性，一个是previous指针，一个是next指针。每一个元素的next指针都会指向下一个元素本身，而下一个元素的previous指针都会指向上一个元素本身。这样，要删除元素就比较简单，只需要让被删元素前面元素的previous指针指向被删元素后面的元素本身，再将被删除元素后面元素的next指针指向被删除元素的前面元素本身即可。