点个赞，看一看，好习惯！本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录，这是我花了 3 个月总结的一线大厂 Java 面试总结，本人已拿大厂 offer。一、线性表
另外，原创文章首发在我的个人博客：blog.ouyangsihai.cn，欢迎访问。
一个线性表（
Linear List）是由n(n≥0)个数据元素（结点，它可以是一个字母，数字，记录或更复杂的信息）所构成的有限序列。线性表逻辑地表示为：（a0,a1,…,an-1)。其中，n为线性表的长度，n=0时为空表。称i为ai在线性表中的位序号。然后，我们对顺序存储结构用图来做一个理解。
1.1 顺序存储结构理解 顺序储存结构是用数组来保存数据的。如下图：
文章图片
说明：线性表也就是数组的一种特殊储存方式：从头到尾依次储存数据。下面这种情况就不是线性表：
文章图片
1.2 插入数据 1. 线性表为空的情况
文章图片
很简单，当线性表为空时，将数据放到0的位置上就可以了
2. 插入到末尾
文章图片
说明：1和2是一种情况，都是将数据直接添加到线性表的末尾。3. 一般情况
文章图片
说明：简单来理解，就是腾出地方，然后插入,即：将要插入的位置的元素的位置之后的元素往后移动一个位置。1.3 移除数据 1. 末尾的数据移除
文章图片
说明：很简单，直接置空就可以了。2.一般情况
文章图片
说明：跟插入的一般操作相反，先移除，再把坑填上,即：把后面的元素往前移动一个位置。看完上面的理解之后，我们再来看java的具体实现，这个也是
ArrayList的实现方式。二、线性表的抽象数据类型
首先，我们给出线性表ode抽象数据类型。
| 1、线性表的置空操作： | clear() |
|---|---|
| 2、线性表判空操作： | isEmpty() |
| 3、求线性表的长度： | length( ) |
| 4、取元素操作： | get( i ) |
| 5、插入操作： | insert( i, x ) |
| 6、删除操作： | remove( i) |
| 7、查找操作： | indexOf(x ) |
| 8、输出操作： | display() |
public interface IList {
public void clear();
// 将一个已经存在的线性表置成空表public boolean isEmpty();
// 判断当前线性表中的数据元素个数是否为0,若为0则函数返回true，否则返回falsepublic int length();
// 求线性表中的数据元素个数并由函数返回其值public Object get(int i) throws Exception;
// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常public void insert(int i, Object x) throws Exception;
// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素xpublic void remove(int i) throws Exception;
// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常public int indexOf(Object x);
// 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1public void display();
// 输出线性表中的数据元素}
三、线性表的顺序存储
线性表它包括顺序表，链式表，这篇文章先介绍介绍顺序表。
1、概念 顺序存储指用一组地址连续的存储单元 依次存放 线性表中的数据元素的存储结构。用顺序存储的线性表就称为顺序表，所有数据元素的存储位置均取决于第一个数据元素的存储位置。
2、特点
- 逻辑上相邻的数据元素，赋以相邻的存储位置；
- 存储密度高；
- 便于随机存取；
- 不便于插入、删除操作。
3、顺序表接口的描述
public class SqList implements IList {
private Object[] listElem;
// 线性表存储空间private int curLen;
// 当前长度// 顺序表的构造函数，构造一个存储空间容量为maxSize的线性表
public SqList(int maxSize) {
curLen = 0;
// 置顺序表的当前长度为0
listElem = new Object[maxSize];
// 为顺序表分配maxSize个存储单元
}// 将一个已经存在的线性表置成空表
public void clear() {
curLen = 0;
// 置顺序表的当前长度为0}// 判断当前线性表中数据元素个数是否为0,若为0则函数返回true，否则返回false
public boolean isEmpty() {
return curLen == 0;
}// 求线性表中的数据元素个数并由函数返回其值
public int length() {
return curLen;
// 返回顺序表的当前长度
}// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常
public Object get(int i) throws Exception {
if (i < 0 || i > curLen - 1) // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在");
// 输出异常return listElem[i];
// 返回顺序表中第i个数据元素
}// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x
public void insert(int i, Object x) throws Exception {
if (curLen == listElem.length) // 判断顺序表是否已满
throw new Exception("顺序表已满");
// 输出异常if (i < 0 || i > curLen) // i小于0或者大于表长
throw new Exception("插入位置不合理");
// 输出异常for (int j = curLen;
j > i;
j--)
listElem[j] = listElem[j - 1];
// 插入位置及之后的元素后移listElem[i] = x;
// 插入x
curLen++;
// 表长度增1
}// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
if (i < 0 || i > curLen - 1) // i小于1或者大于表长减1
throw new Exception("删除位置不合理");
// 输出异常for (int j = i;
j < curLen - 1;
j++)
listElem[j] = listElem[j + 1];
// 被删除元素之后的元素左移curLen--;
// 表长度减1
}// 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1
public int indexOf(Object x) {
int j = 0;
// j为计数器
while (j < curLen && !listElem[j].equals(x))
// 从顺序表中的首结点开始查找，直到listElem[j]指向元素x或到达顺序表的表尾
j++;
if (j < curLen)// 判断j的位置是否位于表中
return j;
// 返回x元素在顺序表中的位置
else
return -1;
// x元素不在顺序表中
}// 输出线性表中的数据元素
public void display() {
for (int j = 0;
j < curLen;
j++)
System.out.print(listElem[j] + " ");
System.out.println();
// 换行}
}
上面我们基本上实现了java版的线性表，但是，有一个问题就是我们的数据只能是
int，因此，在上面的基础上，我们再对数据类型进行泛型化。public class SequenceList{
//默认长度
private int DEFAULT_SIZE = 2;
//定义一个数组用于保存线性表的长度
private Object[] elementData;
//用于保存数组长度
private int capacity;
//保存顺序表中当前元素的个数
private int size = 0;
/**
* 构造一个默认长度的空线性表
*/
public SequenceList(){
capacity = DEFAULT_SIZE;
elementData = https://www.it610.com/article/new Object[capacity];
}
/**
* 用一个初始化元素来创建线性表
* @param element 初始化元素
*/
public SequenceList(T element){
this();
elementData[0] = element;
size++;
}
/**
* 用一个元素和指定长度来创建线性表
* @param element 元素
* @param initSize 指定长度
*/
public SequenceList(T element,int initSize){
capacity = 1;
if(capacitysize){
throw new IndexOutOfBoundsException("数组越界异常");
}
ensureCapacity(size+1);
//把index以后的元素都后移一位
System.arraycopy(elementData, index, elementData, index+1, size-index);
elementData[index] = element;
size++;
}
/**
* 表长
* @return
*/
public int length(){
return size;
}
/**
* 向表中添加元素
* @param element
*/
public void add(T element){
insert(element, size);
}
/**
* 得到线性表存储的对象
* @param index 获得的位置
* @return得到的结果
*/
public T get(int index){
if(index<0||index>size)
throw new IndexOutOfBoundsException("数组越界异常");
return (T)elementData[index];
}
/**
* 判断线性表是否为空
* @return
*/
public boolean isEmpty(){
return size==0;
}
/**
* 清空线性表
*/
public void clear(){
Arrays.fill(elementData, null);
size = 0;
}
/**
* 获取指定位置的前一个元素
* @param index 线性表位置，若是取线性表最后一个元素，必须index = size,
* size为线性表元素个数
* @return
*/
public T priorElem(int index){
if(index>0&&indexsize-1){
throw new IndexOutOfBoundsException("数组越界异常");
}else{
//把数组前移一位
System.arraycopy(elementData, index+1, elementData, index, size-index-1);
size--;
//清空最后一个元素
elementData[size]=null;
}
}/**
* 获取指定线性表位置的后一个元素
* @param index 线性表位置，若是取线性表第0个元素，必须index=-1
* @return
*/
public T nextElem(int index){
if (index==-1) {
return (T)elementData[0];
}
else if (index-1) {
return (T)elementData[index+1];
}else{
throw new IndexOutOfBoundsException("数组越界异常");
}
}/**
* 确保数组所需长度大于数组原有长度
* @param mCapacity 数组所需长度
*/
private void ensureCapacity(int mCapacity){
if(mCapacity>capacity){
capacity=mCapacity+2;
//System.out.println("capacity:"+capacity);
elementData = https://www.it610.com/article/Arrays.copyOf(elementData, capacity);
}
}
}
这个代码是不是简洁多了，这个也是比较接近
ArrayList的源码。我相信，通过上面的介绍，然后小伙伴们把这些代码
敲几遍，记住一定要敲出来，这样才能够体会。如果你这样做了，我相信这个你肯定能够掌握了，下面我们做一个线性表的应用。四、顺序表应用举例：
编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为（a1,a2,…,an-k,an-k+1,…, an），循环向右移动k位后变成（an-k+1,…, an ,a1,a2,…,an-k）。要求时间复杂度为O（n）。1、编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作（函数如下）。在上面SqList类中加上下面函数，
public void shit(int k) {
int n=curLen,p=0,i,j,l;
Object temp;
for(i=1;
i<=k;
i++)
if(n%i==0&&k%i==0) //求n和k的最大公约数p
p=i;
for(i=0;
i2、然后我们测试一下
public class Result {
public static void main(String[] args) throws Exception {
SqList L = new SqList(10);
for (int i = 0;
i <= 8;
i++)
L.insert(i, i);
System.out.println("右移前顺序表中的各个数据元素为：");
L.display();
L.shit(3);
System.out.println("右移3位后顺序表中的各个数据元素为：");
L.display();
}
}
结果：
右移前顺序表中的各个数据元素为：
0 1 2 3 4 5 6 7 8
右移3位后顺序表中的各个数据元素为：
6 7 8 0 1 2 3 4 5
注意：如果上面的讲解还有什么疑问的话，欢迎小伙伴们在留言区留言和大家一起探讨学习。
点个赞，看一看，好习惯！本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录，这是我花了 3 个月总结的一线大厂 Java 面试总结，本人已拿大厂 offer。最后，再分享我历时三个月总结的 Java 面试 + Java 后端技术学习指南，这是本人这几年及春招的总结，已经拿到了大厂 offer，整理成了一本电子书，拿去不谢，目录如下：
另外，原创文章首发在我的个人博客：blog.ouyangsihai.cn，欢迎访问。
文章图片
现在免费分享大家，在下面我的公众号 程序员的技术圈子 回复 面试 即可获取。
文章图片
有收获？希望老铁们来个三连击，给更多的人看到这篇文章 1、老铁们，关注我的原创微信公众号「程序员的技术圈子」，专注于 Java、数据结构和算法、微服务、中间件等技术分享，保证你看完有所收获。
2、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我继续写作，嘻嘻。
3、另外，原创文章首发在我的个人博客：blog.ouyangsihai.cn，欢迎访问。
【√|数据结构（线性表（java实现））】点赞是对我最大的鼓励
↓↓↓↓↓↓
