本篇内容介绍了“什么是线性表、顺序表、链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
首先来看一下线性表，顺序表，和链表之间的区别和联系：
线性表：
逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构，而顺序表、链表都是一种线性表。
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
我们首先定义一个线性表的抽象类，主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现：
/**
* 线性表
*
* @author ervin
* @Date 2021/4/18
*/
public interface ListInterface<T> {
/**
* 初始化
* @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 SeqList<T> implements ListInterface<T> {
//数组存放数据
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” 的地址。
如图：
链表查找元素，需要遍历查找，效率较低；插入删除元素，只需要，修改指针，效率很高。
链表无需考虑 “扩容”
链表元素插入示意：
链表元素删除示意图：
代码实现：
/**
* 链表实现
*
* @author ervin
* @Date 2021/4/18
*/
public class LinkList<T> implements ListInterface<T> {
private static class Node<T> {
T item;
Node<T> next;
Node(T element, Node<T> next) {
this.item = element;
this.next = next;
}
}
Node header;
private int size;
public LinkList(){
this.header = new Node(null,null);
this.size = 0;
}
@Override
public void init(int size) {
}
@Override
public int length() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.length() == 0;
}
@Override
public int eleIndex(T t) {
Node n = header.next;
int index = 0;
while (n.next != null){
if (n.item.equals(t)){
return index;
}
index++;
n = n.next;
}
//找不到返回-1
return -1;
}
@Override
public T getEle(int index) throws Exception {
Node n = getNode(index);
return (T)n.item;
}
@Override
public void add(int index, T t) throws Exception {
//考虑第一个元素
if (index == 0){
this.header.next = new Node(t,null);
} else {
Node n = getNode(index - 1);
//获取到index的上一个元素n, n指向新建的元素，同时新建的元素指向n的下一个元素
n.next = new Node(t,n.next);
}
this.size++;
}
@Override
public void delete(int index) throws Exception {
//index为0时，不用去获取上一个元素，
if (index == 0){
this.header.next = getNode(1);
} else {
Node n = getNode(index - 1);
n.next = n.next.next;
}
size--;
}
@Override
public void add(T t) throws Exception {
add(size,t);
}
@Override
public void set(int index, T t) throws Exception {
Node node = getNode(index);
node.item = t;
}
private Node getNode(int index) throws Exception {
if (index<0 || index > this.size-1){
throw new Exception("数组越界");
}
Node n = header.next;
for (int i = 0;i<index;i++){
n = n.next;
}
return n;
}
}在实际应用中双链表的应用多一些，就比如LinkedList
双链表的一个节点，有存储数据的data，也有后驱节点next(指针)，指向下一个节点，这和单链表是一样的，但它还有一个前驱节点pre(指针)，指向上一个节点。
这样的设计，牺牲了额外的内存类存储 “pre” 指针，但是相比单链表只能 “从头向尾” 查找，双链表不仅可以 “从头向尾”，“从尾向头”，甚至可以从中间开始查找，在有些时候，双链表的查找效率要比单链表快很多。
这一点，在 JDK LinkedList 的源码中有体现，我们来看它的 get(int index) 方法，
接着点进去，看它的 node(int index) 方法
如果 index 位于链表的前半部分，则从前开始查找；反之，则从后开始查找。
单链表查询速度较慢，因为他需要从头遍历，插入删除速度较快；内存利用率高，不会浪费内存，大小没有固定，拓展很灵活
顺序表查询速度较快，插入删除速度较慢
Java中的Arraylist和LinkedList就是两种方式的代表，不过LinkedList使用双向链表优化
双链表的查询速度要优于单链表
从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。
“什么是线性表、顺序表、链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
