线性表定义

线性表（List）：零个或多个数据元素的有限序列。

首先它是一个序列，其次，线性表强调是有限的。

前驱元素：若A元素在B元素的前面，则称A为B的前驱元素。

后继元素：若B元素在A元素的后面，则称B为A的后继元素。

线性表的特征

数据元素之间具有一种一对一的逻辑关系。

• 第一个数据元素没有前驱，这个数据元素被称为头结点；
• 最后一个数据元素没有后继，这个数据元素被称为尾结点；
• 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

如果把线性表用数学语言来定义，则可以表示为（a1,...ai-1,ai,ai+1,...an），ai-1领先于ai，ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素。

线性表的分类

线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

顺序表设计

顺序表代码实现

@SuppressWarnings("unchecked")
public class SequenceList implements Iterable {
    /**
     * 存储元素的数组
     */
    private T[] elements;

    /**
     * 记录当前顺序表中的元素个数
     */
    private int n;

    /**
     * 创建容量为capacity的SequenceList对象
     */
    public SequenceList(int capacity) {
        // 初始化数组
        this.elements = (T[]) new Object[capacity];
        // 初始化长度
        n = 0;
    }

    /**
     * 空置线性表
     */
    public void clear() {
        n = 0;
    }

    /**
     * 判断线性表是否为空，是返回true，否返回false
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * 获取线性表中元素的个数
     */
    public int length() {
        return n;
    }

    /**
     * 读取并返回线性表中的第i个元素的值
     */
    public T get(int i) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("当前元素不存在！");
        }
        return elements[i];
    }

    /**
     * 在线性表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i, E e) {
        if (n == elements.length) {
            throw new RuntimeException("当前表已满");
        }
        // 先把i索引处的元素及其后面的元素依次向后移动一位
        for (int j = n; j > i; j--) {
            elements[j] = elements[j - 1];
        }
        // 再把t元素放到i索引处
        elements[i] = t;
        n++;
    }

    /**
     * 向线性表中添加一个元素t
     */
    public void insert(E e) {
        if (i == elements.length) {
            throw new RuntimeException("当前表已满");
        }
        if (i < 0 || i > n) {
            throw new RuntimeException("插入的位置不合法");
        }
        elements[n++] = t;
    }

    /**
     * 删除并返回线性表中第i个数据元素
     */
    public T remove(int i) {
        if (i < 0 || i > n - 1) {
            throw new RuntimeException("当前要删除的元素不存在");
        }
        // 记录i索引处的值
        T current = elements[i];

        // 索引i后面元素依次向前移动一位
        for (int j = i; j < n - 1; j++) {
            elements[j] = elements[j + 1];
        }
        // 元素个数-1
        n--;
        return current;
    }

    /**
     * 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
     */
    public int indexOf(E e) {
        if (t == null) {
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < n; i++) {
            if (Objects.equals(elements[i], t)) {
                return i;
            }
        }
        return -1;
    }
}

顺序表的遍历

一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。

在Java中，遍历集合的方式一般都是用的是forEach循环，如果想让我们的SequenceList也能支持forEach循环，则需要做如下操作：

0. 让SequenceList实现Iterable接口，重写iterator方法；
1. 在SequenceList内部提供一个内部类SIterator，实现Iterator接口，重写hasNext方法和next方法；

public class SequenceList implements Iterable {
    // ...
    @Override
    public Iterator iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator {
        private int cursor;

        public SIterator() {
            this.cursor = 0;
        }

        @Override
        public boolean hasNext() {
            return cursor < n;
        }

        @Override
        public T next() {
            return elements[cursor++];
        }
    }
}

顺序表容量可变

在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。

考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大小？

添加元素时扩容

添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。

移除元素时缩容

移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。

@SuppressWarnings("unchecked")
public class SequenceList {

    /**
     * 向线性表中添加一个元素t
     */
    public void insert(E e) {
        // 如果当前容量已满，那么扩容2倍
        if (n == elements.length) {
            resize(2 * elements.length);
        }
        // ...
    }

    /**
     * 删除并返回线性表中第i个数据元素
     */
    public T remove(int i) {
        // ...

        // 如果当前元素数量小于容量的1/4，那么缩容为1/2
        if (n < elements.length / 4) {
            resize(elements.length / 2);
        }
        return current;
    }

    /**
     * 根据newSize，重置elements的大小
     */
    public void resize(int newSize) {
        // 定义一个临时数组，指向原数组
        T[] temp = elements;
        // 创建新数组
        elements = (T[]) new Object[newSize];
        System.arraycopy(temp, 0, elements, 0, temp.length);
    }
}

