本篇内容介绍了“什么是线性表、顺序表、链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
首先来看一下线性表，顺序表，和链表之间的区别和联系：
逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构，而顺序表、链表都是一种线性表。
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
线性表
我们首先定义一个线性表的抽象类，主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现：
/**
* 线性表
*
* @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;
}顺序表
顺序表元素插入示意图：
这里以插入为例做说明，删除操作正好相反。
代码实现：
/**
* 顺序表实现
*
* @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;
}
}链表
如图：
链表元素插入示意：
链表元素删除示意图：
代码实现：
/**
* 链表实现
*
* @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(指针)，指向上一个节点。
这一点，在 JDK LinkedList 的源码中有体现，我们来看它的 get(int index) 方法，
接着点进去，看它的 node(int index) 方法
如果 index 位于链表的前半部分，则从前开始查找；反之，则从后开始查找。
总结
单链表查询速度较慢，因为他需要从头遍历，插入删除速度较快；内存利用率高，不会浪费内存，大小没有固定，拓展很灵活
顺序表查询速度较快，插入删除速度较慢
Java中的Arraylist和LinkedList就是两种方式的代表，不过LinkedList使用双向链表优化
双链表的查询速度要优于单链表
从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。
“什么是线性表、顺序表、链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注天达云网站，小编将为大家输出更多高质量的实用文章！