#include<iostream>
#include<cstdlib>
#define MAXSIZE 100
using namespace std;

发现用链表实现必用数组容易多了:

队列:只能一端进行出栈一端进行进栈。

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

typedef struct Node
{
struct Node *Next;   //队列元素的节点连接 
int Element;
}MyNode;

  • 初始化队列:创建一个指向队列节点的头指针
  • 入队:创建一个新节点,将它添加到链表尾部,如果链表为空,让头指针指向该节点
  • 出队:free 头指针指向第一个节点, 让头指针指向该节点的下一个节点,
    然后返回该节点的值。
  • 判断队列是否为空:如果头指针指向 NULL 则该队列是空队列。

队首:只允许进行出栈操作,可以进行删除。

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

typedef struct Queue
{
Node *Front;          //Front和Rear连接着各自应有的节点 
Node *Rear; 
int Items;            //队列元素的个数,用于判断是否空队列,满队列 
}*PtrToQueue; 

纯C语言实现:

队尾:只允许进行入栈操作,可以进行插入。

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

typedef PtrToQueue MyQueue;

#include <stdio.h>
#include <malloc.h>
#define ERROR -1
#define bool int
#define Flase 0
#define True 1
#define elem_type int


typedef struct _node {
    elem_type data;
    struct _node* next;
} Node;

typedef struct q_node {
    Node* front;
    // Node* rear;  不需要
} Queue;

// 初始化
Queue* create_queue(void)
{
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;

    return q;
}

// 队列是否是空,链表可以一直申请内存一般不会满。
bool is_empty(Queue* q)
{
    return (q->front == NULL);
}

// 出队
elem_type delete_q(Queue* q)
{
    if (q->front != NULL){
        elem_type n;
        Node* p = q->front;     // 记录第一个节点的地址
        n = p->data;        // 记录第一个节点的值
        q->front = p->next;     // 更新头指针指向
        free(p);    // 释放内存

        return n;
    } else {
        return ERROR;
    }
}

// 入队
void add_q(Queue *q, elem_type x)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = x;
    node->next = NULL;

    // 将节点添加到链表尾部
    Node* last = q->front;
    if (last){
        // 寻找最后一个节点
        while (last->next){
            last = last->next;
        }
        // 添加
        last->next = node;
    } else {
        q->front = node;
    }
}

// 输出队列
void print(Queue* q)
{
    Node* p;
    for (p=q->front; p; p = p->next){
        printf("%d ", p->data);
    }
    printf("\n");
}

int main(void)
{
    Queue* Q = NULL;
    Q = create_queue();
    // 才创建的队列应为空
    if (is_empty(Q)){
        printf("队列为空\n");
    }
    int i = 0;
    // 入队 0 1 2 3 4
    while (i<5){
        add_q(Q, i++);
    }
    // 出队 0
    delete_q(Q);
    // 输出 1 2 3 4
    print(Q);
    return 0;
}

队尾进,队尾出,先进先出。

                                     
  图片 1

MyQueue Create(void);  //创建一个队列 
void EnQueue(int X,MyQueue Q); //入队 
void DeQueue(MyQueue Q);       //出队 
int IsFull(MyQueue Q);         //判断是否满队 
int IsEmpty(MyQueue Q);        //判断是否为空队列 
void GetQueueFront(MyQueue Q);
//获得队头元素,当然,也可以获得队尾元素,这里交给你写了 

所以队列的实现也有两种形式,一种是数组实现队列,一种是用链表实现队列。

 

int main() //测试 
{
MyQueue Q=Create();
EnQueue(100,Q); 
DeQueue(Q);      
return 0;
}

图片 2

1、线性表

