什么是线性表、顺序表、链表

本篇内容介绍了"什么是线性表、顺序表、链表"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

首先来看一下线性表，顺序表，和链表之间的区别和联系：

• 线性表：

1. 逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构，而顺序表、链表都是一种线性表。

2. 线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种"一对一"关系的数据就可以使用线性表来存储。

• 顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。

线性表

我们首先定义一个线性表的抽象类，主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现：

/** * 线性表 * * @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 SeqList implements 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" 的地址。

如图：

• 链表查找元素，需要遍历查找，效率较低；插入删除元素，只需要，修改指针，效率很高。

• 链表无需考虑 "扩容"

链表元素插入示意：

链表元素删除示意图：

代码实现：

/** * 链表实现 * * @author ervin * @Date 2021/4/18 */public class LinkList implements ListInterface {    private static class Node {        T item;        Node next;        Node(T element, Node 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
双链表
在实际应用中双链表的应用多一些，就比如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个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。
"什么是线性表、顺序表、链表"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！