曾经有一个问题：IT、IT，到底是 I 重要，还是 T 重要？答案是 I。其中 I 代表 IT 技术的终极目标 Information（信息），而 T（Technology）只是储存和管理 Information 的手段。

换句话来说，编程的本质就是对数据（信息以数据的形式而存在）的处理，实际编程中不得不处理大量数据，因此实际动手编码之前必须先分析处理这些数据，处理数据之间存在的关系。

由于现实的数据元素之间存在着纷繁芜杂的逻辑关系，应用程序则需要分析这个数据的逻辑结构，并采用合适的物理结构来储存（在内存中储存，并非数据库储存）这些数据，并以此为基础对这些数据进行相应的操作。当然，还要分析各种数据结构在时间开销、空间开销上的优势。这种专门研究应用程序中数据之间的逻辑关系、储存方式及其操作的学问就是所谓的数据结构。

从数据的逻辑结构来分，数据元素质检存在的关联关系被称为数据的逻辑结构。归纳起来，应用程序中的数据大致有如下 4 类基本的逻辑结构。

• 集合：数据元素之间只有“同属于一个集合”关系；
• 线性结构：数据元素质检存在一个对一个的关系；
• 树形结构：数据元素之间存在一个对多个的关系；
• 图状结构或网状结构：数据元素之间存在多个对多个的关系。

对于数据不同的逻辑结构，计算器在物理磁盘上通常有 2 种物理储存结构：

• 顺序储存结构；
• 链式存储结构。

线性表概述

对于常用数据结构，可以将其简单地分为线性结构和非线性结构，其中线性结构主要是线性表，而非线性结构则主要是树和图。

线性表的定义及逻辑结构

线性表（Linear List）是有 n（n ≥ 0） 个数据元素（节点）a1，a2，a3…，an 组成的有限序列。

线性表中每个元素必须具有相同的结构（即拥有相同的数据项）。线性表是线性结构中最常用而又最简单的一种数据结构。很对读者容易把线性表的数据元素理解成简单数据值，其实不然，如下表所示数据表其实也是一个线性表

对于上面表格所示的数据而言，它本质上依然是线性表，只是它的每个数据元素都是一个“复合”的员工对象，每个数据元素包含 4 个数据项（也被称为 Field）：员工编号、姓名、年龄和学历。

也就是说，线性表中每个数据元素其实可以包含若干个数据项，如果使用 a0 来代表线性表中第一个元素，其中 a1 元素可以包含若干个数据项。关于线性表还可以有如下定义：

• 线性表中包含的数据元素个数 n 被称为表的长度，当线性表的长度为 0 时该表也被称为空表；
• 当 n > 0 时，表可表示为（a1，a2，a3，…，an）。

对于一个非空、有限的线性表而言，它总是具有如下基本特征：

• 总存在唯一的“第一个”数据元素；
• 总存在唯一的“最后一个”数据元素；
• 除第一个数据元素外，集合中的每一个元素都只有一个前驱的数据元素；
• 除最后一个数据元素外，集合中的每一个数据元素都只有一个后继的数据元素。

线性表的基本操作

如果需要实现一个线性表，程序首先需要确定该线性表的每个数据元素。接下来，应该为线性表实现如下基本操作：

• 初始化：通常是一个构造器，用于创建一个空的线性表；
• 返回线性表的长度：该方法用于返回线性表中数据元素的个数；
• 获取指定索引处的元素：根据索引返回线性表中的数据元素；
• 按值查找数据元素的位置：如果线性表中存在一个或多个与查找值相等的数据元素，方法返回第一个搜索值相等的数据元素的索引，否则返回-1。
• 直接插入数据元素：向线性表的头部插入一个数据元素，线性表长度+1；
• 向指定位置插入数据元素：向线性表的指定索引处插入一个数据元素，线性表长度+1；
• 直接删除数据元素：删除线性表头部的数据元素，线性表长度-1；
• 删除线性表中指定位置的数据元素：删除线性表中指定索引处的数据元素，线性表长度-1；
• 判断线性表是否为空：该方法判断线性表是否为空，如果线性表为空，返回 true，否则返回 false；
• 清空线性表：将线性表清空。

