测试题

ArrayList：

ArrayList是一种线性数据结构，它的底层是用数组实现的，相当于动态数组。与Java中的数组相比，它的容量能动态增长。类似于C语言中的动态申请内存，动态增长内存。 
当创建一个数组的时候，就必须确定它的大小，系统会在内存中开辟一块连续的空间，用来保存数组，因此数组容量固定且无法动态改变。ArrayList在保留数组可以快速查找的优势的基础上，弥补了数组在创建后，要往数组添加元素的弊端。实现的基本方法如下

1. 快速查找：在物理内存上采用顺序存储结构，因此可根据索引快速的查找元素。 
2. 容量动态增长

ArrayList与Collection关系如下图，实线代表继承，虚线代表实现接口： 

元素存储 
ArrayList是基于数组实现的，当添加元素的时候，如果数组大，则在将某个位置的值设置为指定元素即可，如果数组容量不够了，以add（E e）为例，可以看到add(E e)中先调用了ensureCapacity(size+1)方法，之后将元素的索引赋给elementData[size]，而后size自增。例如初次添加时，size为0，add将elementData[0]赋值为e，然后size设置为1（类似执行以下两条语句elementData[0]=e;size=1）。http://blog.csdn.net/jianyuerensheng/article/details/51192811

LinkedList

LinkedList与ArrayList一样，实现List接口，LinkedList是基于链表实现的，插入和删除操作比ArrayList更加有效，但随机访问的效率比ArrayList差。

LinedList数据结构原理：底层的数据结构是基于双向循环链表的，且头结点中不存放数据

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息

stack：栈

Queue：队列

Tree：树

Heap：堆

工作随笔