数据结构的存储方式只有两种：数组和链表，这两个是其他数据结构实现的基础。

在编写程序的过程中，我们常常需要「找到」一个位置来存放「中间数据」。此时，我们常常定义变量来存储他们。当创建变量时，计算机会为其创建一个单独的「空间」来存放特定类型的数据。

如下所示，我们创建了一个score变量来存放一位同学的成绩。

var score = 80;

计算机会在内存中单独开辟一片空间来存放数据，并且告诉程序相应的内存地址。如图所示，该变量的内存地址是0x00000005。

当我们需要存储多个相同类型的数据时，似乎使用变量就显得不太「靠谱」了

var score1 = 80;var score2 = 90;var score3 = 59;var score4 = 66;var score5 = 11;var score6 = 99;var score7 = 55;var score8 = 73;

如果有 200 个学生，难不成定义 200 个变量来存储学生成绩？这时可以使用数组和链表来存储。

数组

使用数组时，计算机会在内存中开辟一整段连续的空间用于存放数据。依然以学生成绩为例。

var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};

如图所示，计算机为学生成绩分别开辟了 8 份空间用来分别存放 8 位学生的考试成绩。然而这里又出现了一个问题，如果想要添加第 9 位学生成绩时会怎么样？

答案就是，计算机会重新在内存中找一份空间用于存放这 9 位学生成绩。这也是为什么数组一旦创建就不可变。

数组的操作

在数组中，针对一个元素的位置有一个专业术语称为索引（又称下标）。我们通常通过索引（下标）来获取、修改数组元素

数组的索引由 0 开始，最大值为数组元素总数 - 1。

数组元素数据的获取

数组元素数据通过数组名[索引]来获取。如以下代码展示了如何遍历一个数组。

var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};for(var i = 0; i < scores.length; i++){    System.out.println(scores[i]);}

数组元素数据的修改

数组元素数据可以通过数组名[索引] = 新数据来修改。如以下代码展示了将scores数组中第 4 号元素（11分）修改为81分。

var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};scores[4] = 81;

数组元素的插入

如果需要在数组之间的某个位置插入一个元素，则需要将其后面的元素整体向后挪一位。当数组空间不足时，你需要重新创建一个空间来存放新的数组。

数组元素的删除

数组中一个元素删除时，通常使得其右边的元素向左挪一位。

链表

与数组不同，链表中的元素可以在任意的内存位置存在。

依然以上面的学生成绩为例，其在内存中如图所示。

一个简易链表的实现如下：

链表的操作

在链表中，我们通常将元素称为一个节点(node)，一个节点保存了其上下节点的地址。

通常节点的设计如下：

class Node {    int score;    Node prev;    Node next;    public Node(int score) {        this.score = score;    }}

链表元素数据的获取

在链表中，一个元素数据需要由上一个元素逐步向下寻找。具体代码实现可以参照下面的get(int index)方法。

链表元素数据的修改

在链表中，想要修改一个元素的数据首先要找到该元素，然后对其进行修改。具体代码实现可以参照下面的update(int index, int newData)方法。

链表元素的插入

在链表中，想要插入一个元素可以将上一个节点的next对象以及下一个节点的prev对象指向新的元素。具体代码实现可以参照下面的insert(int index, int data)方法。

链表元素的删除

在链表中，想要删除一个元素只需要确保没有任何一个元素指向该节点即可。具体代码实现可以参照下面的remove(int index)方法。

简易链表的实现

public class MyLinkedList {    /**     * 头节点指针     */    private Node head;    /**     * 尾节点指针     */    private Node last;    /**     * 链表实际长度     */    private int size;    /**     * 链表插入元素     *     * @param data  插入元素     * @param index 插入位置     */    public void insert(int index, int data) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("超出链表节点范围！");        }        final var insertedNode = new Node(data);        insertedNode.prev = last;        if (size == 0) {            // 空链表            head = insertedNode;            last = insertedNode;        } else if (index == 0) {            // 插入头部            insertedNode.next = head;            head = insertedNode;        } else if (size == index) {            // 插入尾部            last.next = insertedNode;            last = insertedNode;        } else {            // 插入中间            final var prevNode = get(index - 1);            insertedNode.next = prevNode.next;            prevNode.next = insertedNode;        }        size++;    }    /**     * 修改数据元素     *     * @param index    修改元素索引     * @param newData  修改值     */    public void update(int index, int newData) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("超出链表节点范围！");        }        final var node = get(index);        node.data = newData;    }    /**     * 链表删除元素     *     * @param index 删除位置     */    public Node remove(int index) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("超出链表节点范围！");        }        Node removedNode = null;        if (index == 0) {            // 删除头节点            removedNode = head;            head = head.next;            head.prev = null;        } else if (index == size - 1) {            // 删除尾节点            final var prevNode = get(index - 1);            removedNode = prevNode.next;            prevNode.next = null;            last = prevNode;        } else {            // 删除中间节点            final var prevNode = get(index - 1);            final var nextNode = prevNode.next.next;            removedNode = prevNode.next;            nextNode.prev = prevNode;            prevNode.next = nextNode;        }        size--;        return removedNode;    }    /**     * 链表查找元素     *     * @param index 查找位置     */    public Node get(int index) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("超出链表节点范围！");        }        var temp = this.head;        for (int i = 0; i < index; i++) {            temp = temp.next;        }        return temp;    }    /**     * 输出链表     */    public void output() {        var temp = this.head;        while (temp != null) {            System.out.println(temp.data);            temp = temp.next;        }    }    /**     * 链表节点     */    private static class Node {        Node prev;        int data;        Node next;        Node(int data) {            this.data = data;        }    }    public static void main(String[] args) throws Exception {        final var myLinkedList = new MyLinkedList();        myLinkedList.insert(0, 3);        myLinkedList.insert(1, 7);        myLinkedList.insert(2, 9);        myLinkedList.insert(3, 5);        myLinkedList.output();        System.out.println("--------------");        myLinkedList.update(3, 8);        myLinkedList.remove(0);        myLinkedList.output();    }}

数组和链表的优劣

如下是数组和链表操作运行所需的时间：