Go语言视频零基础入门到精通

javalearner

数据结构中的线性表，对应着Collection中的List接口。
在本节中，我们将做以下三件事
   第一：我们先来看看线性表的特征
   第二：自己用java实现List
   第三：对比的线性表、链式表性能，以及自己的List性能与JDKList性能对比  线性表特征：
第一：
     一个特定的线性表，应该是用来存放特定的某一个类型的元素的（元素的“同一性”）

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

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

     
   
  
又：
一.线性表只是数据的一种逻辑结构，其具体存储结构可以为顺序存储结构和链式储存结构来完成，对应可以得到顺序表和链表。  二.对线性表的入表和出表顺序做一定的限定，可以得到特殊的线性表，栈(FILO)和队列（FIFO） （1）自己实现线性表之顺序表
思路：  1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据
2.因为存储的具体对象类型不一定，所以采用泛型操作
3.数组操作优点：
1.通过指针快速定位到下表，查询快速  缺点：
1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据  2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）  具体实现代码如下：

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.             ensureCapacity(current);// 确认容量  
     
106.         validateIndex(index);   
     
107.         Object[] tem = new Object[capacity];// 用一个临时数组作为备份   
     
108.         //开始备份数组   
     
109.         for (int i = 0; i < current; i++) {   
     
110.             if (i < index) {   
     
111.                 tem[i] = this.data[i];   
     
112.             }else if(i==index){   
     
113.                 tem[i]=e;   
     
114.             }else if(i>index){   
     
115.                 tem[i]=this.data[i-1];   
     
116.             }   
     
117.         }   
     
118.         this.data=tem;   
     
119.          current++;
     
120.         return true;   
     
121.     }   
     
122. }

复制代码

（2）自己实现线性表之链表  思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）  链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可  缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表
  实现代码如下：

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.     //在index位置后插入元素
    
29.     public boolean insert(int index, E e) {   
    
30.         Node< E> newNode = new Node< E>(e);   
    
31.         // 得到index处的结点   
    
32.         Node< E> cNode = getNode(index);   
    
33.         newNode.next = cNode.next;   
    
34.         cNode.next = newNode;   
    
35.         size++;   
    
36.         return true;   
    
37.   
    
38.     }   
    
39.   
    
40.     /**  
    
41.      * 遍历当前链表，取得当前索引对应的元素  
    
42.      *   
    
43.      * @return  
    
44.      */  
    
45.     private Node< E> getNode(int index) {   
    
46.         // 先判断索引正确性   
    
47.         if (index > size || index < 0) {   
    
48.             throw new RuntimeException("索引值有错：" + index);   
    
49.         }   
    
50.         Node< E> tem = new Node< E>();   
    
51.         tem = header;   
    
52.         int count = 0;   
    
53.         while (count != index) {   
    
54.             tem = tem.next;   
    
55.             count++;   
    
56.         }   
    
57.         return tem;   
    
58.     }   
    
59.   
    
60.     /**  
    
61.      * 根据索引，取得该索引下的数据  
    
62.      *   
    
63.      * @param index  
    
64.      * @return  
    
65.      */  
    
66.     public E get(int index) {   
    
67.         // 先判断索引正确性   
    
68.         if (index >= size || index < 0) {   
    
69.             throw new RuntimeException("索引值有错：" + index);   
    
70.         }   
    
71.         Node< E> tem = new Node< E>();   
    
72.         tem = header;   
    
73.         int count = 0;   
    
74.         while (count != index) {   
    
75.             tem = tem.next;   
    
76.             count++;   
    
77.         }   
    
78.         E e = tem.e;   
    
79.         return e;   
    
80.     }   
    
81.   
    
82.     public int size() {   
    
83.         return size;   
    
84.     }   
    
85.   
    
86.     /**  
    
87.      * 设置index处结点的值  
    
88.      *   
    
89.      * @param x  
    
90.      * @param e  
    
91.      * @return  
    
92.      */  
    
93.     public boolean set(int index, E e) {   
    
94.         // 先判断索引正确性   
    
95.         if (index > size || index < 0) {   
    
96.             throw new RuntimeException("索引值有错：" + index);   
    
97.         }   
    
98.         Node< E> newNode = new Node< E>(e);   
    
99.         // 得到index处的结点   
    
100.         Node< E> cNode = getNode(index);   
     
101.         cNode.e = e;   
     
102.         return true;   
     
103.     }   
     
104.   
     
105.     /**  
     
106.      * 用来存放数据的结点型内部类  
     
107.      */  
     
108.     class Node< E> {   
     
109.         private E e;// 结点中存放的数据   
     
110.   
     
111.         Node() {   
     
112.         }   
     
113.   
     
114.         Node(E e) {   
     
115.             this.e = e;   
     
116.         }   
     
117.   
     
118.         Node
120.    next;// 用来指向该结点的下一个结点   
     
121.   
     
122.         // 在此结点后加一个结点   
     
123.         void addNext(Node< E> node) {   
     
124.             next = node;   
     
125.         }   
     
126.     }   
     
127.   
     
128. }  
     

复制代码

（3）自己实现线性表之栈
栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)
特点：后进先出 (LIFO)或，先进后出（FILO）
因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈操作进行设定即可  具体实现代码

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

复制代码

至于用链表实现栈，则只需要把保存数据的顺序表改成链表即可，此处就不给出代码了 (4)自己实现线性表之队列  与栈类似
队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。
特点：先进先出 (FIFO)、后进后出 (LILO)  同理，我们也可以调用前面两种线性表，只需要对队列的入队和出队方式进行处理即可

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

复制代码

(5)对比线性表和链式表
前面已经说过顺序表和链式表各自的特点，这里在重申一遍
数组操作
优点：1.通过指针快速定位到下标，查询快速  缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据           2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）  链表操作
优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可  缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。 改进：
链表中我们每次添加一个数据时，都需要遍历整个表，得到表尾，再在表尾添加，这是很不科学的 现改进如下：设立一个Node

  类的成员变量last来指示表尾，这样每次添加时，就不需要再重新遍历得到表尾，改进后add()方法如下

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

复制代码

  


  
   
   
     
     

      
     

      
     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/30/000650046.zip