淺析線性表的原理及簡單實現

一、線性表

原理：零個或多個同類數據元素的有限序列

原理圖：

特點 ： 

1、有序性

2、有限性

3、同類型元素

4、第一個元素無前驅，最後一個元素無後繼，中間的元素有一個前驅並且有一個後繼

線性表是一種邏輯上的數據結構，在物理上一般有兩種實現 順序實現和鏈表實現 

二、基於數組的 線性表順序實現

原理 ： 用一段地址連續的存儲單元依次存儲線性表數據元素。

原理圖：

演算法原理：

1、初始化一個定長的數組空間 elementData[] , size 存儲長度 存儲元素

2、通過索引來快速存取元素

3、通過數組複製實現元素的插入和刪除

總結：

1、無需為表示表中元素之間的邏輯關係增加額外的存儲空間

2、可以快速存取表中任一位置元素

3、插入和刪除需要進行數組複製（即大量元素的移動）

4、線性表長度變化較大時，需要頻繁擴容，並造成存儲空間碎片

實現代碼：

介面定義：

 1 package online.jfree.base.container;
 2 
 3 /**
 4  * author : Guo LiXiao
 5  * date : 2017-6-14  11:46
 6  */
 7 
 8 public interface LineList <E>{
 9 
10     /**
11      * lineList 是否為空
12      * @return
13      */
14     boolean isEmpty();
15 
16     /**
17      * 清空 lineList
18      */
19     void clear();
20 
21     /**
22      * 獲取指定位置元素
23      * @param index
24      * @return
25      */
26     E get(int index);
27 
28     /**
29      * 獲取元素第一次出現的位置
30      * @param e
31      * @return
32      */
33     int indexOf(E e);
34 
35     /**
36      * 判斷 lineList是否包含指定元素
37      * @param e
38      * @return
39      */
40     boolean contains(E e);
41 
42     /**
43      * 設置指定位置數據，如數據已存在 則覆蓋原數據
44      * @param index
45      * @param e
46      * @return
47      */
48     E set(int index, E e);
49 
50     /**
51      * 移除指定位置元素
52      * @param index
53      * @return
54      */
55     E remove(int index);
56 
57     /**
58      * 在lineList結尾插入元素
59      * @param e
60      * @return
61      */
62     E add(E e);
63 
64     /**
65      * 在index後面插入元素
66      * @param index
67      * @param e
68      * @return
69      */
70     E add(int index, E e);
71 
72     /**
73      * 返回lineList長度
74      * @return
75      */
76     int size();
77 
78 
79 
80 }

 1 package online.jfree.base.container.list;
 2 
 3 import online.jfree.base.container.LineList;
 4 
 5 /**
 6  * author : Guo LiXiao
 7  * date : 2017-6-19  10:16
 8  */
 9 
10 public abstract class AbstractLineList<E> implements LineList<E> {
11 
12     protected int size;
13 
14     protected abstract void init();
15 
16     @Override
17     public boolean isEmpty() {
18         return this.size == 0;
19     }
20 
21     @Override
22     public void clear() {
23         init();
24     }
25 
26     @Override
27     public int size() {
28         return this.size;
29     }
30 
31     @Override
32     public boolean contains(E e) {
33         return indexOf(e) > 0;
34     }
35 }

演算法實現：

  1 package online.jfree.base.container.list;
  2 
  3 import online.jfree.base.container.LineList;
  4 
  5 /**
  6  * 線性表的順序存儲結構
  7  * author : Guo LiXiao
  8  * date : 2017-6-15  13:44
  9  */
 10 
 11 public class OrderedLineList<E> extends AbstractLineList<E> implements LineList<E> {
 12 
 13     private static final int INIT_CAPACITY = 10;
 14 
 15     private transient E[] elementData;
 16 
 17     private transient int elementLength;
 18 
 19     public OrderedLineList() {
 20         init(0);
 21     }
 22 
 23     private void init(int initCapacity) {
 24         if (initCapacity >= 0) {
 25             this.elementData = (E[]) new Object[initCapacity];
 26             this.elementLength = initCapacity;
 27         } else
 28             throw new IllegalArgumentException("Illegal Capacity: " +
 29                     initCapacity);
 30 
 31         this.size = 0;
 32     }
 33 
 34     @Override
 35     protected void init(){
 36         init(0);
 37     }
 38 
 39     /**
 40      * 擴容
 41      */
 42     private void dilatation() {
 43         int oldCapacity = this.elementLength;
 44         int newCapacity = oldCapacity;
 45         if (oldCapacity <= this.size)
 46             newCapacity = oldCapacity + INIT_CAPACITY;
 47         else if(oldCapacity - INIT_CAPACITY > this.size)
 48             newCapacity = oldCapacity - INIT_CAPACITY;
 49         if (oldCapacity != newCapacity){
 50             E[] newElementData = (E[]) new Object[newCapacity];
 51             System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);
 52             this.elementLength = newCapacity;
 53             this.elementData = newElementData;
 54         }
 55     }
 56 
 57     /**
 58      * 校驗列表索引越界
 59      * @param index
 60      */
 61     private void checkCapacity(int index){
 62         if (index > this.size - 1 || index < 0)
 63             throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString());
 64     }
 65 
 66     @Override
 67     public E get(int index) {
 68         this.checkCapacity(index);
 69         return this.elementData[index];
 70     }
 71 
 72     @Override
 73     public int indexOf(E e) {
 74         for (int i = 0; i < this.size; i++)
 75             if (e == null && elementData[i] == null || e.equals(elementData[i]))
 76                 return i;
 77         return -1;
 78     }
 79 
 80     @Override
 81     public E set(int index, E e) {
 82         this.checkCapacity(index);
 83         this.dilatation();
 84         E oldElement = this.elementData[index];
 85         this.elementData[index] = e;
 86         return oldElement;
 87     }
 88 
 89     @Override
 90     public E remove(int index) {
 91         this.dilatation();
 92         E e = elementData[index];
 93         if (index == size - 1) elementData[index] = null;
 94         else {
 95             int length = size - index - 1;
 96             System.arraycopy(elementData, index + 1, elementData, index, length);
 97         }
 98         size --;
 99         return e;
100     }
101 
102     @Override
103     public E add(E e) {
104         return this.add(size, e);
105     }
106 
107     @Override
108     public E add(int index, E e) {
109         this.dilatation();
110         if (index == size) elementData[index] = e;
111         else {
112             index++;
113             int lastLength = size - index;
114             E[] lastElementData = (E[]) new Object[lastLength];
115             System.arraycopy(elementData, index, lastElementData, 0, lastLength);
116             elementData[index] = e;
117             System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength);
118         }
119         size ++ ;
120         return e;
121     }
122 }