java数据结构基础

Collection
........|--------List
........|..........|----------ArrayList
........|..........|----------Vector
........|..........|.............|-----Stack
........|..........|----------LinkedList
........|--------Set
...................|----------HashSet.
...................|.............|-----LinkedHashSet
...................|----------SortedSet
.................................|-----TreeSet
　
Iterator
.....|-------ListIterator
　
Map
.....|------Hashtable
.....|..........|------Properties
.....|------HashMap
.....|..........|------LinkedHashMap
.....|------WeakHashMap
.....|------SortedMap

................|------TreeMap

Collection.
●..实现该接口及其子接口的所有类都可应用clone()方法，并是序列化类.

1......List.
.....●..可随机访问包含的元素
.....●..元素是有序的
.....●..可在任意位置增、删元素
.....●..不管访问多少次，元素位置不变
.....●..允许重复元素
.....●..用Iterator实现单向遍历，也可用ListIterator实现双向遍历

..........ArrayList
..........●..用数组作为根本的数据结构来实现List
..........●..元素顺序存储
..........●..新增元素改变List大小时，内部会新建一个数组，在将添加元素前将所有数据拷贝到新数组中
..........●..随机访问很快，删除非头尾元素慢，新增元素慢而且费资源
..........●..较适用于无频繁增删的情况
..........●..比数组效率低，如果不是需要可变数组，可考虑使用数组

..........●..非线程安全

..........●ArrayList（顺序表）底层采用数组实现，当使用不带参数的构造方法生成ArrayList对象时，实际上会在底层生成一个长度为10的Object类型数组。如增加的元素超过10个，那么底层会生成一个新的数组， 长度为原数组的1.5倍+1，然后将原数组的内容复制到新数组当中。

.
..........Vector.
..........●..另一种ArrayList，具备ArrayList的特性
..........●..所有方法都是线程安全的（双刃剑，和ArrayList的主要区别）
..........●..比ArrayList效率低

...............Stack
...............●..LIFO的数据结构

..........LinkedList.
..........●..链接对象数据结构（类似链表）
..........●..随机访问很慢，增删操作很快，不耗费多余资源

..........●..非线程安全

..........●..次类实现Queue接口，提供FIFO队列操作

2......Set.
.....●..不允许重复元素，可以有一个空元素
.....●..不可随机访问包含的元素
.....●..只能用Iterator实现单向遍历

..........HashSet
..........●..用HashMap作为根本数据结构来实现Set
..........●..元素是无序的
..........●..迭代访问元素的顺序和加入的顺序不同
..........●..多次迭代访问，元素的顺序可能不同
..........●..非线程安全

...............LinkedHashSet
...............●..基于HashMap和链表的Set实现
...............●..迭代访问元素的顺序和加入的顺序相同
...............●..多次迭代访问，元素的顺序不便
...............●..因此可说这是一种有序的数据结构
...............●..性能比HashSet差
...............●..非线程安全

..........SortedSet
..........●..加入SortedSet的所有元素必须实现Comparable接口
..........●..元素是有序的

...............TreeSet.
...............●..基于TreeMap实现的SortedSet
...............●..排序后按升序排列元素
...............●..非线程安全

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　
Iterator..
●..对Set、List进行单向遍历的迭代器

..........ListIterator.
..........●..对List进行双向遍历的迭代器

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

3.Map
●..键值对，键和值一一对应
●..不允许重复的键.

.....Hashtable.
.....●..用作键的对象必须实现了hashcode()、equals()方法，也就是说只有Object及其子类可用作键
.....●..键、值都不能是空对象
.....●..多次访问，映射元素的顺序相同
.....●..线程安全的

..........Properties
..........●..键和值都是字符串

.....HashMap
.....●..键和值都可以是空对象
.....●..不保证映射的顺序
.....●..多次访问，映射元素的顺序可能不同
.....●..非线程安全

...............LinkedHashMap
...............●..多次访问，映射元素的顺序是相同的
...............●..性能比HashMap差

.....WeakHashMap..
.....●..当某个键不再正常使用时，垃圾收集器会移除它，即便有映射关系存在
.....●..非线程安全

.....SortedMap.
.....●..键按升序排列
.....●..所有键都必须实现.Comparable.接口.

...............TreeMap.
...............●..基于红黑树的SortedMap实现

...............●..非线程安全

-------------------------------------------------------------------------------------

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。 这一点我做了实验。在分别有200000条“记录”的ArrayList和LinkedList的首位插入20000条数据，LinkedList耗时约是ArrayList的20分之1。

4.查找操作indexOf,lastIndexOf,contains等，两者差不多。

5.随机查找指定节点的操作get，ArrayList速度要快于LinkedList.
这里只是理论上分析，事实上也不一定，ArrayList在末尾插入和删除数据的话，速度反而比LinkedList要快。