浅谈线性表的原理及简单实现方法

一、线性表

原理：零个或多个同类数据元素的有限序列

原理图：

特点 ：

有序性

有限性

同类型元素

第一个元素无前驱，最后一个元素无后继，中间的元素有一个前驱并且有一个后继

线性表是一种逻辑上的数据结构，在物理上一般有两种实现 顺序实现和链表实现

二、基于数组的 线性表顺序实现

原理 ： 用一段地址连续的存储单元依次存储线性表数据元素。

原理图：

算法原理：

初始化一个定长的数组空间 elementData[] , size 存储长度 存储元素

通过索引来快速存取元素

通过数组复制实现元素的插入和删除

总结：

无需为表示表中元素之间的逻辑关系增加额外的存储空间

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

插入和删除需要进行数组复制（即大量元素的移动）

线性表长度变化较大时，需要频繁扩容，并造成存储空间碎片

实现代码：

接口定义：

package online.jfree.base;public interface LineList <E>{  boolean isEmpty();  void clear();  E get(int index);  int indexOf(E e);  boolean contains(E e);  E set(int index, E e);  E remove(int index);  E add(E e);  E add(int index, E e);  int size();}