这是小生第一次写博客，语言上难免有一些不清楚，思路上难免有一些不清晰，还望各位批评指正。
最早接触数据结构与算法都是通过C语言实现的，但是我的开发过程中用C语言比较少。随着代码量逐渐的增大，我发现数据结构与算法的重要性越来越强，所以开始研究数据结构与算法的JAVA实现。
在这一篇文章中，我们先来介绍一下顺序表与链表。顺序表分为静态顺序表与动态顺序表。静态顺序表是预先设定好我要用多少空间，不会在改变；而动态顺序则是在空间不足的情况下，动态增加空间。顺序表他们在物理空间中是连续的，而链表则不是，他会储存下一个位置所在地址，是无序的。
Java中顺序表示通过ArrayList实现的，他的构造函数为ArrayList(int a) ，a为数组预分配的地址空间，如果不添加参数，则默认a为16；
而Java中链表的实现是通过LinkedList实现的，他的构造函数为LinkedList();
下面我们来比较一下这两个结构，方便大家更进一步了解他们。
首先先说数据的添加，代码如下
public static void main(String args[]){// LinkedList<Integer> ar=new LinkedList<>();ArrayList<Integer> ar=new ArrayList<>();long startTime=System.currentTimeMillis();Random ran=new Random();for(int i=0;i<500000;i++){ar.add(ran.nextInt(5000));}long endtime=System.currentTimeMillis();System.out.println(endtime-startTime);}
我的机器在运行ArrayList添加50万个数所用的时间为31毫秒左右，而运行LinkedList添加50万个数所用的时间为72毫秒左右.这个是多次运行所得到的，由此可见链表添加数据的时间比顺序表添加数据的的时间要长。因为链表在添加在寻找尾节点的时间复杂度为n，而顺序表为1。
然而，我们换一种添加方式，每一次添加都将他添加到首位，代码如下
public static void main(String args[]){// LinkedList<Integer> ar=new LinkedList<>();ArrayList<Integer> ar=new ArrayList<>();long startTime=System.currentTimeMillis();Random ran=new Random();for(int i=0;i<500000;i++){ar.add(0,ran.nextInt(5000));}long endtime=System.currentTimeMillis();System.out.println(endtime-startTime);}
此时，顺序表的添加时间为29930毫秒，而LinkedList的时间依旧为72毫秒。为什么会有如此大的差距呢，因为在顺序表中添加到首位，就要将其他为分别向后复制，时间复杂度为n2（1+2+…+n）。而链表的时间复杂度为n。
说完了添加我们应该说一下，我们该说一下删除了，我们还是用事实说话。
public static void main(String args[]){// LinkedList<Integer> ar=new LinkedList<>();ArrayList<Integer> ar=new ArrayList<>();long startTime=System.currentTimeMillis();Random ran=new Random();for(int i=0;i<500000;i++){ar.add(ran.nextInt(5000));}for(int i=0;i<500000;i++){ar.remove(ar.size()-1);}long endtime=System.currentTimeMillis();System.out.println(endtime-startTime);}
ArrayList运行时间为32毫秒，LinkedList运行时间为93毫秒，可见在删除末尾节点的时候，链表要花上一段时间，而顺序表几乎就不花时间。这是为什么呢，因为在删除链表的时候，链表要找到尾节点时间复杂度为n，而顺序表的时间复杂度为1。
那么如果我要是从头结点开始呢，我想各位读者已经猜到了，，但是我们还是以事实说话。
public static void main(String args[]){LinkedList<Integer> ar=new LinkedList<>();// ArrayList<Integer> ar=new ArrayList<>();long startTime=System.currentTimeMillis();Random ran=new Random();for(int i=0;i<500000;i++){ar.add(ran.nextInt(5000));}for(int i=0;i<500000;i++){ar.remove(0);}long endtime=System.currentTimeMillis();System.out.println(endtime-startTime);}
顺序表所用的时间为32849毫秒，链表所用时间仍然为78毫秒。在顺序表的删除中，如果删除头结点，就要将后边所有的节点向前移动一位，时间复杂度也为n2.。
Java中的线性表与链表还有什么其他的用法吗？请听下回分解。
我们一路上兴致勃勃地参观，当夕阳西下时，才恋恋不舍地离开。
