线性表 及Java实现 顺序表、链表、栈、队列

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

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

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

1、线性表

       概念：

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

      分类：

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

      （1）顺序表

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

      （2）链表

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

            1.单链表

            2.循环链表

                        ·

            3.双链表（双向循环表）

                 （图有点小问题 ：最后一个节点的 指针域 也指向头结点）

           三者的区别（从上面三个图我们可以总结出来）：

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

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

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

    线性表操作：

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

        顺序表和链表的对比：

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

2、栈

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

      举例：

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

3、队列

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

     举例：

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

分类：

1.顺序队列

          如下图所示：

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

      1.队空：head = tail

      2.队满：tail = m

2.循环队列

        如下图所示：

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

         1.队空：head = tail

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

总结

           线性表真的很简单。

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

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

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

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

            第二，自己用JAVA实现List

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

      线性表特征： 

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

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

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

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

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

    自己实现线性表之顺序表

             思路：

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

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

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

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

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

  具体实现代码如下

   自己实现线性表之链表

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

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

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

  实现代码如下

Java代码  

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

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

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

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. }  

  得到测试结果如下： 

 由以上数据，我们可知：

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

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

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

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

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

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

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

      改进后add()方法如下

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

       分析原因为：

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

       现在改进如下：

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

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

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

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

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

测试结果如下：

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

本文转自农夫山泉别墅博客园博客，原文链接：http://www.cnblogs.com/yaowen/p/4272310.html，如需转载请自行联系原作者