我们将数据结构按存储方法分成两大类：线性结构数据和非线性结构数据。这两类数据结构都包含很多种类，而且实际分类也说法不同。在这里主要学习后面要使用到的，线性数据里面的数组和链表。
一、数据结构
1、数组：是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这是数组的定义，数组就是一串基本数据类型或者引用数据类型的数据的组合。在任何编程语言中，数组都是数据结构的基础。比如下图就是一个由8个int类型数据组成的数组的结构。
数组也是一种引用数据类型，是效率高的线性序列，存取速度快，但缺点是容量必须确定。插入删除元素的效率很低，需要大块连续的内存块，现实情况下，我们大部分情况都不知道容量是多少，一直是不固定的，这就导致使用范围并不广。
2、链表：链表是离散存储线性结构，包括单向链表（一个节点指向下一个节点），双向链表（一个节点有两个指针域）和循环链表（能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环）。比如下图就是一个5个int类型数据组成的双向链表数据结构：任意一个节点包含了int数据本身和两个指针域，前一个指针存放的是上一个数据的地址，后一个指针存放的是下一个数据的地址。
链表结构空间没有限制，插入删除元素很快，正好解决了数组的缺点。但是它也有缺点，就是查询、存取速度很慢。
3、散列表或者hash表：是根据关键码值(Key value)而直接进行访问的数据结构。哈希表通俗来说就是数组和单向链表的组合，其本质是一个数组，数组的每一个元素都是一个单向链表，下图就是一个由6个单向链表组成的哈希表。那么一个集合是怎么形成hash表的呢，也就是这些元素是怎么排到不同的单向链表里面的呢，其实是元素的key值通过hashcode得到的值，再调哈希算法得到值，将这个值相同的元素，放到一个链表下。通过这种方式来存储。
哈希表融合了数组和链表的优点，是我们日后开发项目中最常用到的数据结构。其实数组我们也可以理解成hash表，数组元素下标就是hash表里的key值，只不过hash表的下标是自定义的，通过这种方式可以方便我们理解hash表结构。
第一部分我们简单讲解了一下数据结构的概念，数据结构不止这些种类，它们的深层逻辑也不止这些内容，会牵涉很多高深的数学问题，但是只知道这么多就足够我们现阶段的学习了。那么这些数据结构在Java中是如何体现的呢？我们从两个方面来学习，数据结构的创建和数据结构的操作（算法）。
二、集合或者容器，Collection
在Java中，数据结构也就是数组、链表或者hash表都是对象，并且被抽象成类，Java提供了接口、抽象类以及实现类，方便我们更快捷方便的创建数据结构以及操作数据结构。
1、数组的创建，数组创建的时候长度是确定的，一旦创建长度不可更改，而且里面的元素类型都必须是相同的。如果我去看数组的源码就会发现，创建数组也是创建对象，数组的元素可以看出对象的属性。
数组的声明、创建和初始化语句：
数据类型 数组名称[ ] = new 数据类型[ 数字 ]；
或者 数据类型[ ] 数组名称 = new 数据类型[ 数字 ]；
初始化分为静态初始化，动态初始化以及默认初始化：
动态初始化：数据类型 数组名称[ ] = new 数据类型[ 数据1，数据2，数据3...... ]；
或者： 数组名称[0] = 数据1； 数组名称[1] = 数据2； 数组名称[2] = 数据3；....
如果数据类型是引用数据类型：
数据类型[ ] 数组名称 = new 数据类型[ 数字 ]；
数组名称[0] = new 数据类型();
静态初始化：数据类型 数组名称[ ] = {数据1，数据2，数据3，.......};
如果数据类型是引用数据类型：
数据类型[ ] 数组名称 = new 数据类型{数据1，数据2，数据3，.......};
2、集合
其实，我们发现有了数组我们基本可以创建所有的数据结构了，因为很多容器的底层是数组。根据定义和上面学到的数组知识，链表在Java中，可以通过数组直接定义出来，但是这些常用的数据结构没必要一次次重复的写，因此Java不仅提供了接口规范，还把实现类都写好了，我们直接使用就可以了。反过来我们可以将数据结构统一看做集合或者容器，数组被定义成为容器，为了能够更方面的操作，Java提供了接口或者规范Collection及Map，来定义我们需要的数据结构。常用的实现类有：HashSet ArrayList LinkedList HashMap。另外在学这些实现类之前，我们先要学习一个Java特性泛型。
（1）泛型，就是集合或者容器的标签，确定某一类型的标签，数据类型的参数化，<T,E,V>。编译器处理，提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。泛型最大的作用就是类型安全，可以取消类型强制转换。泛型在我们这里主要就是使用在集合中。
（2）数组和链表的创建，List接口表示有序可重复的容器，类似数组，有下标，常用实现类有ArrayList，LinkedList，Vector。Set接口表示无序不可重复的容器，
a、动态数组，最常用的就是Arraylist。数组最大的缺点就是容量固定，Java给我们重新定义了一个数组类型，能够自动扩容，解决了我们想使用数组的障碍。创建语句格式：
List<String> list = new ArrayList< > ( )；
表示的意思是，创建一个元素类型是String的可实时扩容的一个动态数组。
b、双向链表的创建，LinkedList 类用来创建双向链表，节点（Node，Entry），增删效率高，查询效率低。
List<String> list = new LinkedList<> ( )；
表达的意思是创建一个存储String元素的双向链表集合list。
c、哈希表的创建，通过Map类可以创建哈希数据结构，Map类的常见实现类有HashMap和TreeMap，HashTable，最常用的就是HashMap。
Map<Integer,String> map = new HashMap< >( )；
表达的意思是创建一个key值是int数据类型，value值是String数据类型的哈希数据结构集合。该集合的存储是“键值对”的方式，通过键对象去寻找值对象，因此键对象不能重复，键的概念可以类比数组的下标的概念，只不过这个下标的值可以自己定义。
注意，TreeMap底层采用的是红黑二叉树的数据结构，TreeMap里面的key或者value值需要排序的时候常用到，数据会按照key自增的顺序排列。如果类里面的TreeMap数据希望按照自定义方式排序，常常需要基础Comparable类，然后重写compareTo方法。该方法是重写Comparable接口里面的compareTo方法，为的是能在TreeMap中的数据排序的时候，按照我们指定的方式排列。HashMap线程不安全，但是效率高；HashTable是线程安全的hash数据结构，key和value不能为空
d、一种特殊的数据结构，HashSet的底层是HashMap，TreeSet，底层是TreeMap实现的。HashSet就是HashMap的简化版，并且Set里面的值其实就是Map里面的key，因此我们就能明白为什么Set里面的值是不能重复的原因了。对于TreeSet，对应的TreeMap，排序方式一样，自定义排序的方式也一样。
Set<String> set = new HashSet<> ( )；
三、算法
1、数组的算法
（1）主要指的是对数组里面的元素的操作，包括读取，赋值，拷贝，插入，删除。
a、数组的读取和赋值都可以用循环语句来操作，注意其中的for-each语句，可以更方便的进行读取数组的操作。
b、数组拷贝，插入，删除以及扩容。其中我们主要学习数组的拷贝，因为插入和删除都可以通过拷贝来实现，比如删除就是将除要删除的元素外的其他数据拷贝到另外一个数组，然后将此数组赋值给原数组，就完成了删除元素，插入以及扩容也是相同操作。对于拷贝，Java中的System类提供了一个不需要实现的非抽象方法，我们可以直接调用。
arrayCopy（）方法：arrayCopy（a1，b1，a2，b2，L），这个语句的意思就是将数组a1从下标是b1的元素开始拷贝，总共拷贝L个元素，放入a2数组，位置是从下标b2开始。
（2）Arrays工具类，为了更简单方便的操作数组，Java提供了一个完整的工具类，里面有各种个月的数组操作方法，可以直接调用，现在来说几种常常用到的：
Arrays.toString（数组名）方法：返回数组里面的所有元素，是Object类的toString 的方法重写。看源码知道其是静态方法，可以直接类名.toString(数组名)，直接调用。
Arrays.sort（数组名）方法：对数组中的元素重新排序，按照从小到大。如果是对象数组，我们需要自定义排序的时候，要实现Comparable接口，重新compareTo方法。
Arrays.binarySearch（数组名，元素）方法：查找数组中某个元素的下标，如果没有返回-1。
2、集合的算法
（1）遍历List Set和Map的方法：普通循环，增强for循环，使用迭代器
a、List可以用下标进行普通for循环操作；
b、List和Set可以利用泛型，通过增强for循环操作
c、迭代器，接口Iterator。这个方法是三类集合都可以使用的方法，建议项目中遇到使用这种方法。如果想了解迭代器为什么这么使用的，可以看看工厂模式以及Collection源码，就会发现Collection继承了Iterable接口，这里就不细讲。下面是代码，注意结果很有趣。
（2）
Collection接口的方法，List接口和Set接口下面的所有实现类都有的方法：
size（）方法，返回ArrayList对象中有多少元素。使用方法：对象名.size( )，返回的是int数据。
isEmpty（）方法：使用方法：对象名.isEmpty( )，返回的是布尔值。
add（）方法：向容器中增加元素，使用方法：对象名.add（数据），依次向后添加数据。
remove（）方法：移除元素，使用方法：对象名.remove（数据），将数据从集合移除。
clear（）方法：清空容器，使用方法：对象名.clear（）。
toArray（）方法：将容器转换为一个Object数组。
contains（）方法：查看容器是否包含某个元素，返回的是布尔值。
addAll（）方法：list01.addAll（list02），其中list01和list02都是ArrayList对象，方法的意思是将list02 集合中的元素都加到list01集合中。
removeAll（）方法：list01.removeAll（list02），其中list01和list02都是ArrayList对象，方法的意思是将两个集合中相同的元素删除。
retainAll（）方法：list01.retainAll（list02），其中list01和list02都是ArrayList对象，方法的意思取两个集合的交集。
containsAll（）方法：list01.containsAll（list02），其中list01和list02都是ArrayList对象，方法的意思集合01是否包含集合02的所有元素，返回值时布尔值。
但是由于List是有序集合，类似数组可以有下标，因此可以通过下标有以下自己的方法：
add（）方法：向容器中增加元素，使用方法：对象名.add（a，数据），表达的意思是在集合中，下标为数字a的地方插入一个数据元素，后面的元素依次向后移动一位。
remove（）方法：移除元素，使用方法：对象名.remove（a），将下标为a的元素移除。
set（）方法：设置某一下标元素的值。使用方法：对象名.set（a，数据1），将下标为a的数据设置为数据1，直接替换或者修改了。
get（）方法：取出某一下标元素的值。
indexOf（）方法：找某一个元素的下标。使用方法：对象名.indexOf（数据），返回数据在集合中第一次出现的下标，如果没有返回-1。
lastIndexOf（）方法：最后出现这个元素的下标。
Set由于是无序不可重复的集合，因此除了继承了Collection的方法外，并没有自己的新增方法。
Map接口，HashMap、HashTable的算法：
get（）方法：根据键值取value值，对象名.get（key值），取出key值的value的值。
put（）方法：按键值对存储对象，对象名.put（key值，value值）
size（）方法，返回HashMap对象中有多少元素。使用方法：对象名.size( )，返回的是int数据。
isEmpty（）方法：使用方法：对象名.isEmpty( )，返回的是布尔值。
containsKey（key值）方法：查看容器是否包含某个key值，返回的是布尔值。
containsValue（value值）方法：查看容器是否包含某个value值，返回的是布尔值。
putAll（）方法：使用方法：m1.putAll（m2），意思是将集合m2里面的元素放入m1集合。
（3）Collections工具类，注意其和Collection接口不同，提供对List Set Map进行排序填充查找的辅助方法，注意是工具类，也就是说类名.方法名就可以直接调用了。
Collections.shuffer（list对象名），可以对对对象里面的元素进行随机排列；
Collections.reverse(list对象名)，对对象里面的元素进行倒叙排列；
Collections.sort(list对象名)：对对象元素进行升序排序；
Collections.binarySearch(list对象名，元素）：在对象中查找元素，返回下标。
总结，这一阶段，Java基础就算是学完了，后面就是数据库以及前端的学习，还有同时Java怎么和数据库做连接，与前端内容做连接。在这个过程中就把目前最流行的SSM框架中的MyBatis，Spring及SpringMVC分开学习一下。
网友评论