扩缩容的原理很简单，是创建一个具有指定新容量的新数组，然后把原来的数据拷贝到新数组。

顺序表的时间复杂度

• get(i)：不论数据元素量n有多大，只需要一次elements[i]就可以获取到对应的元素，所以时间复杂度为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。
• insert(int i,E e)：每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n)；
• remove(int i)：每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大，移动的元素也越多，时间复杂度为O(n)；

由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。

顺序表的优缺点

优点

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
• 可以快速地存取表中任意位置的元素。

缺点

• 插入和删除操作需要移动大量元素；
• 当线性表长度变化较大时，难以确定存储空间的容量；
• 造成存储空间的碎片。

链表

虽然顺序表的查询很快，时间复杂度为O(1)，但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？

有，我们可以使用另外一种存储结构实现线性表，链式存储结构。

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

链表节点设计

@NoArgsConstructor
@AllArgsConstructor
@Data
public class Node {

    /**
     * 存储元素
     */
    private E item;

    /**
     * 指向下一个节点
     */
    private Node next;
}

单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

单向链表设计

单向链表代码实现

public class LinkList implements Iterable {

    /**
     * 记录首节点
     */
    private final Node head;
    /**
     * 记录链表的长度
     */
    private int n;

    public LinkList() {
        // 初始化头结点
        head = new Node<>(null, null);
        // 初始化元素个数
        n = 0;
    }

    /**
     * 空置线性表
     */
    public void clear() {
        head.next = null;
        n = 0;
    }

    /**
     * 判断线性表是否为空，是返回true，否返回false
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * 获取线性表中元素的个数
     */
    public int length() {
        return n;
    }