MyQueue Create(void)
{
MyNode *NewNode;
MyQueue Q;
Q=(MyQueue)malloc(sizeof(struct Queue));  //为MyQueue类型的Q开辟内存 
if(Q==NULL)
   cout <<“空间不足! ” <<endl ;
Q->Front=(MyNode *)malloc(sizeof(MyNode)); //为Q的头节点开辟内存 
if(Q->Front==NULL)
   cout <<“空间不足! ” <<endl ;
Q->Rear=(MyNode *)malloc(sizeof(MyNode));//为Q的尾节点开辟内存
if(Q->Rear==NULL)
   cout <<“空间不足! ” <<endl ;
Q->Front=Q->Rear;   //一开始,头结点就是尾节点 
Q->Items=0;         //队列元素为0 
int a[8]={13,15,17,21,18,38,28,31};
for(int i=0;i<8;i++)
{
NewNode=(MyNode *)malloc(sizeof(MyNode));
   if(NewNode==NULL)
       cout <<“空间不足! ” <<endl ;
   NewNode->Element=a[i];  //赋值 
NewNode->Next=NULL;     //新开辟的节点总是尾节点 
if(Q->Items==0)         //如果入的是空队,先入头节点 
{
Q->Front=NewNode; //队头等于NewNode 
Q->Rear=NewNode;  //队尾也是NewNode 
cout <<Q->Front->Element <<“已入列 ” <<endl ;
Q->Items++; //入队后元素个数+1 
}
else          //如果入的不是空队 
{
   Q->Rear->Next=NewNode;  //从队尾进去 
   Q->Rear=Q->Rear->Next;  //NewNode成为新的队尾元素 
   cout <<Q->Rear->Element <<“已入列 ” <<endl
;
   Q->Items++;  //元素个数+1 
}
}
return Q;
}

首先是用数组来实现队列。

       概念:

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

void EnQueue(int X,MyQueue Q)
{
if(IsFull(Q))
   cout <<“队列已满不能插入! ” <<endl ;
MyNode *NewNode;
NewNode=(MyNode *)malloc(sizeof(MyNode));
if(NewNode==NULL)
   cout <<“空间不足! ” <<endl ;
NewNode->Element=X;
NewNode->Next=NULL;
if(Q->Items==0)         //如果入的是空队,先入头节点 
{
Q->Front=NewNode; //队头等于NewNode 
Q->Rear=NewNode;  //队尾也是NewNode 
cout <<Q->Front->Element <<“已入列 ” <<endl ;
Q->Items++; //入队后元素个数+1 
}
else          //如果入的不是空队 
{
   Q->Rear->Next=NewNode;  //从队尾进去 
   Q->Rear=Q->Rear->Next;  //NewNode成为新的队尾元素 
   cout <<Q->Rear->Element <<“已入列 ” <<endl
;
   Q->Items++;  //元素个数+1 
}
cout <<“入队后 ” ; 
GetQueueFront(Q);
}

使用数组队列,因为在删除时front会越来越大,所以最后会出现一种还有空间但是却显示无空间的现象。

      分类:

             分类规则是根据上图中元素的存储结构来划分的。

                                                         
 图片 3                        

void DeQueue(MyQueue Q)
{
if(IsEmpty(Q))
   cout <<“空队列 !” <<endl ;
else
{
MyNode *Deletion; 
   Deletion=Q->Front;  //Deletion是方便释放头节点的内存 
   Q->Front=Q->Front->Next;  //队头的下一个元素成为新的队头 
   delete Deletion;          //释放
   Q->Items–;               //出队后,元素个数-1 
   if(Q->Items==0)
   Q->Rear=NULL;
   cout <<“出队后 ” ; 
   GetQueueFront(Q);
}
}

解决方法:

      (1)顺序表

       
  基本思想:元素的存储空间是连续的。在内存中是以顺序存储,内存划分的区域是连续的。存储结构如下图:

                           图片 4

          

int IsFull(MyQueue Q)
{
return Q->Items==MAXSIZE;      
 //MAXSIZE根据需求定义,如果元素个数为MAXSIZE就返回1,否则返回0 
}

构建循环队列,算法为:

      (2)链表

          基本思想:元素的存储空间是离散的,单独的(物理),它们可以通过在逻辑上指针的联系使得它成为了整体的链表。存储结构如下图:

                             
  图片 5

 

     

            1.单链表

                   图片 6

图片 7

 

            2.循环链表

                        图片 8·

图片 9

            3.双链表(双向循环表)

                   图片 10

                 (图有点小问题 :最后一个节点的 指针域
也指向头结点)

图片 11

           

 

           三者的区别(从上面三个图我们可以总结出来):

     
 1、它们都有数据域(data(p))和指针域(next(p)),但是从图中可以看出双链表有两个指针域,一个指向它的前节点,一个指向它的后节点。

     
 2、单链表最后一个节点的指针域为空,没有后继节点;循环链表和双链表最后一个节点的指针域指向头节点,下一个结点为头节点,构成循环;

       
  3、单链表和循环链表只可向一个方向遍历;双链表和循环链表,首节点和尾节点被连接在一起,可视为“无头无尾”;双链表可以向两个方向移动,灵活度更大。

 

