数据结构：计算机存储、组织数据的方式
数据库 CRUD 操作：增加（Create）、读取查询（Retrieve）、更新（Update）、删除（Delete）

数组（Array）

擅长做查询和修改，不擅长做增加（可能需要扩容）和删除（移位）
在随机访问时性能最好

// 基于数组的线性表（集合）
public class MyArrayList {
    private Object[] elementData;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }
    public MyArrayList(int initiallyCapacity) {
        if (initiallyCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        elementData = new Object[initiallyCapacity];
    }
}
// 1. 在形参包含索引的方法内，检查传入的索引是否越界
// 2. 写每个方法时，最后要判断该方法是否会改变 size 的值

链表（Linked List）

擅长做增加和删除（头和尾），不擅长做查询和修改
在执行插入、删除操作时有较好的性能
单向链表、双向链表

图 1 链表的结构

// 基于双向链表的线性表（集合）
public class MyLinkedList {
    private Node first; // 链表的第一个节点
    private Node last; // 链表的最后一个节点
    private int size; // 节点的数量
    // 删除链表中第一次出现的元素 o
    public boolean removeFirstOccurrence(Object o) {
        Node currentNode = first;
        while (currentNode != null) {
            if (currentNode.ele.equals(o)) {
                // 删除节点
                if (currentNode == first) {
                    currentNode.next.prev = null;
                    first = currentNode.next;
                    size--;
                    return true;
                } else if (currentNode == last) {
                    currentNode.prev.next = null;
                    last = currentNode.prev;
                    size--;
                    return true;
                } else {
                    currentNode.prev.next = currentNode.next;
                    currentNode.next.prev = currentNode.prev;
                    size--;
                    return true;
                }
            }
            currentNode = currentNode.next;
        }
        return false;
    }
    // 返回链表的字符串表示形式
    public String toString() {
        if (size == 0) {
            return "[]";
        }
        Node currentNode = first;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(currentNode.ele);
            if (i != size - 1) {
                sb.append(", ");
            } else {
                sb.append("]");
            }
            currentNode = currentNode.next;
        }
        return sb.toString();
    }
    // 内部类 Node
    private static class Node {
        Node prev; // 上一个节点
        Node next; // 下一个节点
        Object ele; // 节点中的数据
        Node(Object ele) {
            this.ele = ele;
        }
    }
}
// 1. 先修改当前节点，再修改当前节点的上一节点、当前节点的下一节点，最后修改链表的 first、last
// 2. 写每个方法时，最后要判断该方法是否会改变 size 的值