数据结构----数组队列和链表的总结和心得

数据结构----数组队列和链表的总结和心得

 

最近一段时间，除了做一个消灭星星的小游戏外（这个在之后的博文中再提到），就一直在学习数据结构方面的知识。

小女纸在大二下学期的时候系统的学习了数据结构。自我感觉数据结构这门专业课还是比较得心应手的。在最近学习Java的过程中，又接触到了数据结构中的数组队列和链表，感觉思路还是比较清晰。下面对数组队列和链表进行总结。

 

一、数组队列

1.数组的特点：

1）<顺序存储，内存空间中的地址也是连续的

2）可以通过下标方便查找到具体的元素，但是插入和删除元素比较困难

3）长度固定，不可更改

4）类型固定

 

 

2.数组的实现方式

1）数据类型[] 数组名=new 数据类型[固定长度]:

2）数据类型[] 数组名=new 数据类型[]{1,2，...}:

3）数据类型[] 数组名:

数组名=new 数据类型[固定长度]

Or 数组名=new 数据类型{1,2，...}:

4）数据类型[] 数组名={1,2，...}:

 

 

3.数组队列的主要思想

在一个数组长度为0的数组里，每添加一个数据，就将原来的数组指向一个新建的长度+1的新数组（这个新数组为另外开辟空间的数组。长度为原长+1.）

 

二、链表

1.链表的特点：

1）内存地址不连续

2）不方便找到具体的元素（依次遍历），但是在指定元素后面插入删除很方便

3）长度不固定，任意增添删除节点

 

 

2.链表的实现方式：

1）单链表：一个数据域，一个引用域

2）双链表：一个数据域，两个个引用域（分别指前后）

3）循环链表：一个数据域，两个引用域，首尾节点相连

 

3.链表的主要思想 

通过每个节点的引用很好的找到下一个节点的数据域。添加和删除也只需改变节点引用的指向。

 

 

三、数组队列和链表的比较

前面的特点和实现分析我觉得已经很清楚了。

在这里说一点其他的。

1.如果数据经常需要用到添加或删除，最好选择--------链表

2.如果数据长度固定，且经常用到查找操作，那么最好选择---数组队列

 

个人觉得数组队列的效率非常低，每一次添加数据都会去新建一个新的数组。

但是也不排除数组队列在某些时候非常需要。因此需要综合考虑后再作出选择！

 

四、数组队列类的Java 代码（只包括添加和获取操作）

public class ArrayQueue {

 

 

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

private int size=0;

 

 

public void add(Object obj)             //数组队列中添加结点

{

 

if(size==0)

{

size++;

arrayqueue=new Object[size];

arrayqueue[0]=obj;

}

size++;

Object[] array=new Object[size];

for(int i=0;i<size-1;i++)

array[i]=arrayqueue[i];

array[size-1]=obj;

arrayqueue=array;

}

 

 

public Object get(int index)               //获取index位置的对象

{

return arrayqueue[index];

}

 

 

public Object remove(int index)                 //删除index位置的object对象，并且返回该位置对象

{

if(index==size)

{

size--;

}

Object obj=arrayqueue[index];

for(int i=index;i<size-1;i++)

arrayqueue[i]=arrayqueue[i+1];

size--;

return obj;

 

}

public int getsize()                    //获取长度

{

return size;

}

}

 

 

五、链表类的Java代码实现（包含添加、删除、获取等操作）

 

public class LinkList {

 

private Node front;

private Node rear;

private int length=0;

public void add(Object obj)      //在链表中添加节点 传进来的是！student对象！

{

Node node=new Node(obj);

if(front==null)

{

front=node;

rear=front;

}

else

{

rear.next=node;

rear=node;

 

}

length++;

}

 

 

public Object  get(int index)                //获取index位的结点的student对象

{

if(index<0||index>length)

//System.out.println("超出范围");

throw new RuntimeException("超出范围");              //越界的一个异常提示！

 

Node node=front;

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

node=node.next;

   return node.obj ;

}

 

public Node getNode(int index)

{

Node node=front;

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

node=node.next;

return node;

}

 

public Object remove(int index)

{

if(index<0||index>length)

//System.out.println("超出范围");

throw new RuntimeException("超出范围");              //越界的一个异常提示！

 

Node node=front;

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

node=node.next;

Node nodetemp=node.next;

node.next=nodetemp.next;

length--;

return nodetemp.obj;

}

 

 

 

 

public int remove(Object obj)                            //通过查找数据移除节点。返回删掉的节点的个数count

{

int count=0;

int i=0;

Node node=front;

while(node!=null)

{

Student stu=(Student)node.obj;

Student stu2=(Student)obj;

if(stu.getName().equals(stu2.getName())&&stu.getScore()==stu2.getScore())         //如果相等

{

count++;

 

if(i==0)                                                                                 //分类处理：与头结点相等，与尾节点相等，中间的。

{

front=node.next;

}

else if(i==length-1){

Node nodetemp=getNode(i-1);

nodetemp.next=null;

}

else{

Node nodetemp=getNode(i-1);

nodetemp.next=getNode(i+1);

}

i--;

length--;

}

node=node.next;

i++;

}

return count;

}

 

public void input(Object obj,int index)                 //在index的位置上插入一个节点

{

Node node=new Node(obj);

Node nodetemp=front;

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

nodetemp=nodetemp.next;               //得到index-1位置的结点

 

node.next=nodetemp.next;                 //在index的位置插入。前后连起来

nodetemp.next=node;

 

length++;

 

 

}

 

 

public void modify(int index,Object obj)                 //修改index位置的数据域为obj

{

Node node=front;

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

{

node=node.next;

}

node.obj=obj;

}

 

public void bianli()                                //遍历每个链表节点的数据，并打印

{

Node node=front;

((Student)(front.obj)).ToString();

for(int i=0;i<length-1;i++)

{

node=node.next;

((Student)(node.obj)).ToString();

}

}

 

public int getlength()              //获取链表的长度

{

return length;

}

 

}

<!--EndFragment-->