数据结构

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率

常见的数据结构

常见的数据结构可以分为 线性数据结构 与 非线性数据结构

线性数据结构

• 数组（Array）
• 链表（Linked List）
• 栈（Stack）
• 队列（Queue）

数组 (Array)

数组是将相同类型的元素存储在连续内存空间的数据结构，其长度不可变。
构建数组需要在初始化时给定长度，并对数组每个索引元素赋值

// 方式一：初始化一个长度为5的数组 array
int[] array = new int[5];
// 元素赋值
array[0] = 2;
array[1] = 0;
array[2] = 6;
array[3] = 4;
array[4] = 1;

// 方式二：使用直接赋值的初始化方式
int[] array = {2, 0, 6, 4, 1};

可变数组是经常使用的数据结构，基于数组和扩容机制实现，相比普通数组更加灵活。

// 初始化可变数组
List<Integer> array = new ArrayList<>();
// 向尾部添加元素
array.add(2);
array.add(0);
array.add(6);
array.add(4);
array.add(1);

链表 (Linked List)

链表以节点为单位，每个元素都是一个独立的对象，在内存空间的存储是非连续的。
链表的节点对象具有两个成员变量： 值（val）、后继节点引用（next）

    class ListNode {
        // 节点值
        int val;
        // 后继节点引用
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    
    // 实例化节点

    // 节点head
    ListNode n1 = new ListNode(4);
    ListNode n2 = new ListNode(5);
    ListNode n3 = new ListNode(1);

    // 构建引用指向
    n1.next = n2;
    n2.next = n3;    

栈（stack）

栈是一种具有 “先入后出” 特点的抽象数据结构，可使用数组或链表实现

    Stack<Integer> stack = new Stack<>();
    // 元素1进栈
    stack.push(1);
    // 元素2进栈
    stack.push(2);
    
    // 出栈 -> 元素2
    stack.pop();
    // 出栈 -> 元素1
    stack.pop();

注意：通常情况下，不推荐使用Java的Vector以及其子类Stack，而一般将LinkedList作为栈来使用。实现如下：

    LinkedList<Integer> stack = new LinkedList<>();
    // 元素1入栈
    stack.addLast(1);
    // 元素2入栈
    stack.addLast(2);

    // 出栈 -> 元素2
    stack.removeLast();
    // 出栈 -> 元素1
    stack.removeLast();

队列（Queue）

队列是一种具有 “先入先出” 特点的抽象数据结构，可使用链表实现

    Queue<Integer> queue = new LinkedList<>();

    // 元素1入队
    queue.offer(1);
    // 元素2入队
    queue.offer(2);
    
    // 删除第一个
    // 出队 -> 元素1
    queue.poll();
    // 出队 -> 元素2
    queue.poll();

非线性数据结构

• 树（Tree）
• 堆（Heap）
• 散列表（Hashing）
• 图（Graph）

树（Tree）

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。
以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。

    class TreeNode {
        // 节点值
        int val;
        // 左子节点
        TreeNode left;
        // 右子节点
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    
    // 初始化节点

    // 根节点 root
    TreeNode n1 = new TreeNode(3);
    TreeNode n2 = new TreeNode(4);
    TreeNode n3 = new TreeNode(5);
    TreeNode n4 = new TreeNode(1);
    TreeNode n5 = new TreeNode(2);

    // 构建引用指向
    n1.left = n2;
    n1.right = n3;
    n2.left = n4;
    n2.right = n5;