    /**
     * 读取并返回线性表中的第i个元素的值
     */
    public E get(int i) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法！");
        }
        // 通过循环，从头结点开始往后找，依次找i次，就可以找到对应的元素
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    /**
     * 往线性表中添加一个元素
     */
    public void insert(E e) {
        // 找到当前最后一个节点
        Node n = head; // 头节点不存储数据，所以不能算作第一个元素
        while (n.next != null) {
            n = n.next;
        }
        // 创建新节点，保存元素t
        // 让当前最后一个元素指向新节点
        n.next = new Node<>(e, null);
        // 元素个数+1
        this.n++;
    }

    /**
     * 在线性表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i, E e) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法！");
        }

        // 找到i位置前一个节点
        Node pre = head; // 头节点不存储数据，所以不能算作第一个元素
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }

        // 找到i位置的节点
        Node current = pre.next;

        // 创建新节点，并且新节点需要指向原来i位置的节点
        // 原来i位置的前一个节点指向新节点
        pre.next = new Node<>(e, current);

        // 元素个数+1
        n++;
    }

    /**
     * 删除并返回线性表中第i个数据元素
     */
    public E remove(int i) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法");
        }

        // 找到i位置前一个节点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }

        // 找到i位置的节点
        Node current = pre.next;

        // 找到i位置的下一个节点

        // 前一个节点指向下一个节点
        pre.next = current.next;

        // 元素个数 - 1
        n--;
        return current.item;
    }

    /**
     * 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
     */
    public int indexOf(E e) {
        // 从头结点开始，依次找到每一个节点，取出item，和t比较，如果相同，就返回
        Node n = head;
        for (int i = 0; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(e)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    private static class Node {

        // 存储元素
        T item;
        // 指向下一个节点
        Node next;

        Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

}

循环链表

对于单向链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了。

比如，你是一业务员，家在上海，需要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务，如图所示：

有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海是第一站。你会对这人说什么？神经病。哪有这么傻的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。

显然这表示你是从当中一结点开始遍历整个链表，这都是原来的单链表结构解决不了的问题。事实上，把北京和上海之间连起来，形成一个环就解决了前面所面临的困难。这就是循环链表。

从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。

在单向链表中，最后一个节点的指针为NULL，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。

如果链表中没有元素，那么头结点也需要指向自己，从而形成环。

循环链表代码实现

代码实现和单向链表基本一致，只需要在插入尾结点的时候，将尾结点指向头结点即可。

public void insert(E e) {
    // 找到当前最后一个节点
    // 头节点不存储数据，所以不能算作第一个元素
    var n = head;
    while (n.next != null) {
        n = n.next;
    }
    // 创建新节点，保存元素t，让当前最后一个元素指向新节点
    // 循环链表，最后一个元素指向头结点
    n.next = new Node<>(e, head);
    // 元素个数+1
    this.n++;
}

同时，在构造和清空链表时，让头结点指向自己

public CycleLinkList() {
    // 初始化头结点
    head = new Node<>(null, null);
    head.next = head;
    // 初始化元素个数
    n = 0;
}

/**
 * 清空线性表
 */
public void clear() {
    head.next = head;
    n = 0;
}

双向链表

继续刚才的例子，你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时你怎么办？

有人又出主意了，你可以先飞回上海，一路再乘火车走遍这几个城市，到了北京后，你再飞回上海。你会感慨，人生中为什么总会有这样出馊主意的人存在呢？真要气死人才行。哪来这么麻烦，我一路从北京坐火车或汽车回去不就完了吗。

我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗？当然可以，只不过需要加点东西而已。

双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

双向链表结点设计

@AllArgsConstructor
private static class Node {
    // 存储元素
    E item;
    // 指向上一个节点
    Node pre;
    // 指向下一个节点
    Node next;
}

双向链表设计

双向链表代码实现

public class DoubleLinkList implements Iterable {

    /**
     * 记录首节点
     */
    private final Node head;
    /**
     * 记录尾节点
     */
    private Node last;
    /**
     * 记录链表的长度
     */
    private int n;

    public DoubleLinkList() {
        // 初始化头结点
        head = new Node<>(null, null, null);
        // 初始化尾节点
        last = null;
        // 初始化元素个数
        n = 0;
    }

    /**
     * 空置线性表
     */
    public void clear() {
        head.next = null;
        last = null;
        n = 0;
    }

    /**
     * 判断线性表是否为空，是返回true，否返回false
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * 获取线性表中元素的个数
     */
    public int length() {
        return n;
    }

    /**
     * 获取头结点
     */
    public E getFirst() {
        if (isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    /**
     * 获取尾节点
     */
    public E getLast() {
        if (isEmpty()) {
            return null;
        }
        return last.item;
    }

    /**
     * 读取并返回线性表中的第i个元素的值
     */
    public E get(int i) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法！");
        }
        // 通过循环，从头结点开始往后找，依次找i次，就可以找到对应的元素
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    /**
     * 往线性表中添加一个元素
     */
    public void insert(E e) {
        if (isEmpty()) {
            // 如果链表为空
            // 创建新的节点
            Node newNode = new Node<>(e, head, null);
            // 让新节点成为尾节点
            last = newNode;
            // 让头结点指向尾节点
            head.next = last;
        } else {
            // 如果链表不为空
            Node tempLast = last;
            // 创建新的节点
            Node newNode = new Node<>(e, tempLast, null);
            // 当前的尾节点指向新节点
            tempLast.next = newNode;
            // 让新节点成为尾节点
            last = newNode;
        }

        // 元素个数+1
        n++;
    }

    /**
     * 在线性表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i, E e) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法！");
        }

        // 找到i位置的前一个节点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        // 找到i位置的节点
        Node current = pre.next;
        // 创建新节点
        Node newNode = new Node<>(e, pre, current);
        // 让i位置的前一个节点指向新节点
        pre.next = newNode;
        // 让i位置的前一个节点变为新节点
        current.pre = newNode;
        // 元素个数+1
        n++;
    }

    /**
     * 删除并返回线性表中第i个数据元素
     */
    public E remove(int i) {
        if (i < 0 || i >= n) {
            throw new RuntimeException("位置不合法");
        }

        // 找到i位置前一个节点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }

        // 找到i位置的节点
        Node current = pre.next;

        // 找到i位置的下一个节点
        Node next = current.next;

        // i位置的前一个节点的下一个节点指向i位置的下一个节点
        pre.next = next;
        // i位置的下一个节点的前一个节点指向i位置的前一个节点
        next.pre = pre;

        // 元素个数 - 1
        n--;
        return current.item;
    }

    /**
     * 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
     */
    public int indexOf(E e) {
        // 从头结点开始，依次找到每一个节点，取出item，和t比较，如果相同，就返回
        Node n = head;
        for (int i = 0; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(e)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    @AllArgsConstructor
    private static class Node {
        // 存储元素
        E item;
        // 指向上一个节点
        Node pre;
        // 指向下一个节点
        Node next;
    }

    private class LIterator implements Iterator {
        private Node n = head;

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public E next() {
            n = n.next;
            return n.item;
        }
    }

}

链表的时间复杂度

• get(int i)：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)；
• insert(int i, E e)：每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)；
• remove(int i)：每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)。

相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，并且在存储过程中不涉及到扩容等操作，同时它并没有涉及的元素的交换。

相比较顺序表，链表的查询操作性能会比较低。

因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。