数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列

数据结构与算法是程序设计的两大基础，大型的IT企业面试时也会出数据结构和算法的题目，

它可以说明你是否有良好的逻辑思维，如果你具备良好的逻辑思维，即使技术存在某些缺陷，面试公司也会认为你很有培养价值，至少在一段时间之后，技术可以很快得到提高。同时，它也是软考的重点，我们需要对这部分的内容进行一下总结。

我们先看一下数据结构和算法的整体内容。

1、线性表

概念：

数据元素的排列方式是线性的。

线性表操作：

理解了顺序表和链表的基本思想之后，线性表的操作是简单，并且网上有很多讲解插入和删除结点的博客，在这里我就不过多的介绍了。

顺序表和链表的对比：

数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列

栈和队列是特殊的线性表，既然特殊就有不同点。

2、栈

基本思想：后进先出（先进后出）即栈中元素被处理时，按后进先出的顺序进行，栈又叫后进先出表（LIFO）。

举例：

日常生活中有很多栈的例子。例如，放在书桌上的一摞书，只能从书顶上拿走一本书，书也只能放在顶上。如下图所示：

数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列

3、队列

基本思想：先进先出即先被接收的元素将先被处理，又叫先进先出表（FIFO）。如下图所示：

举例：

队列的例子，生活中更多。比如：买车票排队，排头最先买到车票，新来的排的队尾；进车站时，安检行李，先进去的最先出来，后进去的后出来。

数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列

总结

线性表真的很简单。

----------------------------------------------------------------------------------------------------

数据结构中的线性表，对应着Collection接口中的List接口。

在本节中，我们将做以下三件事

第一。我们先来看看线性表的特征

第二，自己用JAVA实现List

第三，对比的线性表、链式表性能，以及自己的List性能与JDKList性能对比

线性表特征：

第一，一个特定的线性表，应该是用来存放特定的某一个类型的元素的（元素的“同一性”）

第二，除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最后一个元素外，其他每一个元素有且仅有一个直接后继（元素的“序偶性”）

第三，元素在线性表中的“下标”唯一地确定该元素在表中的相对位置（元素的“索引性”）

又，一.线性表只是数据的一种逻辑结构，其具体存储结构可以为顺序存储结构和链式储存结构来完成，对应可以得到顺序表和链表，

二.对线性表的入表和出表顺序做一定的限定，可以得到特殊的线性表，栈(FILO)和队列（FIFO）

自己实现线性表之顺序表

思路：

1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据

2.因为存储的具体对象类型不一定，所以采用泛型操作

3.数组操作优点：1.通过指针快速定位到下表，查询快速

缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据

2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）

具体实现代码如下

Java代码

/**
*自己用数组实现的线性表
*/
publicclassArrayList<E>{
Object[]data=null;//用来保存此队列中内容的数组
intcurrent; //保存当前为第几个元素的指标
intcapacity; //表示数组大小的指标
/**
*如果初始化时，未声明大小，则默认为10
*/
publicArrayList(){
this(10);
}
/**
*初始化线性表，并且声明保存内容的数组大小
*@paraminitalSize
*/
publicArrayList(intinitalSize){
if(initalSize<0){
thrownewRuntimeException("数组大小错误:"+initalSize);
}else{
this.data=newObject[initalSize];
this.current=0;
capacity=initalSize;
}
}
/**
*添加元素的方法添加前，先确认是否已经满了
*@parame
*@return
*/
publicbooleanadd(Ee){
ensureCapacity(current);//确认容量
this.data[current]=e;
current++;
returntrue;
}
/**
*确认系统当前容量是否满足需要,如果满足，则不执行操作如果不满足，增加容量
*@paramcur当前个数
*/
privatevoidensureCapacity(intcur){
if(cur==capacity){
//如果达到容量极限，增加10的容量，复制当前数组
this.capacity=this.capacity+10;
Object[]newdata=newObject[capacity];
for(inti=0;i<cur;i++){
newdata[i]=this.data[i];
}
this.data=newdata;
}
}
/**
*得到指定下标的数据
*@paramindex
*@return
*/
publicEget(intindex){
validateIndex(index);
return(E)this.data[index];
}
/**
*返回当前队列大小
*@return
*/
publicintsize(){
returnthis.current;
}
/**
*更改指定下标元素的数据为e
*@paramindex
*@parame
*@return
*/
publicbooleanset(intindex,Ee){
validateIndex(index);
this.data[index]=e;
returntrue;
}
/**
*验证当前下标是否合法，如果不合法，抛出运行时异常
*@paramindex下标
*/
privatevoidvalidateIndex(intindex){
if(index<0||index>current){
thrownewRuntimeException("数组index错误："+index);
}
}
/**
*在指定下标位置处插入数据e
*@paramindex下标
*@parame需要插入的数据
*@return
*/
publicbooleaninsert(intindex,Ee){
validateIndex(index);
Object[]tem=newObject[capacity];//用一个临时数组作为备份
//开始备份数组
for(inti=0;i<current;i++){
if(i<index){
tem[i]=this.data[i];
}elseif(i==index){
tem[i]=e;
}elseif(i>index){
tem[i]=this.data[i-1];
}
}
this.data=tem;
returntrue;
}
/** *删除指定下标出的数据<br>
*@paramindex<br>
*@return<br>
*/
publicbooleandelete(intindex){
validateIndex(index);
Object[]tem=newObject[capacity];//用一个临时数组作为备份
//开始备份数组
for(inti=0;i<current;i++){
if(i<index){
tem[i]=this.data[i];
}elseif(i==index){
tem[i]=this.data[i+1];
}elseif(i>index){
tem[i]=this.data[i+1];
}
}
this.data=tem;
returntrue;
}
}