int IsEmpty(MyQueue Q)
{
return Q->Items==0;  //如果队列元素为0则返回1,否则返回0 
}

判断是否队满:(rear+1)%a.length==front 
//如果相等的话则证明队列已满

    线性表操作:

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

 

void GetQueueFront(MyQueue Q)
{
if(IsEmpty(Q))
   cout <<“空队列 !” <<endl ;
else
   cout <<Q->Front->Element <<“为队头 ” <<endl
<<endl ; //输出队头元素 
}

rear=(rear+1)%a.length;       //创建循环

        顺序表和链表的对比:

                          图片 12

 

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

 

实现代码:

2、栈

      基本思想:后进先出(先进后出)即栈中元素被处理时,按后进先出的顺序进行,栈又叫后进先出表(LIFO)。

      举例:

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

                                               
 图片 13

 

 1     public class Queue {  
 2         private static final int defaultSize = 10;  
 3         private Node[] a;  
 4         private int rear;  
 5         private int front;  
 6         Queue(){                //默认构造方法  
 7             a = new Node[10];  
 8             rear = 0;  
 9             front = 0;  
10         }  
11         Queue(int n){           //指定队列长度的构造方法  
12             a = new Node[n];  
13             rear = 0;  
14             front = 0;  
15         }  
16         public boolean add(Node node){          //在队尾增加队列节点  
17             if((rear+1) % a.length == front )       //检测该对列是否已经满了  
18                 return false;  
19             else{  
20                 a[rear] = node;  
21                 rear = (rear+1) % a.length;     //构建循环队列      
22                 return true;  
23             }     
24         }  
25         public Node remove(){                   //删除对首节点  
26             if(rear == front)  
27                 return null;  
28             else{  
29                 Node n = a[front];  
30                 front = (front+1) % a.length;  
31                 return n;  
32             }     
33         }  
34         public boolean isEmpty(){               //检测是否为空  
35             if(rear == front)  
36                 return true;  
37             else   
38                 return false;  
39         }  
40         public int size(){              //返回队列长度  
41             return a.length;  
42         }  
43     }  

3、队列

     基本思想:先进先出即先被接收的元素将先被处理,又叫先进先出表(FIFO)。如下图所示:

     举例:

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

                                               
  图片 14

   

 

分类:

1.顺序队列

          如下图所示:

                          图片 15

      顺序队列的操作,要判断队满和队空的标志,从图中我们可以总结得到:

      1.队空:head = tail

      2.队满:tail = m

2.循环队列

        如下图所示:

                               
  图片 16

      循环队列的操作,要判断队空和队满的情况,从图中我们可以总结得到:

         1.队空:head = tail

       2.队满:tail + 1 = head(在队列中会留一个空着的空间,所以要加1)

 

总结

           线性表真的很简单。

 


 

 

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

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

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

            第二,自己用JAVA实现List

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

 

      线性表特征: 

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

            第二,
除第一个元素外,其他每一个元素有且仅有一个直接前驱;除最后一个元素外,其他每一个元素有且仅有一个直接后继(元素的“序偶性”)

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

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

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

 

    自己实现线性表之顺序表

             思路:

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

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

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

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

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

  具体实现代码如下