简单了解这些关于线性表的基础只是之后，接下来将使用 Java 为工具，分别实现顺序储存结构的线性表、链式存储结构的线性表。

顺序存储结构

线性表的顺序存储结构是指用一组地址连续的储存单元依次存放线性表的元素。当程序采用顺序存储结构来实现线性表时，线性表中相邻元素两个元素 ai 和 ai+1 对应的存储地址 loc（ai） 和 loc（ai=1）也是响铃的。

换句话说，顺序结构线性表中数据元素的物理关系和逻辑关系是一致的，线性表中数据元素的存储地址可按如下公式计算。
loc(ai) = loc(a0) + i*b (0 < i < n)
上面公式中 b 代表每个数据元素的储存单元。从上面公式可以看出：程序获取线性表中每个元素的储存起始地址的时间相同，读取表中数据元素的时间也相同。而且顺序表中每个元素都可随机存取，因此顺序存储的线性表是一种随机存取的存储结构。

为了使用顺序结构实现线性表，程序通常会采用数组来保存线性表中的数据元素。

当使用数组来保存线性表中的元素时，程序可以很容易地实现线性表中所包含的方法，但当试图向线性表的指定位置添加元素时，系统实现该方法则稍微有些复杂。

线性表的插入运算是指在表的第 i（0 ≤ i < n）个位置，插入一个新的数据元素 x，使长度为 n 的线性表 a0，…，ai-1，ai，…，an-1，变成长度为 n+1 的线性表，a0，…，ai-1，x，ai，…，an-1，向顺序结构的线性表中插入元素。

对于这个插入操作，还有一个必须考虑的问题：由于顺序线性表底层采用数据来存储数据元素，因此插入数据元素时必须保证不会超过底层数组的容量。如果线性表中元素的个数超过了底层数组的长度，那就必须为该线性表扩充底层数组的长度。

线性表的删除运算是指将表的第 i（0 ≤ i < n）个位置的数据元素删除，使长度为 n 的线性表 a0，…，ai-1，ai，ai+1，…，an-1 变成长度为 n-1 的线性表 a0，…，ai-1，ai+1，…，an-1。

public class SequenceList<T> {
    private final int DEFAULT_SIZE = 16;
    //保存数组的长度
    private int capacity;
    //定义一个数组用于保存顺序线性表的元素
    private Object[] elementData;
    //保存顺序表中元素的当前个数
    private int size = 0;
    //以默认数组长度创建空顺序线性表
    public SequenceList() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    //以一个初始化元素创建顺序线性表
    public SequenceList(T element) {
        this();
        elementData[0] = element;
        size++;
    }