自己实现线性表之链表

思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）

链表操作优点：1.因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可

缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。

实现代码如下

Java代码

/**
*自己用链式存储实现的线性表
*/
publicclassLinkedList<E>{
privateNode<E>header=null;//头结点
intsize=0;//表示数组大小的指标
publicLinkedList(){
this.header=newNode<E>();
}
publicbooleanadd(Ee){
if(size==0){
header.e=e;
}else{
//根据需要添加的内容，封装为结点
Node<E>newNode=newNode<E>(e);
//得到当前最后一个结点
Node<E>last=getNode(size-1);
//在最后一个结点后加上新结点
last.addNext(newNode);
}
size++;//当前大小自增加1
returntrue;
}
publicbooleaninsert(intindex,Ee){
Node<E>newNode=newNode<E>(e);
//得到第N个结点
Node<E>cNode=getNode(index);
newNode.next=cNode.next;
cNode.next=newNode;
size++;
returntrue;
}
/**
*遍历当前链表，取得当前索引对应的元素
*
*@return
*/
privateNode<E>getNode(intindex){
//先判断索引正确性
if(index>size||index<0){
thrownewRuntimeException("索引值有错："+index);
}
Node<E>tem=newNode<E>();
tem=header;
intcount=0;
while(count!=index){
tem=tem.next;
count++;
}
returntem;
}
/**
*根据索引，取得该索引下的数据
*
*@paramindex
*@return
*/
publicEget(intindex){
//先判断索引正确性
if(index>=size||index<0){
thrownewRuntimeException("索引值有错："+index);
}
Node<E>tem=newNode<E>();
tem=header;
intcount=0;
while(count!=index){
tem=tem.next;
count++;
}
Ee=tem.e;
returne;
}
publicintsize(){
returnsize;
}
/**
*设置第N个结点的值
*
*@paramx
*@parame
*@return
*/
publicbooleanset(intindex,Ee){
//先判断索引正确性
if(index>size||index<0){
thrownewRuntimeException("索引值有错："+index);
}
Node<E>newNode=newNode<E>(e);
//得到第x个结点
Node<E>cNode=getNode(index);
cNode.e=e;
returntrue;
}
/**
*用来存放数据的结点型内部类
*/
classNode<e>{
privateEe;//结点中存放的数据
Node<E>next;//用来指向该结点的下一个结点
Node(){}
Node(Ee){
this.e=e;
}
//在此结点后加一个结点
voidaddNext(Node<E>node){
next=node;
}
}
}

自己实现线性表之栈

栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。

允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)
特点：后进先出 (LIFO)或，先进后出（FILO）

因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈操作进行设定即可

具体实现代码

Java代码

/**
*自己用数组实现的栈
*/
publicclassArrayStack<E>{
privateArrayList<E>list=newArrayList<E>();//用来保存数据线性表<br>privateintsize;//表示当前栈元素个数
/**
*入栈操作
*@parame
*/
publicvoidpush(Ee){
list.add(e);
size++;
}
/**
*出栈操作
*@return
*/
publicEpop(){
Ee=list.get(size-1);
size--;
returne;
}
}

至于用链表实现栈，则只需要把保存数据的顺序表改成链表即可，此处就不给出代码了

自己实现线性表之队列

与栈类似

队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。

在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。
特点：先进先出 (FIFO)、后进后出 (LILO)

同理，我们也可以调用前面两种线性表，只需要对队列的入队和出队方式进行处理即可

Java代码

packagecn.javamzd.collection.List;
/**
*用数组实现的队列
*/
publicclassArrayQueue<E>{
privateArrayList<E>list=newArrayList<E>();//用来保存数据的队列
privateintsize;//表示当前栈元素个数
/**
*入队
*@parame
*/
publicvoidEnQueue(Ee){
list.add(e);
size++;
}
/**
*出队
*@return
*/
publicEDeQueue(){
if(size>0){
Ee=list.get(0);
list.delete(0);
returne;
}else{
thrownewRuntimeException("已经到达队列顶部");
}
}
}

对比线性表和链式表
前面已经说过顺序表和链式表各自的特点，这里在重申一遍

数组操作优点：1.通过指针快速定位到下标，查询快速

缺点： 1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据

2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）

链表操作优点：1.因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可

缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。

现在，我们通过进行增删改查操作来感受一次其效率的差异

思路：通过两个表，各进行大数据量操作（3W）条数据的操作，记录操作前系统时间，操作后系统时间，得出操作时间

实现代码如下

Java代码

packagecn.javamzd.collection.List;
publicclassTest{
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
//测试自己实现的ArrayList类和Linkedlist类添加30000个数据所需要的时间
ArrayList<String>al=newArrayList<String>();
LinkedList<String>ll=newLinkedList<String>();
LongaBeginTime=System.currentTimeMillis();//记录BeginTime
for(inti=0;i<30000;i++){
al.add("now"+i);
}
LongaEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("arrylistaddtime--->"+(aEndTime-aBeginTime));
LonglBeginTime=System.currentTimeMillis();//记录BeginTime
for(inti=0;i<30000;i++){
ll.add("now"+i);
}
LonglEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("linkedListaddtime---->"+(lEndTime-lBeginTime));
//测试JDK提供的ArrayList类和LinkedList类添加30000个数据所需要的世界
java.util.ArrayList<String>sal=newjava.util.ArrayList<String>();
java.util.LinkedList<String>sll=newjava.util.LinkedList<String>();
LongsaBeginTime=System.currentTimeMillis();//记录BeginTime
for(inti=0;i<30000;i++){
sal.add("now"+i);
}
LongsaEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("JDKarrylistaddtime--->"+(saEndTime-saBeginTime));
LongslBeginTime=System.currentTimeMillis();//记录BeginTime
for(inti=0;i<30000;i++){
sll.add("now"+i);
}
LongslEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("JDKlinkedListaddtime---->"+(slEndTime-slBeginTime));
}
}

得到测试结果如下：

arrylist add time--->446
linkedList add time---->9767
JDK arrylist add time--->13
JDK linkedList add time---->12

由以上数据，我们可知：

1.JDK中的ArrayList何LinkedList在添加数据时的性能，其实几乎是没有差异的

2.我们自己写的List的性能和JDK提供的List的性能还是存在巨大差异的

3.我们使用链表添加操作，花费的时间是巨大的，比ArrayList都大几十倍

第三条显然是跟我们最初的设计不相符的，按照我们最初的设想，链表的添加应该比顺序表更省时

查看我们写的源码，可以发现：

我们每次添加一个数据时，都需要遍历整个表，得到表尾，再在表尾添加，这是很不科学的

现改进如下：设立一个Node<E>类的成员变量end来指示表尾，这样每次添加时，就不需要再重新遍历得到表尾

改进后add()方法如下

Java代码

publicbooleanadd(Ee){
if(size==0){
header.e=e;
}else{
//根据需要添加的内容，封装为结点
Node<E>newNode=newNode<E>(e);
//在表尾添加元素
last.addNext(newNode);
//将表尾指向当前最后一个元素
last=newNode;
}
size++;//当前大小自增加1
returntrue;
}

ArrayList添加的效率和JDK中对比起来也太低

分析原因为：

每次扩大容量时，扩大量太小，需要进行的复制操作太多

现在改进如下：

每次扩大，则扩大容量为当前的三倍，此改进仅需要更改ensureCapacity()方法中的一行代码，此处就不列出了。

改进后，再次运行添加元素测试代码，结果如下：

arrylist add time--->16
linkedList add time---->8
JDK arrylist add time--->7
JDK linkedList add time---->7

虽然还有改进的空间，但是显然，我们的效果已经大幅度改进了，而且也比较接近JDK了

接下来测试插入操作的效率

我们只需要将测试代码中的添加方法(add())改成插入方法(insert(int index,E e)),为了使插入次数尽可能多，我们把index都设置为0

测试结果如下：

arrylist inset time--->17
linkedList inset time---->13
JDK arrylist inset time--->503
JDK linkedList inset time---->11

多次测试，发现我们写的ArrayList在插入方法的效率都已经超过JDK了，而且也接近LinkedLst了。撒花！！！

数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列

1、线性表

概念：

分类：

（1）顺序表

（2）链表

线性表操作：

顺序表和链表的对比：

2、栈

3、队列

分类：

1.顺序队列

2.循环队列

总结

数据结构与算法 ---- 线性表 及Java实现 顺序表、链表、栈、队列

1、线性表

概念：

分类：

（1）顺序表

（2）链表

线性表操作：

顺序表和链表的对比：

2、栈

3、队列

分类：

1.顺序队列

2.循环队列

总结

相关推荐

数据结构与算法 ---- 线性表及Java实现顺序表、链表、栈、队列