Java代码

  1. /** 
  2.  * 自己用数组实现的线性表 
  3.  */  
  4. public class ArrayList<E> {  
  5.     Object[] data = null;// 用来保存此队列中内容的数组  
  6.     int current;        // 保存当前为第几个元素的指标  
  7.     int capacity;        // 表示数组大小的指标  
  8.        
  9.     /** 
  10.      * 如果初始化时,未声明大小,则默认为10 
  11.      */  
  12.     public ArrayList() {  
  13.         this(10);  
  14.     }  
  15.   
  16.     /** 
  17.      * 初始化线性表,并且声明保存内容的数组大小 
  18.      * @param initalSize 
  19.      */  
  20.     public ArrayList(int initalSize) {  
  21.         if (initalSize < 0) {  
  22.             throw new RuntimeException(“数组大小错误:” + initalSize);  
  23.         } else {  
  24.             this.data = new Object[initalSize];  
  25.             this.current = 0;  
  26.             capacity = initalSize;  
  27.         }  
  28.     }  
  29.   
  30.     /** 
  31.      * 添加元素的方法 添加前,先确认是否已经满了 
  32.      * @param e 
  33.      * @return 
  34.      */  
  35.     public boolean add(E e) {  
  36.         ensureCapacity(current);// 确认容量  
  37.         this.data[current] = e;  
  38.         current++;  
  39.         return true;  
  40.     }  
  41.   
  42.     /** 
  43.      * 确认系统当前容量是否满足需要,如果满足,则不执行操作 如果不满足,增加容量 
  44.      * @param cur 当前个数 
  45.      */  
  46.     private void ensureCapacity(int cur) {  
  47.         if (cur == capacity) {  
  48.             // 如果达到容量极限,增加10的容量,复制当前数组  
  49.             this.capacity = this.capacity + 10;  
  50.             Object[] newdata = new Object[capacity];  
  51.             for (int i = 0; i < cur; i++) {  
  52.                 newdata[i] = this.data[i];  
  53.             }  
  54.             this.data = newdata;  
  55.         }  
  56.     }  
  57.   
  58.     /** 
  59.      * 得到指定下标的数据 
  60.      * @param index 
  61.      * @return 
  62.      */  
  63.     public E get(int index) {  
  64.         validateIndex(index);  
  65.         return (E) this.data[index];  
  66.     }  
  67.        
  68.    /** 
  69.     * 返回当前队列大小
  70.     * @return 
  71.     */  
  72.     public int size() {  
  73.         return this.current;  
  74.     }  
  75.   
  76.     /** 
  77.      * 更改指定下标元素的数据为e 
  78.      * @param index  
  79.      * @param e 
  80.      * @return 
  81.      */  
  82.     public boolean set(int index, E e) {  
  83.         validateIndex(index);  
  84.         this.data[index] = e;  
  85.         return true;  
  86.     }  
  87.      
  88.     /** 
  89.      *  验证当前下标是否合法,如果不合法,抛出运行时异常 
  90.      * @param index 下标 
  91.      */  
  92.     private void validateIndex(int index) {  
  93.         if (index < 0 || index > current) {  
  94.             throw new RuntimeException(“数组index错误:” + index);  
  95.         }  
  96.     }  
  97.   
  98.     /** 
  99.      * 在指定下标位置处插入数据e 
  100.      * @param index 下标 
  101.      * @param e 需要插入的数据 
  102.      * @return  
  103.      */  
  104.     public boolean insert(int index, E e) {  
  105.         validateIndex(index);  
  106.         Object[] tem = new Object[capacity];// 用一个临时数组作为备份  
  107.         //开始备份数组  
  108.         for (int i = 0; i < current; i++) {  
  109.             if (i < index) {  
  110.                 tem[i] = this.data[i];  
  111.             }else if(i==index){  
  112.                 tem[i]=e;  
  113.             }else if(i>index){  
  114.                 tem[i]=this.data[i-1];  
  115.             }  
  116.         }  
  117.         this.data=tem;  
  118.         return true;  
  119.     }  
  120.      /**
     * 删除指定下标出的数据<br>    
  121.       * @param index<br>  
  122.       * @return<br>   
  123.       */
  124.      public boolean delete(int index){
  125.           validateIndex(index);
  126.           Object[] tem = new Object[capacity];// 用一个临时数组作为备份
  127.           //开始备份数组
  128.          for (int i = 0; i < current; i++) { 
  129.                 if (i < index) {
  130.                    
    tem[i] = this.data[i];
  131.                 }else if(i==index){
  132.                    
    tem[i]=this.data[i+1];
  133.                 }else if(i>index){
  134.                    
    tem[i]=this.data[i+1];
  135.                 }
  136.             }
  137.           this.data=tem;
  138.           return true;
  139.      }
  140. }  

 

   自己实现线性表之链表

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

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

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

  实现代码如下

