Java基础-JAVA中常见的数据结构介绍
作者：尹正杰
版权声明：原创作品，谢绝转载！否则将追究法律责任。
一.什么是数据结构
答：数据结构是指数据存储的组织方式。大致上分为线性表、栈（Stack）、队列、树（tree）、图（Map）。
二.线性表
线性表又细分为两大类，即数组和链表。
1>.数组（Array）
答：数组是连续的内存存储区。读取速度非常快。缺点就是容量固定，因此当你定义一个数组时，它的容量就已经固定不变啦！如果想要改变容量的话，只能创建新的数组，将之前的数据拷贝到新的数组中。典型代表：ArrayList（内部封装的是数组）。
2>.链表（linked list）
答：链表在java中的实现是LinkedList，内部使用引用的方式（指针）来实现，集合内不同通过Node来实现，有指向上家和下家的指针，每个节点上关联了元素。列表存放了first和last元素。写入速度非常快，但是读取速度远不如ArrayList。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
3>.Java中没有指针为什么又会抛出NullPointerException？
答：Java中没有指针指的是没有指针操作。因为Java中并没有指针型变量，也没有取值符，所谓的指针变量在C，C++，Golang等面向对象编程语言都是有指针操作的！
4>.为什么ArrayList查询速度要比LinkedList快呢？
答：他们底层的存储形式不同，ArrayList是基于数组形式存储的，由于数组的内存地址下标具有连续性，因此如果要在100w中查询第10w条数据时，可以根据偏移量来查询（比如一次性查阅10000条记录，只需要10次查询就能查到）。而LinkedList的存储是基于链表的形式进行存储的，此时内存地址是不连续的，因此想要在100w中查询第10w条数据时，无法通过偏移量来进行查询，必须得逐个查询，幸运的是在Java源码中你可以发现当你查询一个数据时，它会帮你判断你需要查询的索引所存在的位置（换句话说，它能把LinkedList切掉一半，然后去其中的一段遍历查询出你所需要的第10条数据）。
5>.为什么LinkedList写入速度要比ArrayList快呢？
答：还是那句话，因此他们存储的形式不同，ArrayList是基于数组形式存储的，而数组有一个致命的缺点就是容量这个概念，也就是说当你定义一个数组时，那么这个数组存储的范围就已经被确定了。尽管ArrayList可以帮我们自动扩容，当我们去查看Java源码时，你会发现所谓的自动扩容就是当数组要存满时，它会自动把数组扩容一半，即将原来的数据拷贝一份到新的数据中，因此这个过程是相当耗费时间的！而LinkedList的存储是基于链表的形式进行存储的，他在插入数据时，只需要把last和prev的属性更改即可，不需要进行拷贝数据的过程！
6>.使用Java代码测试ArrayList和LinkedList的读写速度
/*
@author :yinzhengjie
Blog:http://www.cnblogs.com/yinzhengjie/tag/Hadoop%E8%BF%9B%E9%98%B6%E4%B9%8B%E8%B7%AF/
EMAIL:y1053419035@qq.com
*/ import org.junit.Test; import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List; public class PerformanceTesting {
@Test
public void testInsertFirstArrayList(){
long start = System.currentTimeMillis();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0;i<1000000;i++){
list.add(0,i);
}
long end = System.currentTimeMillis();
System.out.printf("ArrayList的在第一个索引位置新增100W条数据用时为:[%d]毫秒(Millisecond)\n" , (end - start));
start = System.nanoTime();
list.get(50000);
end = System.nanoTime();
System.out.printf("ArrayList在获取某个元素用时为:[%d]纳秒(nanosecond)\n",(end - start));
} @Test
public void testInsertFirstLinkedList(){
long start = System.currentTimeMillis();
List<Integer> list = new LinkedList<Integer>();
for (int i = 0;i<1000000;i++){
list.add(0,i);
}
long end = System.currentTimeMillis();
System.out.printf("LinkedList的在第一个索引位置新增100W条数据用时为:[%d]毫秒(Millisecond)\n",(end - start));
start = System.nanoTime();
list.get(50000);
end = System.nanoTime();
System.out.printf("LinkedList在获取某个元素用时为:[%d]纳秒(nanosecond)\n",(end - start)); }
} /*
以上代码执行结果如下:
ArrayList的在第一个索引位置新增100W条数据用时为:[124293]毫秒(Millisecond)
ArrayList在获取某个元素用时为:[5440]纳秒(nanosecond)
LinkedList的在第一个索引位置新增100W条数据用时为:[29]毫秒(Millisecond)
LinkedList在获取某个元素用时为:[617912]纳秒(nanosecond)
*/
三.栈（Stack）
1>.什么是栈
答：栈是一种先进后出的结果，完全可以通过List模拟，手枪的弹夹就是典型的栈结构。
2>.用Java代码模拟栈
四.队列
1>.什么是队列
答：队列是先进先出的结果，也可以通过List实现。
2>.用Java代码模拟队列
五.红黑树
1>.
2>.
六.图