数组队列——当用数组不方便的时候,数组队列是非常方便的。数组队列的长度可改变
,存储数据的类型也可以是多样的。这点是数组所不具备的有优点,所以我们可以用数
组队列来记录比如说五子棋中下过的棋子,所以我觉得数组队列是有“记忆功能”的。
因为它的长度可以改变嘛,所以比如说每下一步棋,长度就可以加一,以前的数据也不
会被覆盖掉。
链表呢是有一个部分用来存储数据,一个部分用来指向下一个地址,这是单链表,还有
双链表和循环链表,这样我们使用起来的时候就很方便了,下面我用代码来比较一下数
组队列和链表。
增加数据:
数组队列: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();
}
数组因为有下标,就非常好找,而链表找起来要从头开始遍历。
对于数组队列,我还不能说特别懂,但至少用数组队列来做过一个五子棋,或多或少还
是懂得一些它的用处了,但是链表还不是很熟,用链表排过序,用的选择排序,比数组
方便的多,只要再链表中定义了一个交换元素的方法,选择排序、冒泡排序这些简单的
排序几步就能搞定了。
关于链表的真正用途这些还有待进一步发现和使用。
分享到:
相关推荐
python利用数组和链表实现栈和队列 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
利用数组和链表实现队列的基本操作,如入队,出队,读出队首元素
队列关于数组与链表的实现, linux c语言
数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
在队列的代码中,引用了链表的代码
常见的数据结构(栈、队列、数组、链表和红黑树) 数组和链表.pdf
数组、链表、队列、栈的区别和联系 数组和链表.pdf
循环链表队列的代码实现 循环数组队列的代码实现
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
超级数组和链表及栈队列
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,下面介绍一下java使用数组和链表实现队列的示例
数组 链表 队列 栈 哈希表 字典树 树 图 算法 I II III IV V VI VII VIII IX X XI XII IX X 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序 递归 查找算法 贪心算法 分治...
两个文件 一个是数组实现循环队列 一个是链表实现 功能是常用的基本功能 希望对大家有所帮助
经过一上午的学习,对数据结构有了新的认识和理解 数组 数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找...
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public: