链表和数组

1.为了弄清楚链表和数组的区别，首先要做的是实现一个数组和链表。本实例采用Java实现。

 

2.打开记事本，手动编写数组及其增删该查功能。实现的基本思想是，例如对于增加数据，先建立一个数组长度为0，当需要增加时，再建立一个数组，长度比原数组长度增加1。将原数组的所有值赋给新数组，再将要增加的值放到新数组的最后一位即可实现数据增加功能。其他删除、插入和获取数据的方法类似：

 

public class MyQueue{

private Object[] ds = new Object[0];

 

//加入数据

public void add(Object c){

Object[] ns = new Object[ds.length+1];

for(int i=0;i<ds.length;i++){

ns[i] = ds[i];

}

ns[ns.length-1] = c;

ds=ns;

}

 

  //获取数据

public Object get(int index){

return ds[index];

}

 

//删除

public void remove(int index){

Object[] ns = new Object[ds.length-1];

for(int i=0;i<index;i++){

ns[i]=ds[i];

}

for(int i=index;i<(ds.length-1);i++){

ns[i]=ds[i+1];

}

ds=ns;

}

 

//插入

public void insert(Object c,int index){

Object[] ns = new Object[ds.length+1];

for(int i=0;i<index;i++)

ns[i]=ds[i];

ns[index]=c;

for(int i=index;i<ds.length;i++){

ns[i+1]=ds[i];

}

ds=ns;

}

 

public int size(){

return ds.length;

}

}

 

3.如果用链表来实现的话，基本思想的先建立一个Link类，每个Link对象包含它本身的值和它指向的下一个数据的地址(类似于C++中的指针)。对于新增数据，就是把要增添的数据值赋给现在位置，现在位置再指向下一个地址。其他的获取、删除和插入等情况类似：

 

class Link{

Link next;

Object data;

}

 

public class LinkList{

Link root,present;

int size=0;

 

//新增数据

public void add(Object c){

if(root==null){

root = new Link();

root.data=c;

present=root;

}else{

Link next=new Link();

next.data=c;

present.next=next;

present=next;

}

size++;

}

 

//获取数据

public Link get(int index){

if(index>=size){

return null;

}

else{

Link temp=new Link();

temp=root;

for(int i=0;i<index;i++){

temp=temp.next;

}

return temp;

}

}

 

//删除数据

public void delete(int index){

if(index>=size)

System.out.println("Fail!");

else{

Link temp1=get(index-1);

Link temp2=get(index+1);

temp1.next=temp2;

size--;

}

 

}

 

//插入数据

public void insert(int index,Object c){

if(index>=size)

System.out.println("Fail!");

else{

Link temp=new Link();

temp.data=c;

Link temp1=get(index);

Link temp2=get(index-1);

temp2.next=temp;

temp.next=temp1;

}

}

 

public int size(){

return size;

}

 

}

 

4.编写完成后，我们在cmd中编译和测试。首先编写测试文件。将数量级控制在100000：

 

数组和链表分别执行的时间如下:

public class Test{

public static void main(String args[]){

MyQueue qu = new MyQueue();

LinkList ls = new LinkList();

 

long start1 = System.currentTimeMillis();

for(int i=0;i<100000;i++){

qu.add(i);

}

long end1 = System.currentTimeMillis(); 

 

long start2 = System.currentTimeMillis();

Object c=qu.get(8888);

long end2 = System.currentTimeMillis();

 

long start3 = System.currentTimeMillis();

qu.insert(8888,1);

long end3 = System.currentTimeMillis();

 

System.out.println("数组增加运行时间："+(end1-

start1)+"毫秒");

System.out.println("数组查询运行时间："+(end2-

start2)+"毫秒");

System.out.println("数组插入运行时间："+(end3-

start3)+"毫秒");

 

}

}

 

由此可以看出，当数量级为10万时，数组和链表的运行时间就有了较大的差距。链表在插入数据方面的确有着特别快的处理速度。查询方面，数组几乎不要时间。插入方面，链表几乎比数组插入快30倍。并且可以分析得出当要插入的位置下标越大，二者的时间差距也越大。

 

5.分析

由上可知：

(1)数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)

(2)数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)

(3)另外在空间上，数组在内存上是连续分配的，而链表则非连续分配。这一点使得当数组过大时可能会出现内存分配问题，而链表则不会。