数组队列和链表

数组队列——当用数组不方便的时候，数组队列是非常方便的。数组队列的长度可改变

，存储数据的类型也可以是多样的。这点是数组所不具备的有优点，所以我们可以用数

组队列来记录比如说五子棋中下过的棋子，所以我觉得数组队列是有“记忆功能”的。

因为它的长度可以改变嘛，所以比如说每下一步棋，长度就可以加一，以前的数据也不

会被覆盖掉。
链表呢是有一个部分用来存储数据，一个部分用来指向下一个地址，这是单链表，还有

双链表和循环链表，这样我们使用起来的时候就很方便了，下面我用代码来比较一下数

组队列和链表。
增加数据：
数组队列：array[i]是之前定义好的一个一维数组
public void add(Object element){
Object array1[] = new Object[size+1];
for(int i=0;i<size;i++){
array1[i] = array[i];
}
array1[size] = element;
size++;
//将新的数组名赋给array
array = array1;

}

链表：
public void add(Node node){
// 如果根节点地址为空，则表示没有连表内没有节点
if(root == null){
root = node; //将新的节点赋值给根节点
tail = node; //将新的节点赋值给尾节点

}else { //链表不为空
tail.setNext(node);//在尾节点后面添加节点
node.setLast(tail);
tail = node; //再将新节点赋值给尾节点
}
size++; //链表的大小要增加

}

虽然代码都差不多，但是其实从执行效率来说，一定是链表大于数组队列的，因为数组

队列增加数据的时候，数组队列是需要把原先的数组先赋给新的数组，再把最后一个元

素放进新数组的最后一个位置。而链表直接把最后尾节点的指针再指向新增加的元素就

可以了。
这是添加元素，也许优势不是很明显，但是看下面这一段修改元素值得方法：
数组队列：

public Object alter(int index,Object element){
Object [] array4 = new Object[size];
for(int i=0;i<index;i++){
array4[i] = array[i];
}

array4[index]=element;

for(int j = index+1;j<size;j++){
array4[j] = array[j];
}

链表：

public Object update(int index,Object newobj){
Node node = root;
for(int i=0;i<=index;i++){
node = node.getNext();
}
node.setobj(newobj);

return  node.getobj();
}

数组队列中修改元素值需要创建一个新的数组，将要修改值得前面部分全部赋给新的数

组，然后将修改后的值赋给新数组的最后一个元素，再把原来数组中需要修改的值得后

面部分赋给新数组。这样显得很笨重。链表呢可以直接找到要修改的那个地方，直接给

它附上新值就可以了。除此之外，插入，移除元素，链表都比数组队列效率要高。那么

你就会想，既然链表这么方便，为什么还要用数组队列呢，其实不然，数组队列有一个

极大的好处，就是查找非常方便，而链表的优点就是增删改非常方便，所以各取所需嘛

。下面来对比一下两个的查找功能。
数组队列：

public Object get(int index){
if(index<=0 || index>=size){
return null;
}
return array[index];
}



链表：
public Object get(int index){


if(index<0 || index>=size){//如果索引值小于0或者大于链表长

度，返回空值
return null;
}
Node node = root; //如果符合条件，将根节点赋值给一个

新的节点
for(int i =0;i<index;i++){
node=node.getNext(); //一个一个查找，

不断将节点的下一个值赋给node，最后找到
}

//index-1的时候停止，因为它的下一个就是我么要找的index的值，赋给node

return node.getobj();

}


数组因为有下标，就非常好找，而链表找起来要从头开始遍历。

对于数组队列，我还不能说特别懂，但至少用数组队列来做过一个五子棋，或多或少还

是懂得一些它的用处了，但是链表还不是很熟，用链表排过序，用的选择排序，比数组

方便的多，只要再链表中定义了一个交换元素的方法，选择排序、冒泡排序这些简单的

排序几步就能搞定了。

关于链表的真正用途这些还有待进一步发现和使用。