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

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

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

• 线性表：

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

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

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

线性表

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

/**
 * 线性表
 *
 * @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个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。

“什么是线性表、顺序表、链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！