    /**
     * 以指定长度的数组来创建顺序线性表
     * @param element 指定顺序线性表中第一个元素
     * @param initSize 指定顺序线性表底层数组的长度
     */
    public SequenceList(T element, int initSize) {
        capacity = 1;
        //把capacity设为大于initSize的最小2的n次方
        while (capacity < initSize) {
            capacity <<= 1;
        }
        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }
    //获取顺序线性表的大小
    public int length() {
        return size;
    }
    //获取顺序线性表中索引为i处的元素
    public T get(int i) {
        if (i < 0 || i > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        return (T)elementData[i];
    }
    //查找顺序线性表中指定元素的索引
    public int locate(T element) {
        for (int i = 0;i < size;i++) {
            if (elementData[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }
    //向顺序线性表的指定位置插入一个元素
    public void insert(T element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        ensureCapacity(size + 1);
        //将指定索引处之后的所有元素向后移动一格
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }
    //再顺序线性表的开始处添加一个元素
    public void add(T element) {
        insert(element, size);
    }
    //很麻烦，而且性能很差
    private void ensureCapacity(int minCapacity) {
        //如果数组的原有长度小于目前所需的长度
        if (minCapacity > capacity) {
            //不断地将 capacity * 2，直到 capacity大于minCapacity
            while (capacity < minCapacity) {
                capacity <<= 1;
            }
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
    //删除顺序线性表中指定索引处的元素
    public T delete(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        T oldValue = (T)elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        //清空最后一个元素
        elementData[--size] = null;
        return oldValue;
    }
    //删除顺序线性表中农工最后一个元素
    public T remove() {
        return delete(size - 1);
    }
    //判断顺序线性表是否为空
    public boolean empty() {
        return size == 0;
    }
    //清空线性表
    public void clear() {
        //将底层数组所有元素赋为null
        Arrays.fill(elementData, null);
        size = 0;
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (int i = 0;i < size;i++) {
                sb.append(elementData[i].toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

上面采用数组实现了一个顺序线性表，可以向这个顺序线性表中添加元素、删除元素等等。下面程序简单示范了对顺序线性表的操作：

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> list = new SequenceList<>();
        list.add("aaaa");
        list.add("bbbb");
        list.add("cccc");
        //再索引为1处插入一个新元素
        list.insert("dddd", 1);
        //输出顺序线性表的元素
        System.out.println(list);
        //删除索引为2处的元素
        list.delete(2);
        System.out.println(list);
        //获取cccc字符串再顺序线性表中的位置
        System.out.println("cccc在顺序线性表中的位置：" + list.locate("cccc"));
    }
}

运行结果：

[aaaa,dddd,bbbb,ccc]
[aaaa,dddd,ccc]
cccc在顺序线性表中的位置：2

从上面运行结果可以看出，这个 SequenceList 类部分实现了 ArrayList 的功能，或者说，它其实是一个简单版本的 ArrayList。

实际上线性表的英文单词就是 List，即 ArrayList 就是 JDK 为线性表所提供的顺序实现。

本节所实现的 SequenceList 类也是线性不安全的，在单线程环境下这个类可以正常工作，但如果放在多线程环境下，这个工具类可能引起线程安全问题。

链式存储结构

链式存储结构的线性表（也被简称为链表）将采用一组地址任意的存储单元存放线性表中的数据元素。链式结构的线性表不会按照线性表的逻辑顺序来保存数据元素，它需要在每一个数据元素里保存一个引用下一个数据元素的引用（或者叫指针）。

由于不必须按顺序存储，链表在插入、删除数据元素时比顺序线性表快的多，但是查找一个节点或者访问特定编号的节点则比顺序线性表慢很多。

使用链表结构可以克服顺序线性表（基于数组）需要预先知道数据大小的缺点，链式结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表结构失去了数组随机存取的有点，同时链表由于增加了节点的指针域，空间开销比较大。

对于链式结构存储的顺序表而言，它的每个节点都必须包含数据元素本身和一或两个引用来引用上一个/下一个节点的引用。也就是说，有如下公式：节点 = 数据元素 + 引用下一个节点的引用 + 引用上一个节点的引用。

链表是多个相互引用的节点的集合，整个链表总是从头结点开始，然后依次向后指向每个节点。

空链表就是头结点为 null 的链表。

单链表上的基本运算

单链表指的是每个节点只保留一个引用，该引用指向当前节点的下一个节点，没有引用指向头结点，尾节点的 next 引用为 null。

对于单链表，系统建立单链表的过程就是不断添加节点的过程。动态建立单链表有以下两种方式：

• 头插法建表：该方法从一个空表开始，不断地创建新节点，将数据元素存入节点的 data 域中，然后不断地以新节点为头节点，让新节点指向原有的头节点。
• 尾插法建表：该方法是将新街点插入到当前链表的表尾上，因此需要为链表定义一个引用变量来保存链表的最后一个节点。

头插法建立链表虽然简单，但生成的链表中节点的次序和输入的顺序相反；若希望二者次序一致，则应该采用尾插法来建立链表。

对于单链表而言，常用的操作有：

• 查找
• 插入
• 删除

1. 查找操作
   单链表的查找操作可以分为以下两种：

   • 按序号查找第 index 个节点：从 header 节点依次向下在单链表中找第 index 个节点。算法为，设 head 为头，current 为当前节点（初始时 current 从 header 开始），0 为头节点序号，i 为计数器，则可使 current 依次下移寻找节点，并使 i 同时递增记录节点序号，直到返回指定节点。
   • 在链表中查找指定 element 元素：查找是否有等于给定值 element 的节点。若有，返回首次找到的其值为 element 的节点的索引；否则，返回 -1.查找过程从开始节点出发，顺着链表逐个将节点的值和给定值 element 做比较。
2. 插入操作
   插入操作是将值为 element 的新节点插入到链表的第 index 个节点的位置上。因此，首先找到索引为 index-1 的节点，然后生成一个数据域为 element 的新节点 newNode，并领 index-1 处节点的 next 引用新节点，新街点的 next 引用原来 index 处的节点。
3. 删除操作
   删除操作是将链表的第 index 个节点删去。因为在单链表中，第 index 个节点是由 index-1 处的节点引用的，因此删除 index 处的节点将先获取 index-1 处节点，然后让 index-1 处节点的 next 引用到原 index+1 处节点，并释放 index 处节点即可。

掌握上面方法的思路之后，下面根据该思路采用 Java 语言来实现一个单链表：

public class LinkList<T> {
    //定义一个内部类Node,Node实例代表链表的节点
    private class Node {
        //保存节点的数据
        private T data;
        //指向下个节点的引用
        private Node next;
        //无参数的构造器
        public Node(){
        }
        //初始化全部属性的构造器
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    //保存该链表的头节点
    private Node header;
    //保存该链表的尾节点
    private Node tail;
    //保存该链表中已包含的节点数
    private int size;
    //创建空链表
    public LinkList() {
        //空链表header和tail都是null
        header = null;
        tail = null;
    }
    //以指定数据元素来创建链表，该链表只有一个元素
    public LinkList(T element) {
        header = new Node(element, null);
        //只有一个节点，header、tail都指向该节点
        tail = header;
        size++;
    }
    //返回链表的长度
    public int length() {
        return size;
    }
    //获取链式线性表中索引为index处的索引
    public T get(int index) {
        return getNodeByIndex(index).data;
    }
    //根据索引index获取指定位置的节点
    private Node getNodeByIndex(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        //从header节点开始
        Node current = header;
        for (int i = 0;i < size && current != null;i++, current = current.next) {
            if (i == index) {
                return current;
            }
        }
        return null;
    }
    //查找链式线性表中指定元素的索引
    public int locate(T element) {
        //从头节点开始搜索
        Node current = header;
        for (int i = 0;i < size && current != null;i++, current = current.next) {
            if (current.data.equals(element)) {
                return i;
            }
        }
        return -1;
    }
    //向线性链式表的指定位置插入一个元素
    public void insert(T element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        //如果还是空链表
        if (header == null) {
            add(element);
        } else {
            //当index为0时，即在表头处插入
            if (index == 0) {
                addAtHeader(element);
            } else {
                //获取插入点的前一个节点
                Node prev = getNodeByIndex(index - 1);
                //让prev的next指向新节点，让新节点的next引用指向原来prev的下一个节点
                prev.next = new Node(element, prev.next);
                size++;
            }
        }
    }
    //采用尾插法为链表添加新节点
    public void add(T element) {
        //如果该链表还是空链表
        if (header == null) {
            header = new Node(element, null);
            //只有一个节点，header、tail都指向该节点
            tail = header;
        } else {
            //创建新节点
            Node newNode = new Node(element, null);
            //让尾节点的next指向新增的节点
            tail.next = newNode;
            //以新节点作为新的尾节点
            tail = newNode;
        }
        size++;
    }
    //采用头插法为链表添加新节点
    public void addAtHeader(T element) {
        //创建新节点，让新节点的next指向原来的header
        //并以新节点作为新的header
        header = new Node(element, header);
        //如果插入之前是空链表
        if (tail == null) {
            tail = header;
        }
        size++;
    }
    //删除链式线性表中指定索引处的元素
    public T delete(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        Node del = null;
        //如果被删除的是header节点
        if (index == 0) {
            del = header;
            header = header.next;
        } else {
            //获取删除点的前一个节点
            Node prev = getNodeByIndex(index - 1);
            //获取将要被删除的节点
            del = prev.next;
            //让被删除节点的next指向被删除的下一个节点
            prev.next = del.next;
            //将被删除节点的next引用赋为null
            del.next = null;
        }
        size--;
        return del.data;
    }
    //删除链式线性表中最后一个元素
    public T remove() {
        return delete(size - 1);
    }
    //判断线性表是否为空表
    public boolean empty() {
        return size == 0;
    }
    //清空线性表
    public void clear() {
        //将header、tail赋为null
        header = null;
        tail = null;
        size = 0;
    }
    @Override
    public String toString() {
        //链表为空链表时
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = header;current != null;current = current.next) {
                sb.append(current.data.toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

提供上面 LinkList 类时，程序一样可以将其当成线性表来使用。下面程序测试了 LinkList 类的用法：

public class LinkListTest {
    public static void main(String[] args) {
        LinkList<String> list = new LinkList<>();
        list.insert("aaaa", 0);
        list.add("bbbb");
        list.add("cccc");
        //在索引为1处插入一个新元素
        list.insert("dddd", 1);
        //输出顺序线性表的元素
        System.out.println(list);
        //删除索引为2的元素
        list.delete(2);
        System.out.println(list);
        //获取cccc字符串在链表中的位置
        System.out.println("cccc在链表中的位置：" + list.locate("cccc"));
        System.out.println("链表中索引为2处的元素：" + list.get(2));
    }
}

运行结果：

[aaaa,dddd,bbbb,ccc]
[aaaa,dddd,ccc]
cccc在链表中的位置：2
链表中索引为2处的元素：cccc

对于链表而言，它的功能与前面介绍的顺序线性表基本相同，因为它们都是线性表，只是底层实现不同而已。因此，链表和顺序表只是性能上的差异：顺序表在随机存取时性能很好，但插入、删除时性能就不如链表；链表在插入、删除时候性能很好，但随机存取的性能就不如顺序表。

循环链表

循环链表是一种首尾相接的链表。将单链表的尾节点 next 指针改为单链表 header 节点，这个单链表就成了循环链表。

循环链表具有一个显著特征：从链表的任意节点出发均可找到表中其它所有节点，因此循环链表可以被视为“无头无尾”。

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得它实现许多方法时会更容易，在这样的链表上设计算法会比普通链表更加容易。

新加入的节点应该是在第一个节点之前（采用头插法插入），还是最后一个节点之后（采用尾插法插入），可以根据实际要求灵活处理，具体实现区别不大。

就程序实现来说，循环链表与普通单链表差别并不大，保证链表中 tail.next = header 即可。

除此之外，还有一种伪循环链表，就是在访问到最后一个节点之后的时候，手工地跳转到第一个节点，访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，当直接用循环链表比较麻烦或者可能有问题时，可以考虑使用这种伪循环链表。

双向链表

如果为每个节点保留两个引用 prev 和 next，让 prev 指向当前节点的上一个节点，让 next 指向当前节点的下一个节点，此时的链表既可以向后依次访问每个节点，也可向前依次访问每个节点，这种形式的链表被称为双向链表。

双向链表是一种对称结构，它克服了单链表上指针单向性的缺点，其中每个节点即可向前引用，也可向后引用，这样可以更方便地插入、删除数据元素。

与单链表类似的是，如果将链表的 header 节点与 tail 节点链在一起就构成了双向循环链表。

1. 双向链表的查找
   由于双向链表既可从 header 节点开始依次向后搜索每个节点，也可从 tail 节点开始，依次向前搜索每个节点，因此当程序试图从双向链表中搜索指定索引处的节点时，既可从该链表的 header 节点开始搜索，也可从该链表的 tail 节点开始搜索。至于到底应该从 header 开始搜索，还是应该从 tail 开始搜索，则取决于被搜索节点是更靠近 header 还是更靠近 tail。
   一般来说，可以通过被搜索 index 的值来判断它更靠近 header，还是更靠近 tail。如果 index<size/2，可判断该位置更靠近 header，应从 header 开始搜索；反之，则可以判断该位置更靠近 tail，那就应从 tail 开始搜索。
2. 双向链表的插入
   双向链表的插入操作更复杂，向双向链表中插入一个新节点必须同时修改连个方向的指针（即引用）。如果需要在第 i 个节点插入一个新节点，需要将第 i-1 个节点的 next 节点指向这个新节点，然后将原来第 i 个节点的 prev 节点也指向这个新节点，然后新节点的 prev 节点指向第 i-1 个节点，新节点的 next 节点指向原来第 i 个节点。
3. 双向链表的删除
   双向链表中，删除一个节点也需要同时修改两个方法的指针。如果需要删除第 i 节点，那么需要将第 i-1 节点的 next 节点指向原来第 i+1 节点，将原来第 i+1 节点的 prev 节点指向第 i-1 节点，同时去除第 i 节点的 next 及 prev 引用。

掌握上面的理论之后，可以使用 Java 语言来实现一个双向链表，因为双向链表需要维护两个方向的指针，因此程序在添加节点、删除节点时都比维护普通单链表更复杂。

public class DuLinkList<T> {
    //定义一个内部类Node，Dode实例代表链表的节点
    private class Node {
        //保存节点的数据
        private T data;
        //指向上个节点的引用
        private Node prev;
        //指向下个节点的引用
        private Node next;
        //无参数的构造器
        public Node() {
        }
        //初始化全部属性的构造器
        public Node(T data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }
    //保存该链表的头节点
    private Node header;
    //保存该链表的尾节点
    private Node tail;
    //保存该链表中已包含的节点数
    private int size;
    //创建空链表
    public DuLinkList() {
        //空链表，header 和 tail 都是null
        header = null;
        tail = null;
    }
    //已指定数据元素来创建链表，该链表只有一个元素
    public DuLinkList(T element) {
        header = new Node(element, null, null);
        //只有一个节点，header、tail都指向该节点
        tail = header;
        size++;
    }
    //返回链表的长度
    public int length() {
        return size;
    }
    //获取链式线性表中索引为index处的元素
    public T get(int index) {
        return getNodeByIndex(index).data;
    }
    //根据索引index获取指定位置的节点
    private Node getNodeByIndex(int index) {
        if (index < 0|| index > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        if (index <= size / 2) {
            //从header节点开始
            Node current = header;
            for (int i = 0;i <= size / 2 && current != null;i++, current = current.next) {
                if (i == index) {
                    return current;
                }
            }
        } else {
            //从tail节点开始搜索
            Node current = tail;
            for (int i = size - 1;i > size / 2 && current != null;i++, current = current.prev) {
                if (i == index) {
                    return current;
                }
            }
        }
        return null;
    }
    //查找链式线性表中指定元素的索引
    public int locate(T element) {
        //从头节点开始搜索
        Node current = header;
        for (int i = 0;i < size && current != null;i++, current = current.next) {
            if (current.data.equals(element)) {
                return i;
            }
        }
        return -1;
    }
    //向线性链式表的指定位置插入一个元素
    public void insert(T element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        //如果还是空链表
        if (header == null) {
            add(element);
        } else {
            //当index为0时，也就是在链表头插入
            if (index == 0) {
                addAtHeader(element);
            } else {
                //获取插入点的前一个节点
                Node prev = getNodeByIndex(index - 1);
                //获取插入点的节点
                Node next = prev.next;
                //让新街点的next引用指向next节点，prev引用指向prev节点
                Node newNode = new Node(element, prev, next);
                //让prev的next节点指向新节点
                prev.next = newNode;
                //让prev的下一个节点的prev指向新节点
                next.prev = newNode;
                size++;
            }
        }
    }
    //采用尾插法为链表添加新节点
    public void add(T element) {
        //如果该链表还是空链表
        if (header == null) {
            header = new Node(element, null, null);
            //只有一个节点，header、tail都指向该节点
            tail = header;
        } else {
            //创建新节点，新街点的prev指向原tail节点
            Node newNode = new Node(element, tail, null);
            //让尾节点的next指向新增的节点
            tail.next = newNode;
            //以新节点作为新的尾节点
            tail = newNode;
        }
        size++;
    }
    //采用头插法为链表添加新节点
    public void addAtHeader(T element) {
        //创建新节点，让新节点的next指向原来的header
        //并以新节点作为新的heaer
        header = new Node(element, null, header);
        //如果插入之前是空链表
        if (tail == null) {
            tail = header;
        }
        size++;
    }
    //删除链式线性表中指定索引处的元素
    public T delete(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        Node del = null;
        //如果被删除的是header节点
        if (index == 0) {
            del = header;
            header = header.next;
            //释放新的header节点的prev引用
            header.prev = null;
        } else {
            //获取删除节点的前一个节点
            Node prev = getNodeByIndex(index - 1);
            //获取将要被删除的节点
            del = prev.next;
            //让被删除节点的 next 指向被删除节点的下一个节点
            prev.next = del.next;
            //让被删除节点的下一个节点的prev指向prev节点
            if (del.next != null) {
                del.next.prev = prev;
            }
            //将被删除节点的 prev、next引用赋为null
            del.prev = null;
            del.next = null;
        }
        size--;
        return del.data;
    }
    //删除链式线性表中最后一个元素
    public T remove() {
        return delete(size - 1);
    }
    //判断链式线性表是否为全空表
    public boolean empty() {
        return size == 0;
    }
    //清空线性表
    public void clear() {
        header = null;
        tail = null;
        size = 0;
    }
    @Override
    public String toString() {
        //链表为空链表时
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = header;current != null;current = current.next) {
                sb.append(current.data.toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
    public String reverseToString() {
        //链表为空链表时
        if (empty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = tail;current != null;current = current.prev) {
                sb.append(current.data.toString() + ",");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

从上面程序可以看出，由于双向链表需要同时维护两个方向的指针，因此添加节点、删除节点时的指针维护成本更大；当双向链表具有两个方法的指针，因此可以向两个方向搜索节点，因此双向节点在搜索节点、删除指定索引处节点时具有较好的性能。下面程序简单测试了 DuLinkList 的功能：

public class DuLinkTest {
    public static void main(String[] args) {
        DuLinkList<String> list = new DuLinkList<>();
        list.insert("aaaa", 0);
        list.add("bbbb");
        list.insert("cccc", 0);
        //在索引为1处插入一个新元素
        list.insert("dddd", 1);
        //输出顺序线性表的元素
        System.out.println(list);
        //删除索引为2处的元素
        list.delete(2);
        System.out.println(list);
        System.out.println(list.reverseToString());
        //获取cccc字符串在顺序线性表中的位置
        System.out.println("cccc在顺序线性表中的位置：" + list.locate("cccc"));
        System.out.println("链表中索引1处的元素：" + list.get(1));
        list.remove();
        System.out.println("调用remove方法后的链表：" + list);
        list.delete(0);
        System.out.println("调用delete(0)后的链表：" + list);
    }
}

运行上面的程序，可以看到如下结果：

[cccc,dddd,aaaa,bbb]
[cccc,dddd,bbb]
[bbbb,dddd,ccc]
cccc在顺序线性表中的位置：0
链表中索引1处的元素：dddd
调用remove方法后的链表：[cccc,ddd]
调用delete(0)后的链表：[ddd]

从上面的结果可以看出，双向链表依然是一个线性表，它依然可以“盛装”多个具有线性结构的数据元素。

线性表的分析

前面介绍了线性表的相关概念，并介绍了线性表的两种具体实现：顺序实现和链式实现。接下来，将对线性表的实现和功能做进一步的分析。

线性表的实现分析

线性表的顺序和链式两种实现各有优势，具体对比如下表：

线性表的功能

经过前面介绍，不难发现，线性表本质上是一个充当容器的工具类，当程序有一组结构相同的数据元素需要保存时，就可以考虑使用线性表来保存它们。

从某种程度来看，线性表是数组的加强，线性表比数组多了如下几个功能：

• 线性表的长度是可以动态改变，但 Java 数组的长度是固定的；
• 线性表可以插入元素，数组无法插入元素；
• 线性表可以删除元素，数组无法删除元素，数组只能将指定元素赋为 null，但各种元素依然存在；
• 线性表提供方法来搜索元素的位置，但数组一般不提供该方法；
• 线性表提供方法来清空所有元素，但数组一般不提供蕾丝方法。

从上面线性表的实现能发现线性表比数组功能强大的理由：顺序结构的线性表可以说是包装过的数组，自然会提供更多额外的方法来简化操作。

对于 Java 来说，其实经常在使用线性表 List。Java 的 List 接口就代表了线性表，线性表的两种实现分别是 ArrayList 和 LinkedList，其中 LinkedList 还是一个双向链表。而作为 List 接口的两个实现类，ArrayList 代表了线性表的数组实现，LinkedList 则代表了线性表的链式实现。

虽然线性表对于编程非常重要，但对于 Java 而言，想要使用线性表的哪种实现就使用哪种实现————只要选择使用 ArrayList，还是 LinkedList。

本文转载自：《疯狂Java 突破程序员基本功的16课》第九章 线性表