189 8069 5689
本篇内容介绍了“什么是线性表、顺序表、链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联建站服务项目包括特克斯网站建设、特克斯网站制作、特克斯网页制作以及特克斯网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，特克斯网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到特克斯省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
首先来看一下线性表，顺序表，和链表之间的区别和联系：
线性表：
逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构，而顺序表、链表都是一种线性表。
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
我们首先定义一个线性表的抽象类，主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现：
/** * 线性表 * * @author ervin * @Date 2021/4/18 */ public interface ListInterface{ /** * 初始化 * @param size */ void init(int size); /** * 长度 * @return */ int length(); /** * 是否为空 * @return */ boolean isEmpty(); /** * 获取元素下标 * @param t * @return */ int eleIndex(T t); /** * 根据index获取数据 * @param index * @return * @throws Exception */ T getEle(int index) throws Exception; /** * 根据index插入数据 * @param index * @param t * @throws Exception */ void add(int index,T t) throws Exception; /** * 删除元素 * @param index * @throws Exception */ void delete(int index) throws Exception; /** * 尾部插入元素 * @param t * @throws Exception */ void add(T t) throws Exception; /** * 修改 * @param index * @param t * @throws Exception */ void set(int index,T t) throws Exception; }
顺序表是基于数组实现的，由于数组中的数据时存储的一块连续的内存中，插入、删除元素会导致部分元素的移动，效率较低，但是查询效率却十分快。
顺序表元素插入示意图：
这里以插入为例做说明，删除操作正好相反。
如果要删除下标为 2 的元素时，下标为 2 及之后的元素，从左至右，依次左移一位。
另外，顺序表的插入需要考虑 “扩容”
代码实现：
/** * 顺序表实现 * * @author ervin * @Date 2021/4/18 */ public class SeqListimplements ListInterface { //数组存放数据 private Object[] date; private int length; public SeqList() { //初始大小默认为10 init(10); } @Override public void init(int initSize) { this.date = new Object[initSize]; length = 0; } @Override public int length() { return this.length; } @Override public boolean isEmpty() { //是否为空 return this.length == 0; } @Override public int eleIndex(T t) { for (int i = 0; i < date.length; i++) { if (date[i].equals(t)) { return i; } } return -1; } @Override public T getEle(int index) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } return (T) date[index]; } @Override public void add(T t) throws Exception { //尾部插入 add(length, t); } @Override public void add(int index, T t) throws Exception { if (index < 0 || index > length) { throw new Exception("数值越界"); } //扩容 if (length == date.length) { Object[] newDate = new Object[length * 2]; for (int i = 0; i < length; i++) { newDate[i] = date[i]; } date = newDate; } //后面元素后移动 for (int i = length - 1; i >= index; i--) { date[i + 1] = date[i]; } //插入元素 date[index] = t; length++; } @Override public void delete(int index) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } //index之后元素前移动 for (int i = index; i < length; i++) { date[i] = date[i + 1]; } length--; } @Override public void set(int index, T t) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } date[index] = t; } }
链表存储数据的空间是不连续的，有一个个 “node” 连接起来，形成链表，每一个 “node” 不仅存放数据本身，还存放了下一个 “node” 的地址。
如图：
链表查找元素，需要遍历查找，效率较低；插入删除元素，只需要，修改指针，效率很高。
链表无需考虑 “扩容”
链表元素插入示意：
链表元素删除示意图：
代码实现：
