一、线性表
原理：零个或多个同类数据元素的有限序列
原理图：
特点 ： 
1、有序性
2、有限性
3、同类型元素
4、第一个元素无前驱，最后一个元素无后继，中间的元素有一个前驱并且有一个后继
线性表是一种逻辑上的数据结构，在物理上一般有两种实现 顺序实现和链表实现
二、基于数组的 线性表顺序实现
原理 ： 用一段地址连续的存储单元依次存储线性表数据元素。
原理图：
算法原理：
1、初始化一个定长的数组空间 elementdata[] , size 存储长度 存储元素
2、通过索引来快速存取元素
3、通过数组复制实现元素的插入和删除
总结：
1、无需为表示表中元素之间的逻辑关系增加额外的存储空间
2、可以快速存取表中任一位置元素
3、插入和删除需要进行数组复制（即大量元素的移动）
4、线性表长度变化较大时，需要频繁扩容，并造成存储空间碎片
实现代码：
接口定义：
 1 package online.jfree.base; 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      * @return13      */14     boolean isempty();15 16     /**17      * 清空 linelist18      */19     void clear();20 21     /**22      * 获取指定位置元素23      * @param index24      * @return25      */26     e get(int index);27 28     /**29      * 获取元素第一次出现的位置30      * @param e31      * @return32      */33     int indexof(e e);34 35     /**36      * 判断 linelist是否包含指定元素37      * @param e38      * @return39      */40     boolean contains(e e);41 42     /**43      * 设置指定位置数据，如数据已存在 则覆盖原数据44      * @param index45      * @param e46      * @return47      */48     e set(int index, e e);49 50     /**51      * 移除指定位置元素52      * @param index53      * @return54      */55     e remove(int index);56 57     /**58      * 在linelist结尾插入元素59      * @param e60      * @return61      */62     e add(e e);63 64     /**65      * 在index后面插入元素66      * @param index67      * @param e68      * @return69      */70     e add(int index, e e);71 72     /**73      * 返回linelist长度74      * @return75      */76     int size();77 78 79 80 }
view code
算法实现：
  1 package online.jfree.base;  2   3 /**  4  * author : guo lixiao  5  * date : 2017-6-15  13:44  6  */  7   8 public class orderedlinelist<e> implements linelist<e> {  9  10     private static final int init_capacity = 10; 11  12     private transient e[] elementdata; 13  14     private transient int elementlength; 15  16     private int size; 17  18     public orderedlinelist() { 19         this(0); 20     } 21  22     public orderedlinelist(int initcapacity) { 23         init(initcapacity); 24     } 25  26     private void init(int initcapacity) { 27         if (initcapacity >= 0) { 28             this.elementdata = (e[]) new object[initcapacity]; 29             this.elementlength = initcapacity; 30         } else { 31             throw new illegalargumentexception(illegal capacity:  + 32                     initcapacity); 33         } 34         this.size = 0; 35     } 36  37     /** 38      * 扩容 39      */ 40     private void dilatation() { 41         int oldcapacity = this.elementlength; 42         int newcapacity = oldcapacity; 43         if (oldcapacity <= this.size) { 44 newcapacity = oldcapacity + init_capacity; 45 }else if(oldcapacity - init_capacity > this.size){ 46             newcapacity = oldcapacity - init_capacity; 47         } 48         if (oldcapacity != newcapacity){ 49             e[] newelementdata = (e[]) new object[newcapacity]; 50             system.arraycopy(elementdata, 0, newelementdata, 0, oldcapacity); 51             this.elementlength = newcapacity; 52             this.elementdata = newelementdata; 53         } 54     } 55  56     /** 57      * 校验列表索引越界 58      * @param index 59      */ 60     private void checkcapacity(int index){ 61         if (index > this.size - 1 || index < 0) 62 throw new indexoutofboundsexception(new stringbuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").tostring()); 63 } 64 65 @override 66 public boolean isempty() { 67 return this.size == 0; 68 } 69 70 @override 71 public void clear() { 72 this.init(0); 73 } 74 75 @override 76 public e get(int index) { 77 this.checkcapacity(index); 78 return this.elementdata[index]; 79 } 80 81 @override 82 public int indexof(e e) { 83 for (int i = 0; i < this.size; i++){ 84 if (e == null && elementdata[i] == null || e.equals(elementdata[i])){ 85 return i; 86 } 87 } 88 return -1; 89 } 90 91 @override 92 public boolean contains(e e) { 93 return this.indexof(e) > 0; 94     } 95  96     @override 97     public e set(int index, e e) { 98         this.checkcapacity(index); 99         this.dilatation();100         e oldelement = this.elementdata[index];101         this.elementdata[index] = e;102         return oldelement;103     }104 105     @override106     public e remove(int index) {107         this.dilatation();108         e e = elementdata[index];109         if (index == size - 1) elementdata[index] = null;110         else {111             int length = size - index - 1;112             system.arraycopy(elementdata, index + 1, elementdata, index, length);113         }114         size --;115         return e;116     }117 118     @override119     public e add(e e) {120         return this.add(size, e);121     }122 123     @override124     public e add(int index, e e) {125         this.dilatation();126         if (index == size) elementdata[index] = e;127         else {128             index++;129             int lastlength = size - index;130             e[] lastelementdata = (e[]) new object[lastlength];131             system.arraycopy(elementdata, index, lastelementdata, 0, lastlength);132             elementdata[index] = e;133             system.arraycopy(lastelementdata, 0, elementdata, index + 1, lastlength);134         }135         size ++ ;136         return e;137     }138 139     @override140     public int size() {141         return this.size;142     }143 144 }
view code
以上就是浅析线性表的原理及简单实现的详细内容。