深入浅析Java中的线性表?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等。而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表,单链表以及双链表的各种基本操作。
<强> 1:线性表抽象的数据类型
线性表:是由n (n>=0)个数据相同的元素组成的有限序列。线性表的定义接口如下
公共接口IList{/* * *是否为空 * @return */布尔isEmpty ();/* * *表的长度 * @return */int长度();/* * *根据索引获取长度 * @param我 * @return */T (int i);/* * *设置我第个元素值为x * @param我 * @param x */空集(int i T x);/* * *在线性表最后插入x元素 * @param x */空白添加x (T);/* * *异常第i个元素并返回值 * @param我 * @return */T删除(int i);/* * *删除线性表中所有元素 */空白removeAll ();/* * *查询首次出现关键字为关键的元素 * @param关键 * @return */T搜索(T键); 插入空白(int i T x);/* * *升序添加 * @param x */空隙插入x (T);/* * *升序删除 * @param x */空白消除x (T); }
2：线性表顺序表示和实现
线性表的顺序存储结构是一组连续的内存单元依次存放的线性表的数据元素，元素的物理地址和逻辑地址次序是相同的。我们叫做这种存储方式为顺序表。
由于数组只能进行赋值和取值，而且长度是不可变化的，所以给我们的操作带来很大的麻烦，但是用顺序表就可以进行删除，插入等操作。其实顺序表内部同样适用数组来表示的，只不过这个数据我们可以改变他的长度，这样说来我们就好办了，首先我们要为顺序表定义一个数组，同时在定义一个值来记录线性表的长度，所以第一步我们就有了如下
准备事件做好了以后，我们肯定会对顺序表进行初始化，刚刚开始数组的长度肯定是0。但是我们必须要为数组开辟一个内存空间，来存储要插入的元素，如下
其他的都比较简单，我主要说下插入和删除
插入一个元素的时候，如果插在第i个位置，那么意味着它后面所有的元素前部往后面移一位，但是我们必须把i个位置留出来给即将插入的元素。但是我们还必须考虑，如果这个数组满了的情况。如果满了，我们必须重新为顺序表开辟内存空间，然后把以前的元素进行迁移到新的表中，java实现如下
代码看出，我们把从第i个位置的元素全部往后移（包括第i个元素）然后在把第i个元素进行赋值
删除第i个元素，这个和上面的正好相反，如果删除第i个元素意味着在i之后的元素前部往前移一位。
3：顺序表操作效率分析
因为顺序表是具有索引的，所以get()和set()效率极高，时间复杂度都是O(n)。
从上面发现，在插入和删除的时候都是需要大量元素的移动，因为在各个位置插入元素的概率相同，所以平均插入一个元素要移动的元素是2/n。那么它的时间复杂度就是O(n)，如果要容器满了，那么就需要申请更大的容器来存储新加入的元素，那么效率会更加的低下。所以顺序表的静态性好，动态性就很差了，所以在选择的时候就要注意一下。
4：单链表的实现
线性表的链式存储结构是用若干地址分散的存储单元存储数据元素，逻辑上相邻的2个元素，物理地址不一定相同，这么说来就充分的利用了内存中的地址。但是我们必须用附加信息来连接2个不同的数据元素，所以这里就引进了2个概念，数据域(data)和地址域(next)，其中数据域存储的是这个元素的值，地址域存储下一个元素的地址。其中数据域和地址域联合起来我们称为节点（node）。如果只有后继节点没有前驱节点我们就称为单链表，那么现在我们来看看单链表的实现。