Java代码  图片 17

  1. /** 
  2.  * 自己用链式存储实现的线性表 
  3.  */  
  4. public class LinkedList<E> {  
  5.   
  6.     private Node<E> header = null;// 头结点  
  7.     int size = 0;// 表示数组大小的指标  
  8.   
  9.     public LinkedList() {  
  10.         this.header = new Node<E>();  
  11.     }  
  12.   
  13.     public boolean add(E e) {  
  14.         if (size == 0) {  
  15.             header.e = e;  
  16.         } else {  
  17.             // 根据需要添加的内容,封装为结点  
  18.             Node<E> newNode = new Node<E>(e);  
  19.             // 得到当前最后一个结点  
  20.             Node<E> last = getNode(size-1);  
  21.             // 在最后一个结点后加上新结点  
  22.             last.addNext(newNode);  
  23.         }  
  24.         size++;// 当前大小自增加1  
  25.         return true;  
  26.     }  
  27.   
  28.     public boolean insert(int index, E e) {  
  29.         Node<E> newNode = new Node<E>(e);  
  30.         // 得到第N个结点  
  31.         Node<E> cNode = getNode(index);  
  32.         newNode.next = cNode.next;  
  33.         cNode.next = newNode;  
  34.         size++;  
  35.         return true;
     
  36.     }  
  37.   
  38.     /** 
  39.      * 遍历当前链表,取得当前索引对应的元素 
  40.      *  
  41.      * @return 
  42.      */  
  43.     private Node<E> getNode(int index) {  
  44.         // 先判断索引正确性  
  45.         if (index > size || index < 0) {  
  46.             throw new RuntimeException(“索引值有错:” + index);  
  47.         }  
  48.         Node<E> tem = new Node<E>();  
  49.         tem = header;  
  50.         int count = 0;  
  51.         while (count != index) {  
  52.             tem = tem.next;  
  53.             count++;  
  54.         }  
  55.         return tem;  
  56.     }  
  57.   
  58.     /** 
  59.      * 根据索引,取得该索引下的数据 
  60.      *  
  61.      * @param index 
  62.      * @return 
  63.      */  
  64.     public E get(int index) {  
  65.         // 先判断索引正确性  
  66.         if (index >= size || index < 0) {  
  67.             throw new RuntimeException(“索引值有错:” + index);  
  68.         }  
  69.         Node<E> tem = new Node<E>();  
  70.         tem = header;  
  71.         int count = 0;  
  72.         while (count != index) {  
  73.             tem = tem.next;  
  74.             count++;  
  75.         }  
  76.         E e = tem.e;  
  77.         return e;  
  78.     }  
  79.   
  80.     public int size() {  
  81.         return size;  
  82.     }  
  83.   
  84.     /** 
  85.      * 设置第N个结点的值 
  86.      *  
  87.      * @param x 
  88.      * @param e 
  89.      * @return 
  90.      */  
  91.     public boolean set(int index, E e) {  
  92.         // 先判断索引正确性  
  93.         if (index > size || index < 0) {  
  94.             throw new RuntimeException(“索引值有错:” + index);  
  95.         }  
  96.         Node<E> newNode = new Node<E>(e);  
  97.         // 得到第x个结点  
  98.         Node<E> cNode = getNode(index);  
  99.         cNode.e = e;  
  100.         return true;  
  101.     }  
  102.   
  103.     /** 
  104.      * 用来存放数据的结点型内部类 
  105.      */  
  106.     class Node<e> {  
  107.         private E e;// 结点中存放的数据  
  108.         Node<E> next;// 用来指向该结点的下一个结点 
  109.         
  110. Node() { }  
  111.         Node(E e) {  
  112.             this.e = e;  
  113.         }  
  114.         // 在此结点后加一个结点  
  115.         void addNext(Node<E> node) {  
  116.             next = node;  
  117.         }  
  118.     }  
  119. }  

 

自己实现线性表之栈

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

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

 

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

    具体实现代码

Java代码  图片 18

  1. /** 
  2.  * 自己用数组实现的栈 
  3.  */  
  4. public class ArrayStack<E> {  
  5.       private ArrayList<E> list=new ArrayList<E>();//用来保存数据线性表<br>    private  int size;//表示当前栈元素个数  
  6.       /** 
  7.        * 入栈操作 
  8.        * @param e 
  9.        */  
  10.       public void push(E e){  
  11.           list.add(e);  
  12.           size++;  
  13.       }  
  14.        
  15.       /** 
  16.        * 出栈操作 
  17.        * @return 
  18.        */  
  19.       public E pop(){  
  20.          E e= list.get(size-1);  
  21.          size–;  
  22.          return e;  
  23.       }  
  24.   
  25. }  

 

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

 

