链表和数组的区别？
以前面试遇到一个问题，你什么时候会使用链表什么时候使用数组。大学c数据结构白学了把。有种想回去复读的冲动。这个时候我们要清楚的明白list和Linklist的区别：
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。
二者都属于一种数据结构：
(1) 从逻辑结构角度来看　　
a、 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
　 b、链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）　　
(2)从内存存储角度来看：
a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。　　
b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.
LinkedList类扩展AbstractSequentialList并执行List接口。它提供了一个链接列表数据结构。它具有如下的两个构造函数，说明如下– LinkedList( )– LinkedList(Collection c)– 第一个构造函数建立一个空的链接列表。– 第二个构造函数建立一个链接列表，该链接列表由类集c中的元素初始化LinkedList类的一些方法 public boolean add(Object element) 向链表的末尾添加一个新的节点对象elementpublic void add(int index,Object element)向链表的指定位置尾添加一个新的节点对象element public void addFirst(Object element)把节点对象element添加到链表的表头 public void addLast(Object element)把节点对象element添加到链表的末尾 等介于 == public boolean add(Object element) public void cleat()删除链表的所有节点对象public Object remove(int index)删除指定位置上的节点对象public boolean remove(Object element)将首次出现的节点对象element删除
public Obiect removeFirst() 删除第一个节点对象,并返回这个节点对象.
public Object removeLast() 删除最后一个节点对象
public Object get(int index)得到链表中指定位置上的节点对象public Object getFirst()得到链表中的第一个节点对象
public Object getLast()得到链表中的最后一个节点对象
public int indexOf(Object element) 返回节点对象element，在链表中首次出现的位置，如果链表中无此节点，则返回-1
public int lastIndexOf(Object element) 返回节点对象element，在链表中最后出现的位置，如果链表中无此节点，则返回-1
public Object set(int index ,Object element) 用节点对象element替换指定位置的节点对象，并返回链表中先前位置处的节点对象public int size()返回链表的长度，即节点的个数public boolean contains(Object element) 判断链表节点对象中是否含有element
LinkedList是采用双向循环链表实现的。利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。
总之：
ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。当执行搜索操作时，采用ArrayList 比较好。