1. 线性表

1-1. 顺序表

顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。

Array数组

Array是固定大小的顺序表，定义为：

int[] arr = new int[] {1,2,3,4,5};

ArrayList集合

ArrayList是可以动态扩容的顺序表。

1-2. 链表

自定义链表

单链表节点

public class ListNode {
     int val; // 值
     ListNode next; // 指向下一个节点
     ListNode(int x) { val = x; }
}

双链表节点

public class ListNode {
     int val; // 值
     ListNode next; // 指向下一个节点
     ListNode pre; // 指向上一个节点
     ListNode(int x) { val = x; }
}

LinkedList

此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。

2. 队列

Queue和Deque接口都是队列的数据结构

• Queue是普通队列的接口
• Deque是双端队列的接口

---

2-1. ArrayDeque

ArrayDeque是Java集合框架中的一个双端队列（Deque）实现类。它基于数组实现，可以在两端高效地插入和删除元素。

实现原理

• ArrayDeque内部维护了一个循环数组，通过两个指针(front和rear)来标记队列的头部和尾部。当向队列中添加元素时，rear指针向后移动；当从队列中删除元素时，front指针向后移动。如果数组满了，ArrayDeque会自动扩容。
• ArrayDeque的底层数组长度是2的幂次方，这样可以通过位运算来实现循环队列的操作，提高性能。

2-2. LinkedList

LinkedList也是Java集合框架中的一个双端队列（Deque）实现类。它基于链表实现，可以在任意位置高效地插入和删除元素。

实现原理

• LinkedList内部使用双向链表来存储元素。每个节点都包含一个前驱节点和一个后继节点的引用。通过这种方式，LinkedList可以在任意位置高效地插入和删除元素。
• LinkedList还有一个头结点和尾节点的引用，分别表示链表的头部和尾部。通过这两个引用，可以快速访问到链表的第一个和最后一个元素。

2-3. 区别

1. ArrayDeque不允许null元素，而LinkedList则允许null元素。
2. 如果是使用栈/队列操作，ArrayList明显快于LinkedList
3. LinkedList实现了List接口 ，可以将值插入到指定位置处。

3. 栈

3-1. ArrayDeque

同上，只是操作API方法的不同

3-2. LinkedList

同上，只是操作API方法的不同

4. 树

树又分为：二叉树、二叉搜索树、平衡二叉树、红黑树、B树等。

4-1. 二叉树定义

public class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {val = x;}
}

5. 图

5-1. 图定义

图有节点和边组成，实现的方式有：

Map<Integer, List<int[]>> graph = new HashMap();