自己实现线性表之队列

        与栈类似

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

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

 

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

 

Java代码  图片 19

  1. package cn.javamzd.collection.List;  
  2.   
  3. /** 
  4.  * 用数组实现的队列 
  5.  */  
  6. public class ArrayQueue<E> {  
  7.     private ArrayList<E> list = new ArrayList<E>();// 用来保存数据的队列  
  8.     private int size;// 表示当前栈元素个数  
  9.   
  10.     /** 
  11.      * 入队 
  12.      * @param e 
  13.      */  
  14.     public void EnQueue(E e) {  
  15.         list.add(e);  
  16.         size++;  
  17.     }  
  18.   
  19.     /** 
  20.      * 出队 
  21.      * @return 
  22.      */  
  23.     public E DeQueue() {  
  24.         if (size > 0) {  
  25.             E e = list.get(0);  
  26.             list.delete(0);  
  27.             return e;  
  28.         }else{  
  29.             throw new RuntimeException(“已经到达队列顶部”);  
  30.         }  
  31.     }  
  32. }  

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

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

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

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

 

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

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

 

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

       
 思路:通过两个表,各进行大数据量操作(3W)条数据的操作,记录操作前系统时间,操作后系统时间,得出操作时间

  实现代码如下

 

Java代码  图片 20

  1. package cn.javamzd.collection.List;  
  2.   
  3. public class Test {  
  4.   
  5.     /** 
  6.      * @param args 
  7.      */  
  8.     public static void main(String[] args) {  
  9.         //测试自己实现的ArrayList类和Linkedlist类添加30000个数据所需要的时间  
  10.         ArrayList<String> al = new ArrayList<String>();  
  11.         LinkedList<String> ll = new LinkedList<String>();  
  12.         Long aBeginTime=System.currentTimeMillis();//记录BeginTime  
  13.         for(int i=0;i<30000;i++){  
  14.             al.add(“now”+i);  
  15.         }  
  16.         Long aEndTime=System.currentTimeMillis();//记录EndTime  
  17.         System.out.println(“arrylist  add time—>”+(aEndTime-aBeginTime));  
  18.         Long lBeginTime=System.currentTimeMillis();//记录BeginTime  
  19.         for(int i=0;i<30000;i++){  
  20.             ll.add(“now”+i);  
  21.         }  
  22.         Long lEndTime=System.currentTimeMillis();//记录EndTime  
  23.         System.out.println(“linkedList add time—->”+(lEndTime-lBeginTime));  
  24.           
  25.         //测试JDK提供的ArrayList类和LinkedList类添加30000个数据所需要的世界  
  26.         java.util.ArrayList<String> sal=new java.util.ArrayList<String>();  
  27.         java.util.LinkedList<String> sll=new java.util.LinkedList<String>();  
  28.         Long saBeginTime=System.currentTimeMillis();//记录BeginTime  
  29.         for(int i=0;i<30000;i++){  
  30.             sal.add(“now”+i);  
  31.         }  
  32.         Long saEndTime=System.currentTimeMillis();//记录EndTime  
  33.         System.out.println(“JDK arrylist  add time—>”+(saEndTime-saBeginTime));  
  34.         Long slBeginTime=System.currentTimeMillis();//记录BeginTime  
  35.         for(int i=0;i<30000;i++){  
  36.             sll.add(“now”+i);  
  37.         }  
  38.         Long slEndTime=System.currentTimeMillis();//记录EndTime  
  39.         System.out.println(“JDK linkedList add time—->”+(slEndTime-slBeginTime));  
  40.     }  
  41.   
  42. }  

  得到测试结果如下: 

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代码  

  1. public boolean add(E e) {  
  2.     if (size == 0) {  
  3.         header.e = e;  
  4.     } else {  
  5.         // 根据需要添加的内容,封装为结点  
  6.         Node<E> newNode = new Node<E>(e);  
  7.         //在表尾添加元素  
  8.         last.addNext(newNode);  
  9.                                         //将表尾指向当前最后一个元素  
  10.         last = newNode;  
  11.     }  
  12.     size++;// 当前大小自增加1  
  13.     return true;  
  14. }  

       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了。撒花!!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图