下面小编就为大家带来一篇浅谈线性表的原理及简单实现方法。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧
一、线性表
原理：零个或多个同类数据元素的有限序列
原理图：
特点 ：
1、有序性
2、有限性
3、同类型元素
4、第一个元素无前驱，最后一个元素无后继，中间的元素有一个前驱并且有一个后继
线性表是一种逻辑上的数据结构，在物理上一般有两种实现 顺序实现和链表实现
二、基于数组的 线性表顺序实现
原理 ： 用一段地址连续的存储单元依次存储线性表数据元素。
原理图：
算法原理：
1、初始化一个定长的数组空间 elementData[] , size 存储长度 存储元素
2、通过索引来快速存取元素
3、通过数组复制实现元素的插入和删除
总结：
1、无需为表示表中元素之间的逻辑关系增加额外的存储空间
2、可以快速存取表中任一位置元素
3、插入和删除需要进行数组复制（即大量元素的移动）
4、线性表长度变化较大时，需要频繁扩容，并造成存储空间碎片
实现代码：
接口定义：
package online.jfree.base; /** * author : Guo LiXiao * date : 2017-6-14 11:46 */ public interface LineList{ /** * lineList 是否为空 * @return */ boolean isEmpty(); /** * 清空 lineList */ void clear(); /** * 获取指定位置元素 * @param index * @return */ E get(int index); /** * 获取元素第一次出现的位置 * @param e * @return */ int indexOf(E e); /** * 判断 lineList是否包含指定元素 * @param e * @return */ boolean contains(E e); /** * 设置指定位置数据，如数据已存在 则覆盖原数据 * @param index * @param e * @return */ E set(int index, E e); /** * 移除指定位置元素 * @param index * @return */ E remove(int index); /** * 在lineList结尾插入元素 * @param e * @return */ E add(E e); /** * 在index后面插入元素 * @param index * @param e * @return */ E add(int index, E e); /** * 返回lineList长度 * @return */ int size(); }
算法实现：
package online.jfree.base; /** * author : Guo LiXiao * date : 2017-6-15 13:44 */ public class OrderedLineListimplements LineList { private static final int INIT_CAPACITY = 10; private transient E[] elementData; private transient int elementLength; private int size; public OrderedLineList() { this(0); } public OrderedLineList(int initCapacity) { init(initCapacity); } private void init(int initCapacity) { if (initCapacity >= 0) { this.elementData = (E[]) new Object[initCapacity]; this.elementLength = initCapacity; } else { throw new IllegalArgumentException("Illegal Capacity: " + initCapacity); } this.size = 0; } /** * 扩容 */ private void dilatation() { int oldCapacity = this.elementLength; int newCapacity = oldCapacity; if (oldCapacity <= this.size) { newCapacity = oldCapacity + INIT_CAPACITY; }else if(oldCapacity - INIT_CAPACITY > this.size){ newCapacity = oldCapacity - INIT_CAPACITY; } if (oldCapacity != newCapacity){ E[] newElementData = (E[]) new Object[newCapacity]; System.arraycopy(elementData, 0, newElementData, 0, oldCapacity); this.elementLength = newCapacity; this.elementData = newElementData; } } /** * 校验列表索引越界 * @param index */ private void checkCapacity(int index){ if (index > this.size - 1 || index < 0) throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString()); } @Override public boolean isEmpty() { return this.size == 0; } @Override public void clear() { this.init(0); } @Override public E get(int index) { this.checkCapacity(index); return this.elementData[index]; } @Override public int indexOf(E e) { for (int i = 0; i < this.size; i++){ if (e == null && elementData[i] == null || e.equals(elementData[i])){ return i; } } return -1; } @Override public boolean contains(E e) { return this.indexOf(e) > 0; } @Override public E set(int index, E e) { this.checkCapacity(index); this.dilatation(); E oldElement = this.elementData[index]; this.elementData[index] = e; return oldElement; } @Override public E remove(int index) { this.dilatation(); E e = elementData[index]; if (index == size - 1) elementData[index] = null; else { int length = size - index - 1; System.arraycopy(elementData, index + 1, elementData, index, length); } size --; return e; } @Override public E add(E e) { return this.add(size, e); } @Override public E add(int index, E e) { this.dilatation(); if (index == size) elementData[index] = e; else { index++; int lastLength = size - index; E[] lastElementData = (E[]) new Object[lastLength]; System.arraycopy(elementData, index, lastElementData, 0, lastLength); elementData[index] = e; System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength); } size ++ ; return e; } @Override public int size() { return this.size; } }
